Equivalence of Deterministic One-Counter Automata is NL-complete

2013/01/10 by Böhm, Stanislav, Göller, Stefan, Jančar, Petr · 1 citation
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1301.2181

Abstract

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.

Cited by

• Atomic Gliders and CA as Language Generators (Extended Version)

Related

• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• Equivalence of Deterministic Weighted Real-time One-Counter Automata
• A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars
• Learning Deterministic One-Counter Automata in Polynomial Time
• Revisiting the Equivalence Problem for Finite Multitape Automata