Equivalences of Pushdown Systems Are Hard
From MaRDI portal
Publication:5410661
DOI10.1007/978-3-642-54830-7_1zbMath1407.68258OpenAlexW18618678MaRDI QIDQ5410661
Publication date: 16 April 2014
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-54830-7_1
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (7)
The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes ⋮ Trace Inclusion for One-Counter Nets Revisited ⋮ A generic framework for checking semantic equivalences between pushdown automata and finite-state automata ⋮ Equivalence of pushdown automata via first-order grammars ⋮ Unnamed Item ⋮ Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence ⋮ On long words avoiding Zimin patterns
Uses Software
This page was built for publication: Equivalences of Pushdown Systems Are Hard
