Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-Complete
From MaRDI portal
Publication:3088039
DOI10.1007/978-3-642-22993-0_20zbMath1343.68133OpenAlexW136524193MaRDI QIDQ3088039
Publication date: 17 August 2011
Published in: Mathematical Foundations of Computer Science 2011 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22993-0_20
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ On history-deterministic one-counter nets ⋮ Synchronizing deterministic push-down automata can be really hard
This page was built for publication: Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-Complete
