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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) 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

(10)

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

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)