joint work with Stanislav Böhm and Stefan Göller
- Speaker(s)
- Petr Jančar
- Affiliation
- Technical University of Ostrava
- Date
- March 13, 2013, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
We prove that language equivalence of deterministic one-counter automata is
NL-complete. This improves the superpolynomial time complexity upper bound
shown by Valiant and Paterson in 1975. Our main contribution is to prove that
two deterministic one-counter automata are inequivalent if and only if they can
be distinguished by a word of length polynomial in the size of the two input
automata.