On the computational complexity of bisimulation, redux
type: Item
instance of: scholarly article
title: On the computational complexity of bisimulation, redux
zbMATH Open document ID: 1074.68038
author: Faron Moller
author: Scott A. Smolka
author: Jiří Srba
published in: Information and Computation
publication date: 2005-01-11T00:00:00Z
Mathematics Subject Classification ID: 68Q85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68-02
zbMATH DE Number: 2126482
zbMATH Keywords: One-counter machines
zbMATH Keywords: Equivalence-checking
zbMATH Keywords: Model-checking
zbMATH Keywords: Automata
zbMATH Keywords: Formal languages
zbMATH Keywords: Bisimulation equivalence
zbMATH Keywords: Complexity
MaRDI profile type: Publication
full work available at URL: j.ic.2004.06.003
OpenAlex ID: W2078508239
Wikidata QID: Q59556955
cites work: Decidability of bisimulation equivalence for process generating context-free languages
cites work: Q3761680
cites work: Process Algebra
cites work: Deciding bisimilarity is P-complete
cites work: Q3292904
cites work: Q4717366
cites work: A distributed algorithm for strong bisimulation reduction of state spaces
cites work: Verification on infinite structures.
cites work: An elementary bisimulation decision procedure for arbitrary context-free processes
cites work: On the regular structure of prefix rewriting
cites work: Bisimulation equivalence is decidable for all context-free processes
cites work: Undecidable equivalences for basic process algebra
cites work: Algebraic laws for nondeterminism and concurrency
cites work: Q4525284
cites work: Q4222868
cites work: A polynomial algorithm for deciding bisimilarity of normed context-free processes
cites work: A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
cites work: On the equivalence, containment, and covering problems for the regular and context-free languages
cites work: Q4490743
cites work: On deciding readiness and failure equivalences for processes
cites work: High undecidability of weak bisimilarity for Petri nets
cites work: Undecidability of bisimilarity for Petri nets and some related problems
cites work: Equivalence-Checking with Infinite-State Systems: Techniques and Results
cites work: Q4270051
cites work: Bisimulation from open maps
cites work: CCS expressions, finite state processes, and three problems of equivalence
cites work: Q4072875
cites work: Process rewrite systems.
cites work: A calculus of communicating systems
cites work: Q3929062
cites work: Q3992568
cites work: A calculus of mobile processes. I
cites work: Infinite results
cites work: Three Partition Refinement Algorithms
cites work: Q3907077
cites work: Universal coalgebra: A theory of systems
cites work: Q4068699
cites work: \(L(A)=L(B)\)? decidability results from complete formal systems
cites work: Q3395948
cites work: Q4736869
cites work: Q4737202
cites work: Q4484512
cites work: Bisimulation, modal logic and model checking games
cites work: Decidability of bisimulation equivalence for normed pushdown processes
cites work: Decidability of DPDA equivalence
cites work: Q2769443
cites work: Q4737211
cites work: On the Ehrenfeucht-Fraïssé game in theoretical computer science
cites work: On the foundations of final coalgebra semantics: non-well-founded sets, partial orders, metric spaces
cites work: Q4342096
cites work: Q4874391
cites work: Branching time and abstraction in bisimulation semantics
DBLP publication ID: journals/iandc/MollerSS04
DOI: 10.1016/J.IC.2004.06.003