Recognizing Reduplicated Forms: Finite-State Buffered Machines

Yang WangACL 2021

TL;DR

This paper introduces a novel computational model, the Finite-State Buffered Machine (FSBM), designed to formally capture the linguistic phenomenon of reduplication (word or syllable repetition) within natural languages. By extending finite-state automata with a queue-like buffer, FSBMs can recognize languages with adjacent identical substrings, addressing a gap in formal language theory that previously struggled to model this common linguistic pattern without over-generating unattested structures like string reversals.

What Problem Does This Paper Address?

Formal language theory provides a hierarchy of computational models to describe the complexity of linguistic structures. However, the standard Chomsky Hierarchy doesn't perfectly align with linguistic reality. Specifically, phenomena like unbounded reduplication, where a part of a word is copied to form a new word (e.g., "midi-midi" for "lots of little ones" in Dyirbal), pose a challenge. While context-free grammars can handle some dependencies, unrestricted reduplication requires more power than context-free languages, leading to models that can also generate ungrammatical patterns like string reversals (e.g., "midi-idim"). Existing approaches often either lack the power to model unbounded copying or over-generate. This paper aims to bridge this gap by proposing a model that can capture reduplication accurately without including unattested linguistic patterns.

Methods

The core contribution is the introduction of the Finite-State Buffered Machine (FSBM). An FSBM is essentially a finite-state automaton augmented with an unbounded, queue-like buffer. This buffer allows the machine to store a portion of the input string temporarily. The machine operates in three modes:

  • Normal (N) mode: Functions like a standard finite-state automaton.
  • Buffering (B) mode: Reads input symbols and copies them into the buffer.
  • Emptying (E) mode: Compares symbols from the buffer with the input string to check for identity.

Crucially, the buffer is queue-like (first-in, first-out), and specific restrictions on mode transitions (e.g., needing to enter buffering before emptying) are designed to prevent the generation of string reversals and other non-reduplicative patterns. The paper also defines "complete-path FSBMs" which ensure that all possible computational paths adhere to a specific ordering of G (buffering) and H (emptying) states, guaranteeing that the copying mechanism is properly utilized.

Datasets

Not discussed in the paper. The paper focuses on formal language theory and the computational modeling of linguistic phenomena, rather than empirical data analysis or training on specific corpora. Examples are drawn from linguistic literature to illustrate the concepts.

Key Insights and Ideas

  • Bridging the gap: FSBMs offer a formal mechanism to capture reduplication, a common linguistic process, without over-generating unattested structures like string reversals.
  • The power of a queue: The queue-like nature of the buffer, combined with specific mode transitions, is key to restricting the machine's power to only recognize adjacent identical copies, thus excluding string reversals.
  • Sub-regularity and beyond: The work contributes to the ongoing effort to characterize sub-regular languages and their extensions, which are believed to better model natural language phonology and morphology than purely context-free or context-sensitive grammars.
  • Linguistic relevance: The proposed model is motivated by typological evidence of reduplication in natural languages and aims to provide a more accurate computational characterization than previous formalisms.

Key Results

The paper formally defines FSBMs and demonstrates their ability to recognize languages involving total reduplication (e.g., $L_{ww} = \{ww | w \in \Sigma^*\}$) and partial reduplication (e.g., modeling Agta CVC reduplication). It also shows that complete-path FSBMs are closed under intersection with regular languages, meaning that phonotactic constraints (modeled by FSAs) can be combined with reduplication recognition without increasing the computational power beyond that of FSBMs.

Limitations and Future Work

  • Local Reduplication: Current FSBMs are limited to capturing local reduplication with two adjacent, completely identical copies. They cannot handle non-local reduplication or multiple reduplication.
  • Non-Identical Copies: The current model strictly requires identical copies. The authors suggest that modifications could allow for recognizing non-identical copies by introducing a function to map symbols, potentially enabling the recognition of languages like $\{a^n b^n | n \in \mathbb{N}\}$.
  • Inverse Homomorphism: The paper conjectures that FSBM-recognizable languages are not closed under inverse alphabetic homomorphisms, suggesting a limitation in their expressive power for certain types of linguistic analysis.
  • Transducers: The authors propose extending FSBMs to finite state buffered transducers (FSBTs) to handle morphological analysis questions like $ww \rightarrow w$.
  • Primitive Optimality Theory: Applying FSBMs to models of Primitive Optimality Theory is suggested as a future research direction.

Summary updated

BibTeX
@inproceedings{wang2021recognizing,
  author = {Yang Wang},
  title = {{Recognizing Reduplicated Forms: Finite-State Buffered Machines}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure