Hardness of equivalence checking for composed finite-state systems
From MaRDI portal
Publication:1015390
DOI10.1007/s00236-008-0088-xzbMath1166.68018MaRDI QIDQ1015390
Publication date: 8 May 2009
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00236-008-0088-x
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Hardness of preorder checking for basic formalisms, Equivalence checking of Petri net models of programs using static and dynamic cut-points
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of iterated shuffle
- CCS expressions, finite state processes, and three problems of equivalence
- On the computational complexity of a merge recognition problem
- Deciding bisimilarity is P-complete
- Complexity of equivalence problems for concurrent systems of finite agents
- Undecidability of bisimilarity by defender's forcing
- Three Partition Refinement Algorithms
- Alternation
- CONCUR 2003 - Concurrency Theory