Hardness of equivalence checking for composed finite-state systems

DOI10.1007/s00236-008-0088-xzbMath1166.68018OpenAlexW2027782662MaRDI QIDQ1015390

Petr Jančar, Zdeněk Sawa

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

zbMATH Keywords

computational complexityacyclic systems

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Equivalence checking of Petri net models of programs using static and dynamic cut-points ⋮ Hardness of preorder checking for basic formalisms

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hardness of equivalence checking for composed finite-state systems