Efficient Generation in Primitive Optimality Theory

Jason EisnerACL 1997 · OpenReview

Abstract

This paper introduces Primitive Optimality Theory (OTP), a linguistically motivated formalization of Optimality Theory (OT). OTP restricts the class of autosegmental representations and defines a universal generator (Gen) alongside two simple families of permissible constraints: implication and clash. While the generation problem is shown to be NP-complete, the paper demonstrates that finite-state methods, specifically "factored automata," can achieve a 100-fold speedup in typical phonological generation tasks, making the approach computationally feasible.

Introduction

In linguistic theory, Optimality Theory (OT) posits that surface forms (pronunciations) emerge from a competition among candidates filtered through a ranked hierarchy of constraints. Despite its theoretical success, OT has faced challenges regarding formal rigor and computational complexity. Many standard OT models rely on "Generalized Alignment" constraints that are too powerful for efficient finite-state implementation, often leading to state-space explosions.

Jason Eisner proposes Primitive Optimality Theory (OTP) to address these issues. OTP provides a mathematically precise version of OT that is restricted enough to be implemented using finite-state automata (FSA) while remaining expressive enough to capture the vast majority of phonological phenomena.

The OTP Framework

Representations as Timelines

A key innovation in OTP is the shift from simple character strings to a "constituent timeline." In this model, phonological events—such as voicing, nasality, or syllable structure—are represented as intervals on an infinitely divisible line. Each interval has a discrete start and end point, allowing for overlapping features across different tiers.

Autosegmental representations mapped to a constituent timeline.

Primitive Constraints and FSAs

OTP restricts the set of possible constraints to two "primitive" families:

  1. Implication ($\alpha \to \beta$): If event $\alpha$ occurs, event $\beta$ must also occur simultaneously.
  2. Clash ($\alpha \perp \beta$): Event $\alpha$ and event $\beta$ are prohibited from occurring at the same time.

These constraints are naturally represented as small FSAs. The generation process is then treated as a shortest-path problem in a weighted graph, where each constraint FSA assigns penalties (weights) to paths that violate the rules.

A finite-state automaton representing a primitive constraint on the timeline.

Computational Efficiency and Factored Automata

The author proves that finding the optimal surface form in OTP is NP-complete (via reduction from the Hamilton Path problem). However, this worst-case complexity does not reflect typical linguistic performance. To handle the "state-space explosion" that occurs when intersecting many constraint FSAs, Eisner introduces factored automata.

Instead of pre-computing a single massive automaton representing the entire grammar, the system maintains separate "factored" machines. By using a technique called delayed intersection, the algorithm only combines rules when a constraint specifically mentions a particular tier. This allows for early pruning of the search space, significantly reducing memory and time requirements.

Results and Evaluation

The approach was evaluated on a moderate-sized grammar fragment and a stress typology system consisting of 26 constraints. The results were striking:

  • 100-Fold Speedup: Using factored automata and delayed intersection, the time required to discover a stress pattern dropped from 3.5 minutes to just 2.2 seconds on 1990s-era hardware (167MHz UltraSPARC).
  • Generative Power: Despite its restrictions, OTP is capable of capturing virtually all analyses found in the standard phonological OT literature.
  • Formal Boundaries: The paper provides a formal proof that Generalized Alignment is not finite-state, establishing a clear boundary for computationally "safe" linguistic theories.

Conclusion

OTP offers a bridge between abstract linguistic theory and practical computational implementation. While the underlying generation problem is NP-hard, the structured nature of human language allows for highly efficient optimization. Future work remains in areas like reduplication, which challenges the finite-state framework, and the application of OTP to unsupervised learning of phonological grammars.

Summary updated

Abstract

This paper introduces primitive Optimality Theory (OTP), a linguistically motivated formalization of OT. OTP specifies the class of autosegmental representations, the universal generator Gen, and the two simple families of permissible constraints. In contrast to less restricted theories using Generalized Alignment, OTP's optimal surface forms can be generated with finite-state methods adapted from (Ellison, 1994). Unfortunately these methods take time exponential on the size of the grammar. Indeed the generation problem is shown NP-complete in this sense. However, techniques are discussed for making Ellison's approach fast in the typical case, including a simple trick that alone provides a 100-fold speedup on a grammar fragment of moderate size. One avenue for future improvements is a new finite-state notion, "factored automata," where regular languages are represented compactly via formal intersections ∩ki=1Ai of FSAs.
BibTeX
@inproceedings{eisner1997efficient,
  author = {Jason Eisner},
  title = {{Efficient Generation in Primitive Optimality Theory}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1997},
  url = {https://openreview.net/forum?id=BJWPJ2lO-r},
}
Figure