List of PSPACE-complete problems: Difference between revisions

Revision as of 20:24, 13 January 2021

Revision as of 20:25, 13 January 2021

Line 84:

* Word problem for [[context-sensitive language]]<ref>S.-Y. Kuroda, "Classes of languages and linear-bounded automata", ''Information and Control'', '''7'''(2): 207&ndash;223, June 1964.</ref>

* Intersection emptiness for an unbounded number of [[regular language]]s <ref name="D. Kozen 1977"/>

* Regular Expression StartStar-Freeness <ref>{{cite web |last1=Bernátsky |first1=László |title=Regular Expression star-freeness is PSPACE-Complete |url=http://publicatio.bibl.u-szeged.hu/9528/1/Bernatsky_1997_ActaCybernetica.pdf |access-date=13 January 2021}}</ref>

* [[Equivalence problem]] for [[regular expression]]s<ref name = WagnerW/>

* [[Emptiness problem]] for [[regular expression]]s with intersection.<ref name = WagnerW/>