At the computational level, functions on words are defined by string-to-string transductions (also called mappings or transformations). Transductions have many characterizations, but in linguistics the most popular description is given using transducers. Informally, transducers are idealized machines that transform an input string to an output string. They extend automata (acceptors) with outputs on their transitions. They can be seen as Turing machines with a read-only input tape initially filled with the input word, and a write-only output tape on which to write the output word.

In this paper we will consider three important classes of transducers with a finite number of states: one-way transducers, two-way transducers, and two-way transducers with pebbles, summarized in Table 1. The table lists various formal properties that we will discuss and expand on throughout this section.

For each class, the output head is assumed to move only to the right. For the class of one-way transducer, the input head is also restricted to move to the right on the input tape; for the other classes, the input head can move left or right. These three classes of machines yield three classes of functions: rational, regular, and polyregular. The rational functions can model all attested morphological and phonological processes except for total reduplication (Kaplan & Kay 1994; Roark & Sproat 2007). The regular functions are strictly more expressive than the rational functions, and they can model total reduplication.1 And the most expressive is the class of polyregular functions, which has received more attention in recent years in computer science but not computational linguistics. These different functions display different formal properties that we discuss later.

Note that all the formal results in this section are from the literature on mathematical linguistics or theoretical computer science (Filiot & Reynier 2016; Dolatian & Heinz 2020; Dolatian et al. 2021). We do not provide formal proofs nor do we explain them in mathematical depth. We instead focus on synthesizing all these pre-known results into a single self-contained body on reduplication.

Consider total reduplication, as in the Indonesian example (ia) of buku∼buku ‘books’. Computationally, total reduplication involves making two copies of the input. The process creates exactly one extra copy of the input string. The input string can be of any size.

As a copying function, total reduplication introduces a single extra copy in the output. Such copying functions belong to the class of Regular functions. A regular function can copy a string of unbounded size but only a linearly bounded number of times. Given a string w, the process of generating one extra copy w → ww is a regular function. For a regular function, the size of the output string grows at most linearly with the size of the input string |w|, that is O(n|w|) \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \mathcal{O}(n|w|) \] \end{document} . For total reduplication of an input string w, the size of the output ww is exactly 2|w|. Mnemonically, total reduplication is a case of ‘unbounded fixed-n copying’ where we copy the word to create exactly n = 1 extra copy.

This property of linear-growth rate allows many equivalent characterizations of regular functions, in terms of logic, algebra, and automata (Engelfriet & Hoogeboom 2001; Filiot & Reynier 2016). The one most relevant for linguistics is that Regular functions are exactly the functions computed by deterministic 2-way FSTs (Hopcroft & Ullman 1969; Savitch 1982). The intuition is that each copy is made by the ability of a 2-way transducer to go back-and-forth over the input a bounded number of times while outputting. Figure 1 is a visual representation of a 2-way FST for total reduplication.

Before we demonstrate how this machine models total reduplication, consider the visual properties of the machine in Figure 1. Between any two nodes or states, there is a directed edge called the transition. For example, from state q₀ to state q₁, there is an edge labeled (⋊,λ,+1) \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ (\rtimes,\lambda, + 1) \] \end{document} . The transition means that we read the symbol ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} from the input, we generate an output symbol λ, and we move right (+1) on the input string. In this case, the symbol λ designates the empty string. Elsewhere in the graph, the symbol Σ designates any symbol in our input alphabet (that’s not a word boundary), and the symbol –1 designates moving leftward on the input string.

Let us see how this machine models total reduplication. Table 2 illustrates a derivation using this 2-way FST for the mapping buku→buku∼buku. The steps in our derivation tables have following format where the first element is the processed input string, the second is the current output string, and the third is the transition that was used to go from the previous step to the current step.

The input string is first padded with word boundaries ⋊⋉ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes\ltimes \] \end{document} . In step 1, the machine is in state q₀. We use underlining to show what symbol is to be read next. The first symbol to read is ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} . In step 2, we read ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} , output nothing, move rightward on the input string, and then change to state q₁. The next symbol to read is b. In steps 3–6, we iteratively move left-to-right (+1) on the input string, outputting any input symbol (Σ), and stay in state q₁. This creates the first output copy. Then between step 6–7, we reach the end boundary ⋉ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \ltimes \] \end{document} , move to state q₂, and we iteratively go right-to-left (–1) on the input string, outputting nothing until we reach the start boundary ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} . At around steps 11–12, we read the state boundary ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} , output the reduplicant boundary ∼, move to state q₃, and then read the input string again from left-to-right (+1). Between steps 16–17, we reach the end boundary ⋉ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \ltimes \] \end{document} , output nothing, and we finish the transduction in the final state q_f

