Working Seminar on Formal Models, Discrete Structures, and Algorithms

NL-completeness of equivalence for deterministicone-counter automata

Stanislav Böhm (VŠB Ostrava)

When: December 9, 2pm

Where: room G2.91b/G215


Emerging from formal language theory, a classical model of computation is that of pushdown automata. A folklore result is that equivalence of pushdown automata is undecidable. Concerning deterministic pushdown automata, there is still an enormous complexity gap, where the primitive recursive upper bound is not matched by the best-known lower bound of P-hardness. Thus, further subclasses have been studied. The aim of the talk is to sketch the ideas underlying the recent result. It is shown that equivalence of deterministic one-counter automata is NL-complete. One-counter automata are pushdown automata over a singleton stack alphabet plus a bottom stack symbol. This improves the superpolynomial complexity upper bound shown by Valiant and Paterson in 1975. The talk is based on joint results with S. Göller and P. Jančar.