Introduction: The Computational Asymmetry of OT
In linguistics, Optimality Theory (OT) provides a framework for understanding how speakers select the most "optimal" surface form (pronunciation) for an underlying mental representation. This selection process involves evaluating a set of candidates against a hierarchy of ranked constraints. While the computational properties of production (mapping an input to an output) are well-understood and can be modeled using finite-state transducers (FSTs), the inverse process—comprehension (mapping an output back to its possible inputs)—presents a significant challenge.
The Problem: The "Counting Trap"
The primary hurdle in modeling comprehension within classical OT is the reliance on global violation counting. For instance, a constraint like NoCODA might penalize a candidate based on the total number of codas it contains. Because finite-state automata have a finite number of states, they cannot track an arbitrary number of violations across an infinitely long string.
Jason Eisner demonstrates that this global counting can lead to "non-regular" sets of possible inputs. If a comprehension system must find all inputs that could have produced a specific output, and the grammar relies on comparing total counts (similar to the non-regular language $a^n b^n$), the resulting set of inputs may exceed the power of finite-state tools. This makes standard FST-based methods inapplicable to classical OT comprehension.
Methodology: A Unified Algebraic Framework
To resolve this, the paper proposes a General Presentation of OT that treats all components—underlying forms, surface forms, and candidates—as strings or regular relations. The core of this framework is the Harmony Ordering ($\\succ$), a mathematical relation that determines which candidate is "better" than another.
Eisner introduces a generalized optimality operator ($\\circ\\circ_H$) that combines candidate sets with constraints and harmony orderings. The central theorem of the paper proves that if the harmony ordering itself is a regular relation, the entire OT grammar can be compiled into a single FST. Once compiled, comprehension becomes a simple matter of inverting the transducer.
Key Insights: Directionality vs. Global Counting
The solution to the "counting trap" lies in moving from global integers to more "local" evaluation methods, such as Directional OT. In this approach, violations are compared from left-to-right (or right-to-left) rather than being summed into a single total.
As shown in Figure 3, classical OT (tableau c) evaluates candidates based on the total number of violations (e.g., ** vs ***!). In contrast, directional OT (tableau d) evaluates violations at specific positions ($\\sigma_1, \\sigma_2, \\dots$). This positional evaluation is a regular relation, making it computationally efficient and avoiding linguistic anomalies like "majority rule" effects—patterns where a language chooses a form simply because it has fewer total violations, even if those violations are distributed in ways never seen in human speech.
Key Results and Implications
The paper provides two major contributions:
- Formal Proof of Non-Regularity: A rigorous proof that classical OT can generate non-regular comprehension sets, necessitating a shift in formalism for computational tractability.
- The Compilation Theorem: A proof that any OT grammar with a regular harmony ordering can be compiled into an FST. This unifies various "flavors" of OT (Inviolable, Binary, 3-bounded, and Directional) into a single algebraic notation.
Furthermore, this framework simplifies the implementation of Directional OT, replacing complex automaton constructions with transparent regular expressions.
Conclusion
By shifting the focus from global violation counts to local, directional comparisons, Eisner provides a way to bring OT comprehension into the realm of finite-state processing. This unified framework not only solves a long-standing computational problem but also aligns more closely with observed linguistic phenomena. These finite-state representations offer a promising path forward for developing realistic learning algorithms that model how humans acquire complex phonological systems.
Summary updated