Bisimulation equivalence and regularity for real-time one-counter automata

A one-counter automaton is a pushdown automaton with a singleton stack alphabet, where stack emptiness can be tested; it is a real-time automaton if it contains no ε-transitions. We study the computational complexity of the problems of equivalence and regularity (i.e. semantic finiteness) on real-time one-counter automata. The first main result shows PSPACE-completeness of bisimulation equivalence; this closes the complexity gap between decidability [23] and PSPACE-hardness [25]. The second main result shows NL-completeness of language equivalence of deterministic real-time one-counter automata; this improves the known PSPACE upper bound (indirectly shown by Valiant and Paterson [27]). Finally we prove P-completeness of the problem if a given one-counter automaton is bisimulation equivalent to a finite system, and NL-completeness of the problem if the language accepted by a given deterministic real-time one-counter automaton is regular.