Thus, total reduplication is a regular string-to-string function, requiring only the expressivity of a 2-way FST (Dolatian & Heinz 2018b; 2020).2

Total reduplication is a regular function where we copy the entire input string exactly once. Now consider partial reduplication as in Agta initial-CVC reduplication: takki→tak∼takki (ib). In partial reduplication, a given morphological construction specifies the maximal size of the partial reduplicant. Although a cross-linguistic maximum is unclear, most attested cases of partial reduplication impose a bound that can vary from 1 to around 5 segments, or one to two syllables (Rubino 2013; Inkelas & Downing 2015b). For pluralization in Agta, this bound seems to be 3.

It is immediately clear that partial reduplication is also a regular function. Just like total reduplication, partial reduplication generates exactly one extra copy of the input string. This copy is however a substring of the input string.

Figure 2 is a 2-way FST for partial reduplication with initial-CVC reduplication. The main difference between our 2-way FST for total (Figure 1) vs. partial reduplication (Figure 2) is the following. For total reduplication, the machine first reads and outputs the entire input string before returning to the start boundary ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} . But for partial reduplication, the machine outputs the first CVC substring and then returns to the start boundary ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} .

Table 3 illustrates a derivation using this 2-way FST for the mapping takki→tak∼takki. In steps 1–5, we output the first CVC substring (= the reduplicant). Steps 6–7 return to the start boundary ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} . Finally, steps 8–14 output the input string (= the base).

Note that the above machines are for prefixal partial reduplication. Suffixal partial reduplication can also be modeled with such machines and functions. The difference would be the choice of directionality: do we read left-to-right up until the first CVC, or do we read right-to-left up until the final CVC.

Thus, like total reduplication, partial reduplication is a regular function. Furthermore, the bound on the size of the reduplicant means all partial reduplication types belong to a more restricted subclass of regular functions called rational functions. Rational functions can describe copying a substring of bounded size. Given a string w, the process of generating a copy w → uw where u is a fixed-size substring of w is a rational function. Given a string w of size |w|, the output string is at most the size 2|w|. For initial-CVC reduplication, the size of the output string is exactly |w|+3.

Rational functions are far more restricted than regular functions. They can be described by 1-way FSTs, among other logical and algebraic characterizations (Filiot & Reynier 2016). 1-way FSTs are a common tool enough so that that the prefix ‘1-way’ is usually omitted in publications in NLP and computational linguistics.3 For this reason, most computational work describes partial reduplication using 1-way FSTs (Roark & Sproat 2007; Chandlee & Heinz 2012). This situates partial reduplication alongside most other attested morphological and phonological processes (Johnson 1972; Koskenniemi 1983; Ritchie 1992; Kaplan & Kay 1994; Beesley & Karttunen 2003; Roark & Sproat 2007; Rogers & Pullum 2011; Heinz & Idsardi 2013; Rogers et al. 2013; Chandlee 2014; 2017; Chandlee & Heinz 2018; Chandlee et al. 2018). To illustrate, Figure 3 is a 1-way FST for partial reduplication with initial-CV reduplication, with a simple alphabet Σ = {p, t, a}. The machine works by reading the initial CV substring, memorizing it, and outputting twice. The machine cannot go back and forth on the input, but only move rightward.

Because partial reduplication requires that the copied substring has a fixed size (such as 2 for initial-CV, or 3 for initial-CVC), then partial reduplication is a rational function. Since every rational function is by definition a regular function, we stick to categorizing partial reduplication as a ‘regular function’ in order to clarify the connection between partial and total reduplication.4

So far, we discussed only reduplicative patterns where there is exactly one new copy that is generated. In spoken natural languages, most attested cases of reduplication involve adding only one copy, whether partial or total. For example, in the Indonesian case of total reduplication (ia), the additional copy is used to mark plurality. In some natural languages, a single morphosyntactic feature can instead be expressed by generating multiple copies (ii), such as adding two copies to mark intensity in Taiwanese.

Such cases of triplication are less common but attested in spoken natural languages, both as total copying as above or partial copying (Rai & Winter 1997; Rai et al. 2005).5 Triplication is very widespread in sign languages (Pfau & Steinbach 2006). It is used for pluralization, reciprocals, and various types of aspectual modification (Wilbur 2005).

Computationally, triplication of the entire input string is no more complex than total reduplication. As mentioned, given a string w, the process of generating one extra copy w → ww is a regular function. Likewise, the process of generating 2 extra copies w → www is a separate but still regular function.

