Paper

Efficient universal generation in a fragment of Optimality Theory

---

Abstract

Various work in computational phonology has studied the computational properties of Optimality Theory. Some algorithms exist for the universal generation problem, including those of Ellison and Tesar, but their domain of applicability is poorly understood. I propose and study a concrete `minimal' fragment of finite-state Optimality Theory. I show that the universal generation problem for it is efficiently solvable by improving Ellison's Algorithm, demonstrate that it has been implicitly used in the literature,  and discuss its limitations. The minimal fragment is a natural and foundational step towards a computationally tractable general formalism for phonological analysis.

Keywords: Optimality Theory, computational efficiency, finite-state transducer

How to Cite:

Siewert, P. K., (2026) “Efficient universal generation in a fragment of Optimality Theory”, Society for Computation in Linguistics 9(1). doi: https://doi.org/10.7275/scil.4019