Bounded and unbounded copying

Can an FST handle reduplication? The answer depends on how much material must be copied. Copying a fixed amount and copying an arbitrarily long stem have different formal properties. We will call this the copying bound distinction.

Bounded copying

Suppose a process copies at most the first two segments of a stem. An FST needs only finitely many states to remember those segments and emit them at the appropriate point. The same is true for any fixed copying bound.

To see the construction, let the bound be $k$ over a finite alphabet $\Sigma$. Before the copy site, give the transducer one state $q_u$ for every string $u\in\Sigma^{\leq k}$ that it might need to remember. There are only

\[ 1+|\Sigma|+|\Sigma|^2+\cdots+|\Sigma|^k \]

such strings. Reading a segment extends the stored $u$ until the bound is reached. At the copy site, a finite path from $q_u$ emits the symbols of that particular $u$. The number of states grows with $k$, but it does not grow with the length of an input stem. Thus, every fixed bound gives a finite transducer.

Many partial reduplication processes can be analyzed in this way. Once the size and location of the copied material are bounded, the map may be subsequential or otherwise finite state, depending on the representation and on how the copy site is located (Chandlee 2017).

So the fact that a description uses the word copy is not enough to diagnose nonregularity. What matters is whether the amount of information that must be retained is bounded independently of the input length.

Total reduplication

Unbounded total reduplication maps an arbitrary nonempty string $w$ to two copies of that string. The map below is a formal idealization of productive total reduplication, where the relevant stem length is not fixed in advance:

\[f_{\text{total-red}}(w)=ww.\]

Its graph is the relation

\[R_{\text{total-red}}=\{\langle w,ww\rangle\mid w\in\Sigma^+\}.\]

We will prove that this relation is not rational. Recall that the output projection of every rational relation is a regular language. The output projection here is the copy language

\[\pi_2(R_{\text{total-red}})=\{ww\mid w\in\Sigma^+\}.\]

We first verify that this language is not regular. Assume for contradiction that $L_{copy}$ is regular, and intersect it with the regular language

\[K=a^*ba^*b.\]

A string in $L_{copy}\cap K$ is a doubled string with exactly two copies of $b$. Each half must thus contain one $b$. Since the string also has the form $a^iba^jb$, its two halves are identical only when $i=j$. Hence,

\[ L_{copy}\cap K=\{a^nba^nb\mid n\geq0\}. \]

If $L_{copy}$ were regular, closure under intersection would make this language regular as well. Let $p$ be its proposed pumping length and choose

\[w=a^pba^pb.\]

For every permitted decomposition $w=xyz$, the nonempty $y$ lies inside the first block of $a$s because $|xy|\leq p$. Thus, $y=a^k$ for some $k>0$. Pumping down gives

\[xz=a^{p-k}ba^pb,\]

whose two $a$ blocks have different lengths. This string is not in the intersection language, contradicting the pumping lemma. Thus, $L_{copy}$ is not regular.

Now return to the transduction. If $R_{\text{total-red}}$ were rational, its output projection would be regular. Its output projection is $L_{copy}$, which we have just shown to be nonregular. Thus, $R_{\text{total-red}}$ is not rational, and no FST can compute unrestricted total reduplication.

The copy language is not context-free either. Moving from FSAs to context-free grammars will not make unrestricted copying available. More powerful formalisms—such as the multiple context-free grammars introduced later in the course—can generate it.

Culy gives a related linguistic lower-bound argument for Bambara (Culy 1985). The argument treats a lexical construction of the form N o N as requiring the same noun form in both positions. It combines this identity requirement with two productive agentive formations, filɛ-la and nyini-la, which can apply recursively and contain the transitive verbs filɛ and nyini followed by the suffix la. A regular filter then isolates a language of the form $\{a^m b^n a^m b^n\mid m,n\geq1\}$, which is not context-free. This does not mean that every reduplicative construction has the full power of the abstract copy language. The lower bound depends on these constructions being lexical and productive without a fixed depth bound.

Question

Why can an FST copy a two-segment prefix but not an arbitrary stem?

Answer

There are only finitely many two-segment prefixes over a finite alphabet, so the states can encode which prefix was seen. The number of possible stems grows without bound. Remembering an arbitrary stem would require an unbounded number of distinct memory states.

What the result does and does not show

The result separates two claims. First, many attested affixation and bounded-copying maps require less than the full power of rational relations (Chandlee 2017). Second, unrestricted total reduplication exceeds that power. Culy’s Bambara result similarly depends on treating the N o N construction as lexical and the two agentive formations as productive without a depth bound (Culy 1985). Culy notes that long forms become awkward, even though his informants accepted the relevant examples. And the proof supplies only a lower bound: it shows that the vocabulary is not context-free, but it does not determine an upper bound on its complexity. It does not follow that every linguistic analysis described as total reduplication must use a non-finite-state mechanism. A finite lexicon, a bounded stem length, or a richer representation may change the formal problem.

The next module introduces context-free grammars to model a different property of morphology: hierarchical composition. That hierarchy is needed to distinguish structures such as $[\text{un}[\text{lock-able}]]$ and $[[\text{un-lock}]\text{-able}]$, even when no copying is involved.

References

Chandlee, Jane. 2017. “Computational Locality in Morphological Maps.” Morphology 27 (4): 599–641. https://doi.org/10.1007/s11525-017-9316-9.

