Recognizing Reduplicated Forms: Finite-State Buffered Machines (2021)

Abstract: Total reduplication is common in natural language phonology and morphology. However, formally as copying on reduplicants of unbounded size, unrestricted total reduplication requires computational power beyond context-free, while other phonological and morphological patterns are regular, or even sub-regular. Thus, existing language classes characterizing reduplicated strings inevitably include typologically unattested context-free patterns, such as reversals. This paper extends regular languages to incorporate reduplication by introducing a new computational device: finite state buffered machine (FSBMs). We give its mathematical definitions and discuss some closure properties of the corresponding set of languages. As a result, the class of regular languages and languages derived from them through a copying mechanism is characterized. Suggested by previous literature, this class of languages should approach the characterization of natural language word sets.

## some closure properties of fsbms in this section, we show some closure properties of complete-path fsbm-recognizable languages and their linguistic relevance. section 3.1 discusses its closure under intersection with regular languages; section 3.2 shows it is closed under homomorphism; section 3.3 briefly mentions union, concatenation, kleene star. these operations are of special interests because they are regular operations defining regular expressions @xcite . that complete-path fsbms are closed under regular operations leads to a conjecture that the set of languages recognized by the new automata is equivalent to the set of languages denoted by a version of regular expression with copying added. noticeably, given fsbms are fsas with a copying mechanism, the proof ideas in this section are similar to the corresponding proofs for fsas, which can be found in hopcroft and @xcite and @xcite . ## discussion and conclusion in summary, this paper provides a new computational device to compute unrestricted total reduplication on any regular languages, including the simplest copying language l ww where w can be any arbitrary string of an alphabet. as a result, it introduces a new class of languages incomparable to cfls. this class of languages allows unbounded copying without generating non-reduplicative nonregular patterns: we hypothesize context-free string reversals are excluded since the buffer is queue-like. meanwhile, the mcs swiss-german cross-serial dependencies, abstracted as {a i b j c i d j |i, @xmath0, is also excluded, since the buffer works on the same alphabet as the input tape and only matches identical sub-strings. following the sub-classes of 2-way fsts in @xcite @xcite , which successfully capture unbounded copying as functions while exclude the mirror image mapping, complete-path fsbms successfully capture the total-reduplicated stringsets while exclude string reversals. comparison between the characterized languages in this paper and the image of functions in @xcite should be further carried out to build the connection. moreover, one natural next step is to extend fsbms as acceptors to finite state buffered transducers (fsbt). our intuition is fsbts would be helpful in handling the morphological analysis question (@xmath1, a not-yet solved problem in the 2-way fsts that dolatian and heinz (2020) study. after reading the first w in input and buffering this chunk of string in the memory, the transducer can output for each matched symbol when transiting among h states. another potential area of research is applying this new machinery to primitive optimality theory @xcite . @xcite used weighted finite state machine to model constraints while represented the set of candidates by multiple context free grammars to enforce basereduplicant correspondence @xcite . parallel to albro's way, given completepath fsbms are intersectable with fsas, it is possible to computationally implement the reduplica-tive identity requirement by complete-path fsbms without using the full power of mildly context sensitive formalisms. to achieve this goal, future work should consider developing an efficient algorithm that intersects complete-path fsbms with weighted fsas. the present paper is the first step to recognize reduplicated forms in adequate yet more restrictive models and techniques compared to mcs formalisms. there are some limitations of the current approach on the whole typology of reduplication. complete-path fsbms can only capture local reduplication with two adjacent identical copies. as for non-local reduplication, the modification should be straightforward: the machines need to allow the filled buffer in n mode (or in another newly-defined memory holding mode) and match strings only when needed. as for multiple reduplication, complete-path fsbms can easily be modified to include multiple copies of the same base form ({w n | @xmath2, @xmath3, @xmath4. it remains to be an open question on the computational nature of multiple reduplication. last but not the least, as a reviewer points out, recognizing non-identical copies can be achieved by either storing or emptying not exactly the same input symbols, but mapped symbols according to some function f . under this modification, the new automata would recognize {a n b n | @xmath5. in all, detailed investigations on how to modify complete-path fsbms should be the next step to complete the typology.