List of PSPACE-complete problems: Difference between revisions

Revision as of 13:39, 13 December 2020

Revision as of 22:47, 1 January 2021

Line 72:

* Equivalence problem for [[Nondeterministic finite automaton|nondeterministic finite automata]]<ref>[[Larry Stockmeyer|L. J. Stockmeyer]] and A. R. Meyer. Word problems requiring exponential time. In Proceedings of the 5th Symposium on Theory of Computing, pages 1–9, 1973.</ref><ref>Garey–Johnson: AL1</ref>

* Word problem and emptiness problem for non-erasing [[stack automaton|stack automata]]<ref>J. E. Hopcroft and J. D. Ullman. [[Introduction to Automata Theory, Languages, and Computation]], first edition, 1979.</ref>

* [[Intersection_Non-Emptiness_Problem|Emptiness of intersection of an unbounded number of [[deterministic finite automata]]<ref name="D. Kozen 1977">D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.</ref>

<!-- the original reference to Kozen should suffice, no?...

<ref>M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.</ref> <ref>K.-J. Lange and P. Rossmanith. The emptiness problem for intersections of regular languages. In I. Havel, editor, Proc. of the 17th Conf. on Mathematical Foundations of Computer Science, number 629 in LNCS, pages 346–354. Springer-Verlag, 1992.</ref>