Culy, Christopher. 1985. “The Complexity of the Vocabulary of Bambara.” Linguistics and Philosophy 8 (3): 345–51. https://doi.org/10.1007/BF00630918.

--- title: Bounded and unbounded copying bibliography: ../../references.bib --- Can an FST handle reduplication? The answer depends on how much material must be copied. Copying a fixed amount and copying an arbitrarily long stem have different formal properties. We will call this the **copying bound distinction**. ## Bounded copying Suppose a process copies at most the first two segments of a stem. An FST needs only finitely many states to remember those segments and emit them at the appropriate point. The same is true for any fixed copying bound. To see the construction, let the bound be $k$ over a finite alphabet $\Sigma$. Before the copy site, give the transducer one state $q_u$ for every string $u\in\Sigma^{\leq k}$ that it might need to remember. There are only $$ 1+|\Sigma|+|\Sigma|^2+\cdots+|\Sigma|^k $$ such strings. Reading a segment extends the stored $u$ until the bound is reached. At the copy site, a finite path from $q_u$ emits the symbols of that particular $u$. The number of states grows with $k$, but it does not grow with the length of an input stem. Thus, every fixed bound gives a finite transducer. Many partial reduplication processes can be analyzed in this way. Once the size and location of the copied material are bounded, the map may be subsequential or otherwise finite state, depending on the representation and on how the copy site is located [@Chandlee2017]. So the fact that a description uses the word *copy* is not enough to diagnose nonregularity. What matters is whether the amount of information that must be retained is bounded independently of the input length. ## Total reduplication Unbounded total reduplication maps an arbitrary nonempty string $w$ to two copies of that string. The map below is a formal idealization of productive total reduplication, where the relevant stem length is not fixed in advance: $$f_{\text{total-red}}(w)=ww.$$ Its graph is the relation $$R_{\text{total-red}}=\{\langle w,ww\rangle\mid w\in\Sigma^+\}.$$ We will prove that this relation is not rational. Recall that the output projection of every rational relation is a regular language. The output projection here is the **copy language** $$\pi_2(R_{\text{total-red}})=\{ww\mid w\in\Sigma^+\}.$$ We first verify that this language is not regular. Assume for contradiction that $L_{copy}$ is regular, and intersect it with the regular language $$K=a^*ba^*b.$$ A string in $L_{copy}\cap K$ is a doubled string with exactly two copies of $b$. Each half must thus contain one $b$. Since the string also has the form $a^iba^jb$, its two halves are identical only when $i=j$. Hence, $$ L_{copy}\cap K=\{a^nba^nb\mid n\geq0\}. $$ If $L_{copy}$ were regular, closure under intersection would make this language regular as well. Let $p$ be its proposed pumping length and choose $$w=a^pba^pb.$$ For every permitted decomposition $w=xyz$, the nonempty $y$ lies inside the first block of $a$s because $|xy|\leq p$. Thus, $y=a^k$ for some $k>0$. Pumping down gives $$xz=a^{p-k}ba^pb,$$ whose two $a$ blocks have different lengths. This string is not in the intersection language, contradicting the pumping lemma. Thus, $L_{copy}$ is not regular. Now return to the transduction. If $R_{\text{total-red}}$ were rational, its output projection would be regular. Its output projection is $L_{copy}$, which we have just shown to be nonregular. Thus, $R_{\text{total-red}}$ is not rational, and no FST can compute unrestricted total reduplication. The copy language is not context-free either. Moving from FSAs to context-free grammars will not make unrestricted copying available. More powerful formalisms—such as the multiple context-free grammars introduced later in the course—can generate it. Culy gives a related linguistic lower-bound argument for Bambara [@culy_complexity_1985]. The argument treats a lexical construction of the form `N o N` as requiring the same noun form in both positions. It combines this identity requirement with two productive agentive formations, `filɛ-la` and `nyini-la`, which can apply recursively and contain the transitive verbs `filɛ` and `nyini` followed by the suffix `la`. A regular filter then isolates a language of the form $\{a^m b^n a^m b^n\mid m,n\geq1\}$, which is not context-free. This does not mean that every reduplicative construction has the full power of the abstract copy language. The lower bound depends on these constructions being lexical and productive without a fixed depth bound. ::: {.callout-caution} ## Question Why can an FST copy a two-segment prefix but not an arbitrary stem? ::: ::: {.callout-tip collapse=true} ## Answer There are only finitely many two-segment prefixes over a finite alphabet, so the states can encode which prefix was seen. The number of possible stems grows without bound. Remembering an arbitrary stem would require an unbounded number of distinct memory states. ::: ## What the result does and does not show The result separates two claims. First, many attested affixation and bounded-copying maps require less than the full power of rational relations [@Chandlee2017]. Second, unrestricted total reduplication exceeds that power. Culy's Bambara result similarly depends on treating the `N o N` construction as lexical and the two agentive formations as productive without a depth bound [@culy_complexity_1985]. Culy notes that long forms become awkward, even though his informants accepted the relevant examples. And the proof supplies only a lower bound: it shows that the vocabulary is not context-free, but it does not determine an upper bound on its complexity. It does not follow that every linguistic analysis described as total reduplication must use a non-finite-state mechanism. A finite lexicon, a bounded stem length, or a richer representation may change the formal problem. The next module introduces context-free grammars to model a different property of morphology: hierarchical composition. That hierarchy is needed to distinguish structures such as $[\text{un}[\text{lock-able}]]$ and $[[\text{un-lock}]\text{-able}]$, even when no copying is involved.