Elamur Research⌕
☰
home / papers / 2026 / Efficient universal generation in a fragment of Optimality Theory

Efficient universal generation in a fragment of Optimality Theory

Summary

This paper addresses the universal generation problem in Optimality Theory (OT): computing a grammar's output from its constraint ranking. For several OT formalisms this problem is NP-hard, and the conditions under which existing algorithms by Ellison and Tesar work were unclear. The author defines a deliberately restricted variant of finite-state OT, the "minimal OT fragment" (mOT). It uses string-based candidates with correspondence to the underlying form, substring markedness constraints (optionally using phonological sets such as sibilants or plosives), and faithfulness constraints like Ident, Max and Dep. The paper improves Ellison's Algorithm, which applies Dijkstra-style shortest-path search over a product "combined evaluator" transducer, by adding a precomputation step. This yields a compact transducer that evaluates all constraints together, making generation provably efficient. mOT turns out to cover many standard segmental analyses, and the paper suggests it is implicitly used in prior work. The result matters because it is the first positive tractability result for OT since Tesar's work, and it offers a foundation for building richer formalisms that remain computationally tractable.

Key points

  • mOT puts avoiding computational intractability ahead of avoiding overgeneration. The author argues overgeneration can be fixed later by restricting the allowed grammars, as was done in Lexical Functional Grammar.
  • The algorithm extends Ellison's (1994) finite-state method. It finds optimal candidates by lexicographically minimising harmony vectors, then prunes non-optimal edges to obtain an automaton of all optimal outputs.
  • The method incorporates the Aho–Corasick Algorithm and properly subsumes Tesar's Algorithm (1995, 1996), though the two procedures are nearly identical.
  • As a case study, the Hixkaryana stress analysis from Kager (1999) is expressed in mOT using syllable-boundary and word-bracket symbols. A possible extension to context-free (tree-like) prosodic structure would use dynamic programming following Barrett et al. (2000).
  • The main limitation is the simplicity of representations: full correspondence theory, autosegmental, rich prosodic and gradient structures are left as future extensions.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Linguistics & languages

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.scil-main.27

