Bisimilarity of one-counter processes is PSPACE-complete

DOI10.1007/978-3-642-15375-4_13MaRDI QIDQ3584929zbMATH OpenOpenAlexFDO

Authors Stanislav Böhm, Stefan Göller, 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Decidability of bisimilarity for one-counter processes.
• Bisimulation equivalence is decidable for one-counter processes
• The complexity of bisimilarity-checking for one-counter processes.
• scientific article; zbMATH DE number 1670834
• Bisimulation equivalence and regularity for real-time one-counter automata

Cited in

(8)

• scientific article; zbMATH DE number 7559503 (Why is no real title available?)
• The complexity of bisimilarity-checking for one-counter processes.
• Decidability of bisimilarity for one-counter processes.
• Bisimulation equivalence is decidable for one-counter processes
• Bisimulation equivalence and regularity for real-time one-counter automata
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Game characterization of probabilistic bisimilarity, and applications to pushdown automata
• scientific article; zbMATH DE number 2086414 (Why is no real title available?)

This page was built for publication: Bisimilarity of one-counter processes is PSPACE-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3584929)