To illustrate, Figure 4 is a 2-way FST for triplication. This 2-way is larger than the one for total reduplication (Figure 1). The main difference is that we have an extra set of states q₄, q₅ that read the input string again for the third time in order to create an extra copy.

Table 4 illustrates a derivation using this 2-way FST for the hypothetical mapping buku→buku∼buku∼buku.

Although it may seem counter-intuitive, triplication is not more computationally complex than total reduplication. Informally, any function which generates n number of copies is regular as long the number of copies n is pre-determined and fixed.6 For triplication, the number of new copies (= 2) is still bounded for any particular process. In terms of output growth, triplication of a string w creates an output string of size 3|w|.

This is a crucial property for the computation of reduplicative morphology. If the function cannot predetermine the number of copies, i.e., we need to calculate and count how many copies to generate, then the function is not regular. For triplication, the relevant semantic feature is realized by a fixed number of multiple copies. However, there are few if any robust cases in spoken languages where a single feature (such as pluralization or continuativity) is realized by a variable number of copies without any difference in semantics, e.g., w → ww,www without a difference in meaning between ww and www. Recent corpus and elicitation data suggests that signers may variably mark plurals using two, three, or more copies in this way (van Boven 2021). Regardless, such a process is still a regular relation because there is a maximum bound. The difference between a function and a relation is that a function returns at most one output string, while a relation can return multiple, such as in the case of linguistic variation.

As mentioned, the key property defining regular functions is that their output length may be at most a linear growth on the input (potentially even just a constant), such as 2|w| for total reduplication, 3+|w| for CVC partial reduplication, and 3|w| for triplication. In this section, we discuss more expressive functions that go beyond linear growth rates. These are polyregular functions. Crucially, reduplication is weaker than such functions.

For polyregular functions, the size of the output string can grow polynomially with respect to the size of the input string |w|, i.e. O \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \mathcal{O} \] \end{document} (|w|ⁿ) (Bojańczyk et al. 2019; Lhote 2020). The polynomial growth property enables many equivalent characterizations of polyregular functions, in terms of logic, algebra, and automata (Bojanczyk 2022). With respect to automata, polyregular functions are exactly the functions that can be computed by augmenting a 2-way FST with a set of “pebbles”, an analogous mechanism to a stack where some number k of markers are dropped and picked up along the input while it is being read. These pebbles are used as a type of memory device so that the machine can hop back and forth on the input tape, and remember its previous positions. Such “pebble transducers” exactly compute the polyregular functions.7

A type of copying function that is properly polyregular is what we call input-specified copying. Here, the input contains a string of instruction symbols R that determine how many copies of w will be generated. For these functions there is a dependency between the number of instructions R and the number of output copies.8

To illustrate why such input-specified copying is not a regular function, we provide example 2-way FSTs that approximate a polyregular function where one or two reduplication morphemes are input-specified. We formulate such functions below.

First, consider Figure 5 which is a 2-way FST for doing total reduplication for up to one reduplication instruction R. The way the machine works is that, as we read left to right, if we see a symbol R, then we are told to go back to the start ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} of the input and create a copy. Table 5 illustrates a derivation using this 2-way FST.

The above FST is for reading an input string with exactly one instruction R. If we want to read an input string with one or two instructions, then we need a bigger FST. For example, Figure 6 is a 2-way FST for doing total reduplication for up to two reduplication morphemes.

Informally, if we read the first instruction R, then we go back to the beginning ⋊ \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \rtimes \] \end{document} , generate a copy of the input string, and then pass over the first R. If we see a second R, then we again go back to the beginning, generate a new copy of the input string, and then pass over the first two R’s. Table 6 illustrates a derivation using this 2-way FST.

While these 2-way FSTs can sufficiently compute these particular reduplication examples, it is easy to see why allowing any number of input-specified reduplicative instructions is impossible for a regular function. One would either have to have a separate 2-way transducer for each reduplication number, or have one transducer whose state size is equal to the number of possible reduplicative input R morphs. Since this number can be infinite, one would need an infinite number of transducers or a single transducer of infinite size.

The above function is thus not regular, but polyregular. As mentioned, this means the size of the output string grows at a polynomial rate of the input. For example, for an input string wRⁿ of input size |w|+|R| = |w|+n, the output string has a size n|w| where n is not a constant number like 2 for total reduplication or 3 for triplication. It is instead dependent by the number of R morphs in the input. For illustration and space, we only provide a growth-based description of polyregular functions and don’t illustrate with pebble FSTs (though see Bojanczyk (2022) for various descriptions).

