On the computational complexity of bisimulation, redux

DOI10.1016/J.IC.2004.06.003zbMATH Open1074.68038DBLPjournals/iandc/MollerSS04OpenAlexW2078508239WikidataQ59556955 ScholiaQ59556955MaRDI QIDQ703845FDOQ703845

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

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

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)

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• Equivalence checking 40 years after: a review of bisimulation tools
• A complexity analysis of bisimilarity for value-passing processes
• Title not available (Why is that?)
• 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)