Simulation preorder over simple process algebras

DOI10.1006/inco.2001.3122zbMath1009.68083OpenAlexW1965060352MaRDI QIDQ1854513

Antonín Kučera, Richard Mayr

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.3122

Mathematics Subject Classification ID

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

DP lower bounds for equivalence-checking and model-checking of one-counter automata ⋮ A generic framework for checking semantic equivalences between pushdown automata and finite-state automata ⋮ The complexity of bisimilarity-checking for one-counter processes. ⋮ On the complexity of checking semantic equivalences between pushdown processes and finite-state processes ⋮ A general approach to comparing infinite-state systems with their finite-state specifications ⋮ EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system

Cites Work

• On the regular structure of prefix rewriting
• Results on the propositional \(\mu\)-calculus
• The theory of ends, pushdown automata, and second-order logic
• Undecidable equivalences for basic process algebra
• Process rewrite systems.
• Decidability of bisimilarity for one-counter processes.
• Pushdown processes: Games and model-checking
• Bisimulation equivalence is decidable for all context-free processes
• Process Algebra
• Deciding bisimulation-like equivalences with finite-state processes
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item