Polyregular functions are a well-studied class, and provide a window into logically possible but naturally unattested types of reduplication. For example, one might imagine a type of input-specified copying where the number of reduplicants is based on the length of the input word, i.e. how many segments there are. Given a string w, the process of generating a copy w → w^|w| is not a regular function. This is because the number of reduplicants grows polynomially with the length of the input. For example, with an input string ‘abcd’ with a length of 4, the output string contains 4 copies of 4 segments each, for a total of 16 segments. A word with 5 segments would have 25 output segments, and so on, i.e. quadratic growth. Alternately, one might imagine a “partial reduplication” variant of the above where all possible prefixes of a word are copied and concatenated, i.e. for an input word ‘abcd’ the output would be ‘a ab abc abcd’. It is easy to see that this is also properly polyregular.

The takeaway from this section is that there is a definite upper bound on the generative capacity of individual reduplicative processes.9 Table 7 summarizes the generative capacity of reduplication types. Computationally, attested cases of partial and total reduplication are both regular functions, since they can both be modeled with 2-way FSTs, and partial reduplication is a restricted subclass (rational functions) that can be modeled with 1-way FSTs. Such statuses are constant regardless of the number of generated copies, meaning that triplication and variable numbers of copying are likewise regular.

Logically possible but unattested cases of reduplication inhabit a more expressive but natural extension of regular functions, namely polyregular functions. Studying classes of possible but unattested types of functions is important, because it allows a counterfactual in the presence of limited data. With this counterfactual, we can examine the expressivity of individual theories in a way that is well behaved but not restricted by just attested examples.

With these computational properties in place, the question now is how linguistic theories for reduplication lie with respect to this this regular/polyregular threshold. As we will show, theories which handle reduplication via direct transformations (functions) are regular. In contrast, theories that involve counting the number of reduplicative instructions are not regular but at least polyregular. A compromise between these two extremes of theories exists which is regular.

Since early seminal work on reduplication (Wilbur 1973; Moravcsik 1978), there have been many generative treatments of reduplication (Marantz 1982; McCarthy & Prince 1986; 1995; Steriade 1988; Raimy & Idsardi 1997; Raimy 2000; Struijke 2000; Inkelas & Zoll 2005; Kiparsky 2010). There are many overviews of developments in reduplication typology and theory (Hurch 2005; Urbanczyk 2007; 2011; Raimy 2011; Inkelas & Downing 2015a; b). Some of the most prominent theories include word-formation rules (Aronoff 1976), templatic reduplication (Marantz 1982), Base-Reduplicant Correspondence theory (BRCT: McCarthy & Prince 1995), and Precedence-Based Phonology (PBP: Raimy 2000).

However, most of these theories are not computationally explicit enough to clearly understand their generative capacity. A minority of theories like PBP do have explicit algorithms (Raimy 1999), and those are computationally very expressive (Dolatian & Raimy forthcoming).

In order to determine the generative capacity of these theories, we do two things. First, as a baseline, we focus on how these theories model the reduplication caused by a single morphosemantic feature (Table 7), not when multiple reduplicative processes are involved in generating a single word.10 Second, as a descriptive device, we classify these different theories of reduplication based on how reduplication is represented in the input: representational vs. non-representational. A theory is representational if it uses special symbols in the input to represent a reduplicative morph. A theory is non-representational if it does not utilize any such representations. We further divide representational theories into counting vs. non-counting theories.

Briefly, theories which create a dependence between the number of reduplicated copies and the number of input reduplicative morphs are not regular, but polyregular. Such theories are reducible to the polyregular input-specified copying functions from §2.5. Such theories explicitly count the number of reduplicative morphs, as a way to count the number of reduplication instructions. In contrast, theories which don’t do counting could be described with a regular function, assuming the theory’s other aspects can be regular too.11 Some of these non-counting are representational (Item-and-Arrangement) while some are not representational (Item-and-Process).

Non-representational theories include base-copying (Steriade 1988), word-formation rules (Aronoff 1976), and transformational rules (Carrier 1979; Lieber 1980). Here, the input undergoes either a special compounding construction or a readjustment rule. These theories are arguably item-and-process approaches to morphology (cf. Hockett 1942). In these theories, the process itself specifies how many copies to generate, whether one or two. Examples of total reduplication, triplication, and variable reduplication via rules are given below:

