{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:00:17Z","timestamp":1753884017741},"reference-count":36,"publisher":"MIT Press","issue":"1","license":[{"start":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T00:00:00Z","timestamp":1700006400000},"content-version":"vor","delay-in-days":318,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>This article shows that the universal generation problem for Optimality Theory (OT) is PSPACE-complete. While prior work has shown that universal generation is at least NP-hard and at most EXPSPACE-hard, our results place universal generation in between those two classes, assuming that NP \u2260 PSPACE. We additionally show that when the number of constraints is bounded in advance, universal generation is at least NL-hard and at most NPNP-hard. Our proofs rely on a close connection between OT and the intersection non-emptiness problem for finite automata, which is PSPACE-complete in general and NL-complete when the number of automata is bounded. Our analysis shows that constraint interaction is the main contributor to the complexity of OT: The ability to factor transformations into simple, interacting constraints allows OT to furnish compact descriptions of intricate phonological phenomena.<\/jats:p>","DOI":"10.1162\/coli_a_00494","type":"journal-article","created":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T19:25:52Z","timestamp":1700076352000},"page":"83-117","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":2,"title":["Universal Generation for Optimality Theory Is PSPACE-Complete"],"prefix":"10.1162","volume":"50","author":[{"given":"Sophie","family":"Hao","sequence":"first","affiliation":[{"name":"Center for Data Science, New York University. sophie.hao@nyu.edu"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2023,3,1]]},"reference":[{"key":"2024041918253665800_bib1","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tcs.2015.02.037","article-title":"Classic Nintendo games are (computationally) hard","volume":"586","author":"Aloupis","year":"2015","journal-title":"Theoretical Computer Science"},{"key":"2024041918253665800_bib2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"Arora","year":"2009"},{"key":"2024041918253665800_bib3","first-page":"28","article-title":"Implementing faithfulness constraints in a finite state model of optimality theory","volume-title":"Proceedings of the 14th Irish Conference on Artificial Intelligence and Cognitive Science","author":"Chen-Main","year":"2003"},{"key":"2024041918253665800_bib4","volume-title":"The Sound Pattern of English","author":"Chomsky","year":"1968","edition":"first edition"},{"issue":"1","key":"2024041918253665800_bib5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numerische Mathematik"},{"key":"2024041918253665800_bib6","doi-asserted-by":"publisher","first-page":"313","DOI":"10.3115\/976909.979657","article-title":"Efficient generation in primitive optimality theory","volume-title":"Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics","author":"Eisner","year":"1997"},{"key":"2024041918253665800_bib7","doi-asserted-by":"publisher","first-page":"257","DOI":"10.3115\/990820.990858","article-title":"Directional constraint evaluation in optimality theory","volume-title":"Proceedings of the 18th Conference on Computational Linguistics","author":"Eisner","year":"2000"},{"key":"2024041918253665800_bib8","first-page":"22","article-title":"Easy and Hard Constraint ranking in OT: Algorithms and complexity","volume-title":"Proceedings of the Fifth Workshop of the ACL Special Interest Group in Computational Phonology","author":"Eisner","year":"2000"},{"key":"2024041918253665800_bib9","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.3115\/991250.991312","article-title":"Phonological derivation in optimality theory","volume-title":"Proceedings of the 15th Conference on Computational Linguistics","author":"Ellison","year":"1994"},{"issue":"1","key":"2024041918253665800_bib10","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1016\/S0304-3975(01)00173-6","article-title":"Rush hour is PSPACE-complete, or \u201cWhy you should generously tip parking lot attendants\u201d","volume":"270","author":"Flake","year":"2002","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"2024041918253665800_bib11","first-page":"307","article-title":"Optimality theory and the generative complexity of constraint violability","volume":"24","author":"Frank","year":"1998","journal-title":"Computational Linguistics"},{"key":"2024041918253665800_bib12","first-page":"10","article-title":"Practical finite state optimality theory","volume-title":"Proceedings of the 10th International Workshop on Finite State Methods and Natural Language Processing","author":"Gerdemann","year":"2012"},{"key":"2024041918253665800_bib13","unstructured":"Goldsmith, John Anton\n          . 1976. Autosegmental Phonology. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA."},{"issue":"2","key":"2024041918253665800_bib14","doi-asserted-by":"publisher","first-page":"49","DOI":"10.15398\/jlm.v7i2.210","article-title":"Finite-state optimality theory: Non-rationality of harmonic serialism","volume":"7","author":"Hao","year":"2019","journal-title":"Journal of Language Modelling"},{"issue":"2","key":"2024041918253665800_bib15","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1162\/ling.2009.40.2.277","article-title":"Evaluating the complexity of optimality theory","volume":"40","author":"Heinz","year":"2009","journal-title":"Linguistic Inquiry"},{"issue":"2","key":"2024041918253665800_bib16","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1162\/ling.2006.37.2.271","article-title":"A simple proof that optimality theory is computationally intractable","volume":"37","author":"Idsardi","year":"2006","journal-title":"Linguistic Inquiry"},{"issue":"2","key":"2024041918253665800_bib17","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(94)90131-7","article-title":"The Othello game on an n \u00d7 n board is PSPACE-complete","volume":"123","author":"Iwata","year":"1994","journal-title":"Theoretical Computer Science"},{"key":"2024041918253665800_bib18","unstructured":"Johnson, C. Douglas\n          . 1970. Formal Aspects of Phonological Description. Ph.D. thesis, University of California, Berkeley, Berkeley, CA, USA."},{"key":"2024041918253665800_bib19","doi-asserted-by":"publisher","DOI":"10.1515\/9783110876000","volume-title":"Formal Aspects of Phonological Desription","author":"Johnson","year":"1972"},{"issue":"1","key":"2024041918253665800_bib20","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","article-title":"Space-bounded reducibility among combinatorial problems","volume":"11","author":"Jones","year":"1975","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"2024041918253665800_bib21","first-page":"331","article-title":"Regular models of phonological rule systems","volume":"20","author":"Kaplan","year":"1994","journal-title":"Computational Linguistics"},{"key":"2024041918253665800_bib22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3115\/1611533.1611534","article-title":"The proper treatment of optimality in computational phonology","volume-title":"Proceedings of the International Workshop on Finite State Methods in Natural Language Processing","author":"Karttunen","year":"1998"},{"key":"2024041918253665800_bib23","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1109\/SFCS.1977.16","article-title":"Lower bounds for natural proof systems","volume-title":"18th Annual Symposium on Foundations of Computer Science (Sfcs 1977)","author":"Kozen","year":"1977"},{"key":"2024041918253665800_bib24","article-title":"Optimality Theory is not computable","author":"Lamont","year":"2023"},{"key":"2024041918253665800_bib25","first-page":"249","article-title":"Faithfulness and reduplicative identity","volume":"18: Papers in Optimality Theory","author":"McCarthy","year":"1995","journal-title":"University of Massachusetts Occasional Papers in Linguistics"},{"issue":"6","key":"2024041918253665800_bib26","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1111\/j.1551-6709.2009.01047.x","article-title":"Weighted constraints in generative linguistics","volume":"33","author":"Pater","year":"2009","journal-title":"Cognitive Science"},{"issue":"4","key":"2024041918253665800_bib27","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","article-title":"A variant of a recursively unsolvable problem","volume":"52","author":"Post","year":"1946","journal-title":"Bulletin of the American Mathematical Society"},{"issue":"1","key":"2024041918253665800_bib28","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1017\/S0952675710000047","article-title":"Harmonic Grammar with linear programming: From linear systems to linguistic typology","volume":"27","author":"Potts","year":"2010","journal-title":"Phonology"},{"key":"2024041918253665800_bib29","unstructured":"Prince, Alan and PaulSmolensky. 1993. Optimality theory: Constraint interaction in generative grammar. Technical Report 2, Rutgers University, New Brunswick, NJ, USA."},{"key":"2024041918253665800_bib30","doi-asserted-by":"publisher","DOI":"10.1002\/9780470759400","volume-title":"Optimality Theory: Constraint Interaction in Generative Grammar","author":"Prince","year":"2004"},{"issue":"2","key":"2024041918253665800_bib31","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","article-title":"Finite automata and their decision problems","volume":"3","author":"Rabin","year":"1959","journal-title":"IBM Journal of Research and Development"},{"key":"2024041918253665800_bib32","unstructured":"Riggle, Jason Alan\n          . 2004. Generation, Recognition, and Learning in Finite State Optimality Theory. Ph.D. thesis, University of California, Los Angeles, Los Angeles, CA, USA."},{"issue":"2","key":"2024041918253665800_bib33","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","article-title":"Relationships between nondeterministic and deterministic tape complexities","volume":"4","author":"Savitch","year":"1970","journal-title":"Journal of Computer and System Sciences"},{"key":"2024041918253665800_bib34","volume-title":"Introduction to the Theory of Computation","author":"Sipser","year":"2013","edition":"third edition"},{"key":"2024041918253665800_bib35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/800125.804029","article-title":"Word problems requiring exponential time: Preliminary report","volume-title":"Proceedings of the Fifth Annual ACM Symposium on Theory of Computing","author":"Stockmeyer","year":"1973"},{"key":"2024041918253665800_bib36","unstructured":"Wareham, Harold Todd\n          . 1998. Systematic Parameterized Complexity Analysis in Computational Phonology. Ph.D. thesis, University of Victoria, Victoria, Canada."}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/coli\/article-pdf\/50\/1\/83\/2364983\/coli_a_00494.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/coli\/article-pdf\/50\/1\/83\/2364983\/coli_a_00494.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,19]],"date-time":"2024-04-19T18:26:03Z","timestamp":1713551163000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/50\/1\/83\/118130\/Universal-Generation-for-Optimality-Theory-Is"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,3,1]]},"published-print":{"date-parts":[[2023,3,1]]}},"URL":"https:\/\/doi.org\/10.1162\/coli_a_00494","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023]]},"published":{"date-parts":[[2023]]}}}