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

Title in Polish

Equivalence of Deterministic One-Counter Automata is NL-complete

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.

---