As explained in §2.4, generating a specific maximally bounded number of copies is regular since the output growth is linearly bounded. This means that if reduplication is implemented via a word-formation rule, then the theory is a regular function. It does not matter if the natural language consists of a large number of word-formation rules, each for generating a different number of copies (reduplication, triplication, quadruplication, etc.). As long as the set of word-formation rules is finite, then the finite union of these rules (and their regular transductions) is regular.

Additionally, for such regular theories, it is not obvious at all how we can create a word-formation rule for an input-specified copying function such as wRⁿ → wwⁿ. This is because such theories by definition don’t allow the input to have representational devices such as R, which would necessarily involve non-linear output growth.

In contrast to non-representational theories, representational theories of reduplication appear to be akin to item-and-arrangement style approaches. Here, the input must have a special symbol which triggers reduplication (see Table 8). Furthermore, based on our computational result, we further divide representational theories into counting-based vs. non-counting-based theories based on whether the input representation ‘counts’ the number of reduplicative morphs.

Some theories create a 1-to-1 correspondence between the number of reduplicative morphs and the number of copies to generate. This group of ‘counting theories’ include templatic reduplication (Marantz 1982; Kiparsky 2010; Saba Kirchner 2010; 2013; Paschen 2018) and Precedence-Based Phonology (PBP) (Raimy 2000; Papillon 2020). For example, to reduplicate the input kat into kat∼kat, templatic reduplication involves adding an empty prosodic word node in the input. This node is filled out in the output. Similarly, triplication involves adding two empty word nodes.12

Computationally, counting theories of reduplication are not regular, but polyregular. The input is examined for the number of reduplicative morphemes/morphs. The number of generated copies will depend on the number of these reduplicative morphs. The size of the output necessarily depends polynomially on the size of the input, and is reducible to the input-specified copying functions in Table 7, meaning it is properly polyregular. For example, we can use template reduplication to model a polyregular function as such as wRⁿ → wwⁿ. The trick is that the prosodic word nodes like ω are our reduplicative instructions R.

PBP is like templatic reduplication in this regard. PBP treats words as graphical structures. It assumes that the input to reduplication contains a special edge making the relation intransitive, a back-loop. These back-loops are reduplicative instructions. To generate triplication, PBP simply adds an additional back-loop as seen below.

For PBP specifically, Dolatian & Raimy (forthcoming) provide a proof that PBP is not regular. Going beyond their result, we can specifically say that any counting representational theories like PBP are polyregular functions which can be computed with polyregular transducers (Bojańczyk 2018).

As a caveat, it is true that any point in time a natural language will have a finite number of reduplicative processes, such as one construction for total reduplication (wR → ww) and another construction for triplication (wRR → www). If we assume that the language can create only at most some specific number of reduplicative instructions (such as 2), then the language’s reduplication system is regular, though in a way which trivializes the very concept of reduplicative instructions. But, the fact remains that any complete counting-theory of reduplication is supra-regular. This is because the theory is expressive enough to allow the language to innovate and add a new reduplicative construction which uses an extra number of reduplicative instructions (wRⁿ → wwⁿ).

Finally, the third group of theories are representational non-counting theories. This class is much smaller. It only includes some variants of Base-Reduplicant Correspondence Theory (BRCT, McCarthy & Prince 1995).

BRCT is couched within Optimality Theory (OT, Prince & Smolensky 2004) and it is a popular approach. Depending on the exact analysis, BRCT is either a counting or non-counting representational theory. For simple reduplication, the input consists of a string kat and a special symbol Red. The existence of Red triggers segment copying.

Although a BRCT analysis is straightforward for reduplication, to our knowledge there is no explicit BRCT treatment for triplication. In any case, a BRCT-based analysis for triplication could be either counting (vii(b)i) or non-counting (vii(b)ii). A counting analysis would posit two Red morphs for triplication. Here, the two Red symbols do not act as separate morphological constructions; the two symbols act as morphs which constitute a single grammatical construction. This analysis is similar to positing a circumfix as a combination of a prefix and suffix.

Hsiao (2011) sketches out a triplication analysis resembling a counting BRCT treatment. A counting BRCT analysis is polyregular by reduction to the input-specified copying function wRⁿ → wwⁿ. Essentially, such a theory in principle can allow an input with any number of reduplicative morphemes w+Redⁿ.

In contrast, a non-counting BRCT treatment for triplication (vii(b)ii) would posit a single Red symbol. This symbol is diacritically specified to generate two copies, not one. This analysis is suggested in Blevins (1996). A similar analysis is proposed in Zukoff (2017). Based off of a similar analysis by Zuraw (2002), Zukoff (2017) argues that the Red morpheme triggers a constraint Redup which then creates a coupling relationship among multiple copies in the output. His constraint is only exemplified for simple reduplication, but we speculate that it can easily be redefined to allow triplication.

