On the computational complexity of bisimulation, redux

DOI10.1016/J.IC.2004.06.003MaRDI QIDQ703845zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Faron Moller, Scott A. Smolka, Jiří Srba

Publication date 11 January 2005

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

Full work available at URL https://doi.org/10.1016/j.ic.2004.06.003

zbMATH Keywords

ComplexityAutomataFormal languagesBisimulation equivalenceEquivalence-checkingModel-checkingOne-counter machines

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• On the parallel complexity of bisimulation on finite systems
• scientific article; zbMATH DE number 6970796
• scientific article; zbMATH DE number 1670835
• scientific article; zbMATH DE number 1759489
• Deciding bisimilarity is P-complete

Cites work

• scientific article; zbMATH DE number 1701362 (Why is no real title available?)
• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 5604065 (Why is no real title available?)
• scientific article; zbMATH DE number 4011914 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 3744561 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 3485746 (Why is no real title available?)
• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 1231553 (Why is no real title available?)
• scientific article; zbMATH DE number 1361117 (Why is no real title available?)
• scientific article; zbMATH DE number 1028833 (Why is no real title available?)
• scientific article; zbMATH DE number 1927587 (Why is no real title available?)
• scientific article; zbMATH DE number 1479629 (Why is no real title available?)
• scientific article; zbMATH DE number 1555184 (Why is no real title available?)
• scientific article; zbMATH DE number 952378 (Why is no real title available?)
• scientific article; zbMATH DE number 2086414 (Why is no real title available?)
• scientific article; zbMATH DE number 2086665 (Why is no real title available?)
• scientific article; zbMATH DE number 2086674 (Why is no real title available?)
• scientific article; zbMATH DE number 869193 (Why is no real title available?)
• A calculus of communicating systems
• A calculus of mobile processes. I
• A distributed algorithm for strong bisimulation reduction of state spaces
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
• Algebraic laws for nondeterminism and concurrency
• An elementary bisimulation decision procedure for arbitrary context-free processes
• Bisimulation equivalence is decidable for all context-free processes
• Bisimulation from open maps
• Bisimulation, modal logic and model checking games
• Branching time and abstraction in bisimulation semantics
• CCS expressions, finite state processes, and three problems of equivalence
• Decidability of DPDA equivalence
• Decidability of bisimulation equivalence for normed pushdown processes
• Decidability of bisimulation equivalence for process generating context-free languages
• Deciding bisimilarity is P-complete
• Equivalence-checking with infinite-state systems: techniques and results
• High undecidability of weak bisimilarity for Petri nets
• Infinite results
• On deciding readiness and failure equivalences for processes
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
• On the equivalence, containment, and covering problems for the regular and context-free languages
• On the foundations of final coalgebra semantics: non-well-founded sets, partial orders, metric spaces
• On the regular structure of prefix rewriting
• Process Algebra
• Process rewrite systems.
• Three Partition Refinement Algorithms
• Undecidability of bisimilarity for Petri nets and some related problems
• Undecidable equivalences for basic process algebra
• Universal coalgebra: A theory of systems
• Verification on infinite structures.
• \(L(A)=L(B)\)? decidability results from complete formal systems

Cited in

(7)

• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• A complexity analysis of bisimilarity for value-passing processes
• Equivalence checking 40 years after: a review of bisimulation tools
• scientific article; zbMATH DE number 5263437 (Why is no real title available?)
• From bisimulation to simulation: Coarsest partition problems
• CONCUR 2005 – Concurrency Theory
• Bisimulation indexes and their applications

This page was built for publication: On the computational complexity of bisimulation, redux

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