Bisimilarity of Pushdown Automata is Nonelementary
From MaRDI portal
Publication:5271086
DOI10.1109/LICS.2013.55zbMath1366.68136arXiv1210.7686MaRDI QIDQ5271086
Michael Benedikt, Andrzej S. Murawski, Stefan Göller, Stefan Kiefer
Publication date: 3 July 2017
Published in: 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1210.7686
Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Bisimulation equivalence and regularity for real-time one-counter automata ⋮ 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