Abstractly, a non-counting representational theory of reduplication is a regular function. The input is examined for the presence of a special symbol Red. The symbol must carry a label that tells the grammar how many copies to generate. A natural language can specify that a morpheme Red₁ maps to a single copy, while Red₂ maps to two copies. It can specify as many Red_x as logically possible. At any given time, the language will have a finite number of Red_x morphemes in its lexicon or morphological rules.

In effect, a non-counting version of BRCT is like forcing a regular approximation of a polyregular function. Given a string w and a single reduplicative morph Red, the regular function checks that if that reduplicative morph is actually the reduplicative morph Red₁, then it creates the word ww. If that morph is actually Red₂, then it creates the word www. At any point in time, the language’s morphology will have a finite set of types of Red morphemes, such as {Red₁,Red₂,… Red_x} for some constant x. Computationally, non-counting BRCT is a regular function that is a union of all possible mappings with these Red_x symbols. The result is a big 2-way FST.

Although counter-intuitive, such a theory is not polyregular but is regular. This theory cannot do a mapping of wRⁿ to wwⁿ where n is any possible integer. This is because for a specific language for a specific point of time, the function recognizes only a finite number of Red morphemes, not an unbounded number.

When a word contains multiple reduplicated copies, it’s common to find that the different copies belong to separate reduplicative processes. For example, a word can have multiple partial copies that designate different semantic features (Urbanczyk 1999; 2001; Fitzpatrick & Nevins 2004; Fitzpatrick 2006; Stonham 2007; Zimmermann 2021; Mellesmoen & Urbanczyk 2021). As long as the number of such partial reduplicants is bound, then the function is regular (in fact, rational).

Multiple reduplication is also found in total reduplication in Guébie (Sande 2017; 2021). One type of total reduplication is used to mark reciprocalization, abstractly as w → ww. A separate total reduplication process is used for nominalization, abstractly as w → ww. Each of these functions on their own is regular. When nominalization applies to the output of reciprocalization, we generate in total four copies: w → ww → wwww. The composition of these two regular functions is thus another regular function.

Much rarer are languages where the output can contain multiple copies such that each copy expresses the same semantic feature (called re-triplication in Friday-Otun 2021). For example in Tigre (Table 9), the syllable of the penultimate root consonant is reduplicated (underlined) to mark frequentativity (Rose 1997; 2003a; b). This partial reduplication can apply multiple times, with each generated copying adding an additional semantic level of frequency or attenuation.

In terms of a function, we can conceptualize the generation of the output with four copies dəga:ga:ga:gəm-a: in one of two ways: factorized (cyclic) and unfactorized (non-cyclic). The factorized approach would iteratively apply the same partial reduplication function f_cv four times, with each function f_cv adding a copy: dəgm-a: → dəga:gəm-a: → dəga:ga:gəm-a: → dəga:ga:ga:gəm-a:. The unfactorized approach is to generate the four copies in one single swoop as a single function f₄ which is specified to generate four copies: dəgm-a: → dəga:ga:ga:gəm-a:. Because this is partial reduplication and because the maximum number of copies is 4 (Rose 2003b: 124), both functions f_cv and f₄ would be rational functions.14

The Tigre example focuses on how the same feature F and its reduplicant can be repeated to add semantic nuances. The reduplicative pattern in Tigre is partial. There are other rare cases of natural language where the repeated reduplicative process is total reduplication. For example in Runyankore (Hyman 2020), frequentativity is marked by total reduplication of the root, abstractly as w → ww ‘to w a lot’. The root can reduplicate further and further to designate greater degrees of frequentativity: www*. The individual copies be segmentally identical or undergo some truncation. Each application of reduplication is regular. Besides Runyankore, another possible case is English contrastive reduplication (Ghomeshi et al. 2004).

For Runyankore, the computation depends on if a theory uses cyclicity, bounds on the number of copies, and how it represents the semantically-based input to reduplication. If factorized with cycles of the same function, then each cycle of a function would be regular. If we try to use a single collapsed function, then the computational expressivity depends on how many times a copy can be generated. If such a bound on the number of copies exists, then the finite composition of multiple total reduplication functions would be a single regular function. But if there is no bound, then regularity would depend on how the input string w looks like and how the mapping between semantic features F to the input works. If the input it treated as a word plus a sequence of identical frequentative features F, then this process is reduced to the polyregular input-specified copying: w Fⁿ → wwⁿ.

