---
title: "Efficient universal generation in a fragment — Siewert 2026"
description: "This paper addresses the universal generation problem in Optimality Theory (OT): computing a grammar's output from its constraint ranking."
authors: ["Paul Siewert"]
year: 2026
venue: "Proceedings of the Society for Computation in Linguistics 2026"
source: "https://aclanthology.org/2026.scil-main.27/"
doi: "10.18653/v1/2026.scil-main.27"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/siewert-2026-efficient-universal-generation-fragment-optimality/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/siewert-2026-efficient-universal-generation-fragment-optimality/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2026](https://md.research.elamur.ai/free/en/papers/2026/page/5/) / Efficient universal generation in a fragment of Optimality Theory

# Efficient universal generation in a fragment of Optimality Theory

**Authors:** Paul Siewert · **Institutions:** [University of Cambridge](https://md.research.elamur.ai/free/en/universities/university-of-cambridge/) · **Year:** 2026 · **Venue:** Proceedings of the Society for Computation in Linguistics 2026 · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2026.scil-main.27/) · [PDF](https://aclanthology.org/2026.scil-main.27.pdf) · [DOI 10.18653/v1/2026.scil-main.27](https://doi.org/10.18653/v1/2026.scil-main.27) · [OpenAlex](https://openalex.org/W7166851130)

**Citations:** 0 citations (OpenAlex, 2026-10-14)

## 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](https://md.research.elamur.ai/free/en/shelves/linguistics/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@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}
}
```

- [← previous Efficient Topic Extraction via Graph-Based Labeling: A Lightweight Alternative to Deep Models](https://md.research.elamur.ai/free/en/papers/mekaoui-2026-efficient-topic-extraction-graph-based/)
- [next → Egypto-Semitic Comparison: Some Considerations on Bilabials and Dentals Relationship](https://md.research.elamur.ai/free/en/papers/franci-2026-egypto-semitic-comparison-some-considerations/)
- [↑ back to papers of 2026](https://md.research.elamur.ai/free/en/papers/2026/page/5/)

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