Equivalence of Deterministic One-Counter Automata is NL-complete

Prelegent(ci)

Petr Jančar

Afiliacja

Technical University of Ostrava

Termin

13 marca 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Stanislav Böhm and Stefan Göller

Seminarium

Seminarium „Teoria automatów”

---

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.

---