In sum, for repeated but bounded application of a reduplicative process, this process is rational for generating partial copies, regular for total copies. However, if there is no bound on the number of total copies, then we may be entering polyregular computation. The mathematical perspective shows that any answer to this question depends on a unified theory of how repeated reduplication is modeled in the input to the morphophonological derivation, meaning it should be a key focus of future research in reduplication.

So far, we discussed how individual theories of reduplication are regular or polyregular. Individual reduplicative functions are regular, while the interaction among an unbounded number of reduplication functions might not be regular. Given this state of affairs, one can ask: Do regular theories then undergenerate, and do we now need polyregular theories The answer is somewhere between ‘no’ and ‘unclear’.

The main problem behind multiple reduplication is how we encode concepts like cyclicity and semantic features, and how composition can be integrated into our formal model of reduplication.

For the Guébie data, the two total reduplication functions are individually regular. The composition of a bounded, finite sequence of regular functions is at most regular. Thus the composition of these two regular reduplicative processes is thus also regular. Thus a regular theory can model the data.

But now consider Runyankore. Total reduplication on its own is still regular. But the language allows the unbounded application of the same regular function. But the composition of an unbounded sequence can be non-regular. In order to handle the data, we need to be more exact about how the morphology-phonology interface is formalized. One option is to combine a regular theory of reduplication (like word-formation rules) with cyclicity: w → ww → www → … → wwⁿ. Another option is to combine a polyregular theory with a semantically-enriched input representation: w+Fⁿ → wwⁿ.

The choice between the two approaches cannot be settled based on just the empirical data behind reduplication. Instead, the choice is up to the analyst on how they conceptualize the morphology-phonology interface: with cyclicity or with semantically-enriched inputs?

One takeaway from this and related work (Dolatian & Heinz 2020; Wang 2021a) is that making copies is computationally simpler than recognizing copies. Computational perspectives on reduplication, and copying more generally, have centered around the complexity of the “copy language”, which is the set of totally reduplicated strings: {ww | w ∈ Σ*}, which is not a regular language since there is no bound on the reduplicant size (Culy 1985), nor is it a context-free language for the same reason. Instead, more advanced types of acceptors are needed, such as context-sensitive grammars (Seki et al. 1991; Albro 2000; 2005; Stabler 2004; Clark & Yoshinaka 2014), a combination of an FSA with some queue mechanism (Gazdar & Pullum 1985; Wang 2021a; b), or other elaborate extensions (Manaster-Ramer 1986; Savitch 1989). However, when viewed as a transformation f(w) = ww, this copying function is a regular function.

If we step back and take a broader perspective, it is useful to compare what we know about functions which map strings to strings with what we know about functions which map real numbers to real numbers. The latter has been informed by hundreds of years of mathematical study and we are quite conversant in different classes of functions over the reals (linear, polynomial, trigonometric, logarithmic, etc.) and many of the properties of such functions. However, our knowledge of functions over strings is still, relatively speaking, in an early stage. It is our view that it behooves us – especially for those with a goal to better understand natural language – to better understand the different kinds of string-to-string functions and their properties. This paper takes a small step in that direction.

One possible hypothesis from this paper is that, because reduplication on its own is computationally regular, then psychologically real models of reduplication should likewise be computationally regular. We are agnostic over this hypothesis, but we discuss it.

This hypothesis is a significant issue for BRCT. As explained, proposals on reduplication in BRCT are not specified enough to make a final determination of their computational power. There is wiggle room over whether the Red symbol acts as a single diacritic for reduplication processes (thus being regular) or as a sequence of instructions for each copy (thus being polyregular). This choice will fundamentally affect the models. The regular approach can be considered an Item-and-Process formulation. Such a formulation seems unlikely to be developed within BRCT because of the dependence on correspondence theory to compute the content of the Red morph. If the evaluation of the Red morph becomes a process, then either all of correspondence theory becomes a process or reduplication as a phenomenon is removed from phonology. Triplication as a phenomenon also lacks an explicit analysis in BRCT models. We are unaware of any active research on these topics.

As for templatic reduplication, all current models (McCarthy et al. 2012; Zimmermann 2013) are Item-and-Arrangement models that inherit the basic architecture from Marantz (1982). Empty prosodic structure is added and then filled by copying melodic structure. They would all still require polyregular computation. Again, there is an alternative possibility that reduplication is a process that is diacritically triggered by these empty nodes. But then this process alternative would nullify the main thrust of this line of research.

For the representational counting theories like PBP or templatic copying, the entire computation is polyregular. However, within the literature, these theories do consist of multiple derivational stages. To illustrate, consider a hypothetical example of initial-CV reduplication: pat→pa∼pat in Table 10. Assume a templatic approach to reduplication (Marantz 1982).

