Simulation preorder over simple process algebras

DOI10.1006/INCO.2001.3122MaRDI QIDQ1854513zbMATH OpenOpenAlexFDO

Authors Antonin Kučera, Richard M. 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

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

• scientific article; zbMATH DE number 2086521
• Priorities in process algebras
• Strong bisimilarity of simple process algebras: Complexity lower bounds
• scientific article; zbMATH DE number 1929970
• scientific article; zbMATH DE number 7774247
• Priority and abstraction in process algebra
• Partial-order process algebra (and its relation to Petri nets)
• Simulations up-to and canonical preorders (extended abstract)
• Process Algebra: An Algebraic Theory of Concurrency
• scientific article; zbMATH DE number 1500527

Cites work

• scientific article; zbMATH DE number 3885321 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 1759489 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Bisimulation equivalence is decidable for all context-free processes
• Decidability of bisimilarity for one-counter processes.
• Deciding bisimulation-like equivalences with finite-state processes
• On the regular structure of prefix rewriting
• Process Algebra
• Process rewrite systems.
• Pushdown processes: Games and model-checking
• Results on the propositional \(\mu\)-calculus
• The theory of ends, pushdown automata, and second-order logic
• Undecidable equivalences for basic process algebra
• Verification on infinite structures.
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time

Cited in

(10)

• The complexity of bisimilarity-checking for one-counter processes.
• Testing preorders for probabilistic processes can be characterized by simulations
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes
• DP lower bounds for equivalence-checking and model-checking of one-counter automata
• EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system
• scientific article; zbMATH DE number 1114007 (Why is no real title available?)
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Deciding bisimulation-like equivalences with finite-state processes
• scientific article; zbMATH DE number 1927588 (Why is no real title available?)
• A general approach to comparing infinite-state systems with their finite-state specifications

This page was built for publication: Simulation preorder over simple process algebras

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