@article{hao-2024-universal,
title = "Universal Generation for {O}ptimality {T}heory Is {PSPACE}-Complete",
author = "Hao, Sophie",
journal = "Computational Linguistics",
volume = "50",
number = "1",
month = mar,
year = "2024",
address = "Cambridge, MA",
publisher = "MIT Press",
url = "https://aclanthology.org/2024.cl-1.4",
doi = "10.1162/coli_a_00494",
pages = "83--117",
abstract = "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 {\mbox{$\neq$}} 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.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="hao-2024-universal">
<titleInfo>
<title>Universal Generation for Optimality Theory Is PSPACE-Complete</title>
</titleInfo>
<name type="personal">
<namePart type="given">Sophie</namePart>
<namePart type="family">Hao</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2024-03</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<genre authority="bibutilsgt">journal article</genre>
<relatedItem type="host">
<titleInfo>
<title>Computational Linguistics</title>
</titleInfo>
<originInfo>
<issuance>continuing</issuance>
<publisher>MIT Press</publisher>
<place>
<placeTerm type="text">Cambridge, MA</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">periodical</genre>
<genre authority="bibutilsgt">academic journal</genre>
</relatedItem>
<abstract>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 ʼneq 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.</abstract>
<identifier type="citekey">hao-2024-universal</identifier>
<identifier type="doi">10.1162/coli_a_00494</identifier>
<location>
<url>https://aclanthology.org/2024.cl-1.4</url>
</location>
<part>
<date>2024-03</date>
<detail type="volume"><number>50</number></detail>
<detail type="issue"><number>1</number></detail>
<extent unit="page">
<start>83</start>
<end>117</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Journal Article
%T Universal Generation for Optimality Theory Is PSPACE-Complete
%A Hao, Sophie
%J Computational Linguistics
%D 2024
%8 March
%V 50
%N 1
%I MIT Press
%C Cambridge, MA
%F hao-2024-universal
%X 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 ʼneq 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.
%R 10.1162/coli_a_00494
%U https://aclanthology.org/2024.cl-1.4
%U https://doi.org/10.1162/coli_a_00494
%P 83-117
Markdown (Informal)
[Universal Generation for Optimality Theory Is PSPACE-Complete](https://aclanthology.org/2024.cl-1.4) (Hao, CL 2024)
ACL