The input contains the segments connected to CV-timing slots. A reduplicative CV template is affixed; this template acts as the reduplicative instruction. The CV template is associated with the initial segments. This creates multiple crossing corresponding relations. In the last stage, these crossing relations are removed by copying the segments. This second stage has been called tier conflation (McCarthy 1986; Mester 1986; McCarthy & Prince 1995) for the templatic copying theories, and serialization or linearization for PBP (Raimy 1999).

Over string-to-string functions, this second stage of tier conflation is necessary in order to generate a string. Without tier conflation, there would not be a copying process at all. It is an open question if the polyregular computation can be avoided if these representational theories were instead treated as graph-to-graph functions, without any tier conflation.

This option without tier-conflation is an interesting option for PBP. As explained before, PBP uses graphical structures. It proposes that precedence structure in phonology is a directed graph with reduplication being a case that demonstrates that graphs in human language can have cycles. Papillon (2020) elaborates the possible graphs that would be involved in phonology and morphology. With tier conflation, converting these graphs is not MSO-definable (Dolatian & Raimy forthcoming). But alternatively without tier conflation, processing these graphical structures is similar to topological sorting (Höpfner 2011) with parallel edges and cycles (Papillon 2020; 2021), as opposed to using paths (Idsardi & Raimy 2013).

This paper tried to survey common or previously common approaches in modeling reduplication. We tried to catalog as many theories as we could in terms of whether the theory uses regular or polyregular computation. One theory that we haven’t discussed yet is Morphological Doubling Theory (MDT) (Inkelas & Zoll 2005). Unfortunately, current formulations of the theory are too vague to computationally formalize.

The main idea behind MDT is that reduplication is not a transformation like w+Red → ww. Instead, reduplication is about creating a compound of two strings, such that the two strings are identical (total reduplication) or near-identical (partial reduplication). For our computational purposes, the problem with this approach is that it reduces reduplication to recognizing a string language, and not a string-to-string function or transformation.

In our reading of Inkelas & Zoll (2005), we couldn’t find unambiguous examples of how MDT would model the transformation from an unreduplicated string w to a reduplicated string ww. The theory instead implies that the lexicon or the morphology of a natural language has something like a template or construction whereby words like ww are licit and have a specific semantic interpretation when compared to w. From this reading, MDT is not a theory about string-to-string mappings, but of string languages.15 This implicitness about MDT has been somewhat noticed in the previous literature (cf. Raimy 2006: 484ff). Thus, we a priori cannot apply concepts like ‘regular functions’ or ‘polyregular functions’ to MDT in the way that we did for others, simply because MDT is not defined as a transformation in the first place. Until such a theory is created, we cannot computationally compare MDT against the other theories, only against the prior work on reduplication as a language, as overviewed in §5.1.

The formalization of reduplication theories raises the issue of how theories represent the idea of not only copying segments, but also the sequencing of repeated segments within a reduplicative construction. These issues have analogs to the role of sequencing and repetition in cognition (Endress et al. 2007; Moreton et al. 2021).

Cognitive neuroscience has provided evidence for the role that the hippocampus plays in navigation and episodic memory (Hasselmo 1999). Buzsáki & Tingley (2018) argue that the hippocampus is a generalized sequence generator. Words (or more properly morphemes) can be conceived of as sequences of phonological categories, thus some questions and findings from cognitive neuroscience can be relevant to our investigation of the nature of reduplication. Hasselmo (2011) identifies the question of how to deal with forks in overlapping sequences through activation levels associated with goal states. Hasselmo (2011) addresses loops in paths by proposing arc length cells that distinguish between the length of a sequence with or without the loop part. Analogously, these arc length cells (or the time cell equivalent: MacDonald & Tonegawa (2021)) would act as a counter for our polyregular models of reduplication. Coded trajectories in the hippocampus are more graph-like than string-like, and consequently further investigation into graph-to-graph functions seems warranted.

An interesting possibility is that reduplication is special when compared to morphology and phonology because it reflects the use of cognition-general mechanisms for sequences. Endress et al. (2007) argues that learning repeated sequences (i.e. reduplication) is different from learning ordinal sequences in an artificial grammar. If the hippocampus provides the general mechanism for sequences (Buzsáki & Tingley 2018) then recognizing and learning repetition could be a fundamental cognitive function and then learning additional relations among sequences, such as the ratios among notes in the Endress et al. (2007) study, is based on an additional elaborated learning mechanism.