Bisimilarity of One-Counter Processes Is PSPACE-Complete

DOI10.1007/978-3-642-15375-4_13zbMath1287.68122OpenAlexW1594502574MaRDI QIDQ3584929

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

Publication date: 31 August 2010

Published in: CONCUR 2010 - Concurrency Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15375-4_13

Mathematics Subject Classification ID

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

A generic framework for checking semantic equivalences between pushdown automata and finite-state automata, Unnamed Item, Unnamed Item