Bisimilarity of one-counter processes is PSPACE-complete

DOI10.1007/978-3-642-15375-4_13zbMATH Open1287.68122OpenAlexW1594502574MaRDI QIDQ3584929FDOQ3584929

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

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

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)

Cited In (8)

• Title not available (Why is that?)
• The complexity of bisimilarity-checking for one-counter processes.
• Bisimulation equivalence is decidable for one-counter processes
• Decidability of bisimilarity 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
• Title not available (Why is that?)

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)