Complexity of equivalence problems for concurrent systems of finite agents

DOI10.1006/INCO.1997.2661MaRDI QIDQ1383143zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Checking equivalences between concurrent systems of finite agents (extended abstract)
• Hardness of equivalence checking for composed finite-state systems
• CCS expressions, finite state processes, and three problems of equivalence
• Equivalence checking of non-flat systems is EXPTIME-hard.
• scientific article; zbMATH DE number 2102770

Cites work

• scientific article; zbMATH DE number 4039251 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 48630 (Why is no real title available?)
• scientific article; zbMATH DE number 177845 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 2102770 (Why is no real title available?)
• A Theory of Communicating Sequential Processes
• CCS expressions, finite state processes, and three problems of equivalence
• Checking equivalences between concurrent systems of finite agents (extended abstract)
• Three Partition Refinement Algorithms

Cited in

(13)

• scientific article; zbMATH DE number 1314226 (Why is no real title available?)
• Symbolic model checking for -calculus requires exponential time
• Improved model checking of hierarchical systems
• EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system
• Is your model checker on time? On the complexity of model checking for timed modal logics
• On the complexity of verifying concurrent transition systems
• Equivalence checking of non-flat systems is EXPTIME-hard.
• A Parametrized Analysis of Algorithms on Hierarchical Graphs
• A parametric analysis of the state-explosion problem in model checking
• Hardness of preorder checking for basic formalisms
• Dichotomy results for fixed point counting in Boolean dynamical systems
• Hardness of equivalence checking for composed finite-state systems
• Checking equivalences between concurrent systems of finite agents (extended abstract)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1383143)