BPA bisimilarity is EXPTIME-hard
From MaRDI portal
Publication:1943623
DOI10.1016/j.ipl.2012.12.004zbMath1259.68145arXiv1205.7041OpenAlexW2018817970MaRDI QIDQ1943623
Publication date: 20 March 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1205.7041
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 (8)
Countdown games, and simulation on (succinct) one-counter nets ⋮ 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 ⋮ Deciding the Bisimilarity of Context-Free Session Types ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bisimilarity on basic parallel processes
This page was built for publication: BPA bisimilarity is EXPTIME-hard