On the computational complexity of bisimulation, redux
DOI10.1016/j.ic.2004.06.003zbMath1074.68038OpenAlexW2078508239WikidataQ59556955 ScholiaQ59556955MaRDI QIDQ703845
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
ComplexityAutomataFormal languagesModel-checkingBisimulation equivalenceEquivalence-checkingOne-counter machines
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items
Cites Work
- Undecidability of bisimilarity for Petri nets and some related problems
- On the regular structure of prefix rewriting
- CCS expressions, finite state processes, and three problems of equivalence
- A calculus of communicating systems
- A calculus of mobile processes. I
- Deciding bisimilarity is P-complete
- On the equivalence, containment, and covering problems for the regular and context-free languages
- Decidability of bisimulation equivalence for normed pushdown processes
- Undecidable equivalences for basic process algebra
- A polynomial algorithm for deciding bisimilarity of normed context-free processes
- Universal coalgebra: A theory of systems
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Process rewrite systems.
- On deciding readiness and failure equivalences for processes
- Bisimulation equivalence is decidable for all context-free processes
- Bisimulation from open maps
- Equivalence-Checking with Infinite-State Systems: Techniques and Results
- Decidability of bisimulation equivalence for process generating context-free languages
- An elementary bisimulation decision procedure for arbitrary context-free processes
- Algebraic laws for nondeterminism and concurrency
- Three Partition Refinement Algorithms
- Process Algebra
- On the foundations of final coalgebra semantics: non-well-founded sets, partial orders, metric spaces
- Bisimulation, modal logic and model checking games
- Branching time and abstraction in bisimulation semantics
- A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
- On the Ehrenfeucht-Fraïssé game in theoretical computer science
- High undecidability of weak bisimilarity for Petri nets
- Decidability of DPDA equivalence
- Infinite results
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