@inproceedings{siewert2026efficient,
  title = {{Efficient universal generation in a fragment of Optimality Theory}},
  author = {Siewert, Paul},
  booktitle = {Proceedings of the Society for Computation in Linguistics 2026},
  year = {2026},
  doi = {10.18653/v1/2026.scil-main.27},
  url = {https://doi.org/10.18653/v1/2026.scil-main.27}
}

References

43 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Jason Eisner. 2000. Easy and hard constraint ranking in OT: Algorithms and complexity. In Proceedings of the Fifth Workshop of the ACL Special Interest Group in Computational Phonology, pages 22–33. find
  2. T Mark Ellison. 1994. Phonological derivation in Optimality Theory. In COLING 1994 Volume 2: The 15th International Conference on Computational Linguistics. find
  3. Alfred Vaino Aho and Margaret J. Corasick. 1975. Efficient string matching: an aid to bibliographic search. Communications of the ACM, 18(6):333–340. find
  4. Fernanda Ferreira. 2005. Psycholinguistics, formal grammars, and cognitive science. Linguistic review, 22. find
  5. Diana Archangeli and Douglas Pulleyblank. 2022. Emergent Phonology. Language Science Press. find
  6. Robert Frank and Giorgio Satta. 1998. Optimality Theory and the generative complexity of constraint violability. Computational linguistics, 24(2):307–315. find
  7. John S. Baras and George Theodorakopoulos. 2010. Path Problems in Networks. Springer. find
  8. Chris Barrett, Riko Jacob, and Madhav Marathe. 2000. Formal-language-constrained path problems. SIAM Journal on Computing, 30(3):809–837. find
  9. Dale Gerdemann and Mans Hulden. 2012. Practical finite state Optimality Theory. In Proceedings of the 10th International Workshop on Finite State Methods and Natural Language Processing, pages 10–19. find
  10. Jill N Beckman. 1998. Positional faithfulness. Ph.D. thesis, University of Massachusetts, Amherst. find
  11. Sophie Hao. 2024. Universal generation for Optimality Theory is PSPACE-complete. Computational Linguistics, 50(1):83–117. find
  12. Tamás Sándor Biró. 2006. Finding the right words: Implementing Optimality Theory with simulated annealing. Ph.D. thesis, Rijksuniversiteit Groningen. find
  13. Jeffrey Heinz and William James Idsardi. 2017. Computational phonology today. Phonology, 34(2):211–219. find
  14. Paul Boersma and Jan-Willem van Leussen. 2017. Efficient evaluation and learning in multilevel parallel constraint grammars. Linguistic Inquiry, 48(3):349–388. find
  15. Brian Buccola. 2012. On the expressivity of Optimality Theory versus ordered rewrite rules. In International Conference on Formal Grammar, pages 142–158. Springer. find
  16. Jane Chandlee. 2014. Strictly local phonological processes. Ph.D. thesis, University of Delaware, Newark. find
  17. Noam Chomsky and Morris Halle. 1968. The sound pattern of English. Harper & Row. find
  18. Paul de Lacy. 2006. Markedness: Reduction and preservation in phonology. Cambridge University Press. find
  19. William James Idsardi. 2006. A simple proof that Optimality Theory is computationally intractable. Linguistic Inquiry, 37(2):271–275. find
  20. Charles Douglas Johnson. 1970. Formal aspects of phonological description. Ph.D. thesis, University of California, Santa Barbara. find
  21. René Kager. 1999. Optimality Theory. Cambridge University Press, Cambridge. find
  22. Lauri Karttunen. 1998. The proper treatment of Optimality in computational phonology. In Finite state methods in natural language processing. find
  23. András Kornai. 2006. Guarded optimalism. Technical report, Rutgers Optimality Archive. find
  24. Edsger Wybe Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271. find
  25. William F. Dowling and Jean Henri Gallier. 1984. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. The Journal of Logic Programming, 1(3):267–284. find
  26. Jason Eisner. 1997a. Efficient generation in Primitive Optimality Theory. In 35th annual meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, pages 313–320. find
  27. Jason Eisner. 1997b. What constraints should OT allow? Technical report, LSA. ROA 204. find
  28. Jeffrey Heinz, Gregory M Kobele, and Jason Riggle. 2009. Evaluating the complexity of Optimality Theory. Linguistic Inquiry, 40(2):277–288. find
  29. András Kornai. 2009. The complexity of phonology. Linguistic Inquiry, 40(4):701–712. find
  30. Andrew Lamont. 2021. Optimality Theory implements complex functions with simple constraints. Phonology, 38(4):729–740. find
  31. Andrew Lamont. 2025. Optimality Theory with lexical insertion is not computable. University of Massachusetts Occasional Papers in Linguistics, 42. find
  32. John Joseph McCarthy and Alan Prince. 1993. Prosodic Morphology: Constraint interaction and satisfaction. Rutgers Center for Cognitive Science. find
  33. Elliott Moreton. 1999. Non-computable functions in Optimality Theory. In John Joseph McCarthy, editor, Optimality Theory in Phonology: A Reader. Blackwell Publishing. find
  34. Christopher Potts and Geoffrey Keith Pullum. 2002. Model theory and the content of OT constraints. Phonology, 19(3):361–393. find
  35. Alan Prince and Paul Smolensky. 1993. Constraint interaction in generative grammar. Rutgers University Center for Cognitive Science, New Brunswick. find
  36. Michael Oser Rabin and Dana Scott. 1959. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114–125. find
  37. Jason Alan Riggle. 2004. Generation, recognition, and learning in finite state Optimality Theory. Ph.D. thesis, University of California, Los Angeles. find
  38. Kristina Strother-Garcia. 2019. Using Model Theory in Phonology: A Novel Characterization of Syllable Structure and Syllabification. Ph.D. thesis, University of Delaware, Newark. find
  39. Bruce Benson Tesar. 1995. Computational Optimality Theory. Ph.D. thesis, University of Colorado, Boulder. find
  40. Bruce Benson Tesar. 1996. Computing optimal descriptions for Optimality Theory grammars with context-free position structures. In 34th Annual Meeting of the Association for Computational Linguistics, pages 101–107. find
  41. Jürgen Wedekind and Ronald M. Kaplan. 2020. Tractable Lexical-Functional Grammar. Computational Linguistics, 46(3):515–569. find
  42. Leo Wetzels and Joan Mascaró. 2001. The typology of voicing and devoicing. Language, 77(2):207–244. find
  43. Kie Zuraw. 2007. The role of phonetic knowledge in phonological patterning: corpus and survey evidence from Tagalog infixation. Language, 83(2):277–316. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/siewert-2026-efficient-universal-generation-fragment-optimality/