Equivalence of Deterministic One-Counter Automata is NL-complete

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

paper · pdf · doi:10.48550/arxiv.1301.2181

arxiv created 2013/01/10 · arxiv updated 2013/01/11

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