Complexity of equivalence problems for concurrent systems of finite agents

DOI10.1006/inco.1997.2661zbMath0892.68061OpenAlexW2068806367MaRDI QIDQ1383143

Alexander Rabinovich

Publication date: 16 July 1998

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ff0832df7ca490906d5676dab273fbbd0da8c081

zbMATH Keywords

concurrent systemsynchronous communicating agents

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semantics in the theory of computing (68Q55)

Related Items (10)

Improved model checking of hierarchical systems ⋮ Hardness of preorder checking for basic formalisms ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system ⋮ A Parametrized Analysis of Algorithms on Hierarchical Graphs ⋮ Hardness of equivalence checking for composed finite-state systems ⋮ Symbolic model checking for \(\mu\)-calculus requires exponential time ⋮ On the complexity of verifying concurrent transition systems ⋮ Is your model checker on time? On the complexity of model checking for timed modal logics

Cites Work

• CCS expressions, finite state processes, and three problems of equivalence
• A Theory of Communicating Sequential Processes
• Three Partition Refinement Algorithms
• Checking equivalences between concurrent systems of finite agents (Extended abstract)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of equivalence problems for concurrent systems of finite agents