Equivalence of deterministic one-counter automata is NL-complete

DOI10.1145/2488608.2488626MaRDI QIDQ5495783zbMATH OpenOpenAlexWikidataFDO

Authors Stanislav Böhm, Stefan Göller, Petr Jančar

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.2181

zbMATH Keywords

computational complexitydeterministic one-counter automatalanguage equivalence

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

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.

Recommendations

• Language equivalence of deterministic real-time one-counter automata is NL-complete
• Bisimulation equivalence and regularity for real-time one-counter automata
• On Büchi one-counter automata
• scientific article; zbMATH DE number 2087430
• On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)

Cited in

(16)

• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Trace inclusion for one-counter nets revisited
• Bisimulation equivalence and regularity for real-time one-counter automata
• Language equivalence of deterministic real-time one-counter automata is NL-complete
• Trace inclusion for one-counter nets revisited
• On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)
• On Büchi one-counter automata
• The Hoare logic of deterministic and nondeterministic monadic recursion schemes
• Countdown games, and simulation on (succinct) one-counter nets
• Input-driven multi-counter automata
• On history-deterministic one-counter nets
• The different shades of infinite session types
• Invariants for one-counter automata with disequality tests
• Equivalence of deterministic weighted real-time one-counter automata
• Parikh one-counter automata
• Weighted one-deterministic-counter automata

This page was built for publication: Equivalence of deterministic one-counter automata is NL-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495783)