Equivalence of deterministic one-counter automata is NL-complete

DOI10.1145/2488608.2488626zbMath1293.68181arXiv1301.2181OpenAlexW1991034910MaRDI QIDQ5495783

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

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth 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 complexitylanguage equivalencedeterministic one-counter automata

Mathematics Subject Classification ID

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

Related Items (10)

The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes ⋮ Countdown games, and simulation on (succinct) one-counter nets ⋮ Trace Inclusion for One-Counter Nets Revisited ⋮ Trace inclusion for one-counter nets revisited ⋮ Bisimulation equivalence and regularity for real-time one-counter automata ⋮ A generic framework for checking semantic equivalences between pushdown automata and finite-state automata ⋮ On history-deterministic one-counter nets ⋮ The different shades of infinite session types ⋮ Input-driven multi-counter automata ⋮ Shortest Paths in One-Counter Systems

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