Deciding bisimilarity is P-complete

DOI10.1007/BF03180566zbMath0758.68033MaRDI QIDQ1203120

Joaquim Gabarró, José L. Balcázar, Miklos Santha

Publication date: 4 February 1993

Published in: Formal Aspects of Computing (Search for Journal in Brave)

zbMATH Keywords

CCSP-completenessbisimilaritymany-one NC-reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (20)

A connection between concurrency and language theory ⋮ Compressed Tree Canonization ⋮ Bisimulation equivalence and regularity for real-time one-counter automata ⋮ On the axiomatisability of priority. III: Priority strikes again ⋮ The strength of extensionality. II: Weak weak set theories without infinity ⋮ Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus ⋮ Hardness of preorder checking for basic formalisms ⋮ Lattice-valued simulations for quantitative transition systems ⋮ Exploring the tractability border in epistemic tasks ⋮ Deciding bisimulation and trace equivalences for systems with many identical processes ⋮ EXPTIME-completeness of thorough refinement on modal transition systems ⋮ On the complexity of verifying concurrent transition systems ⋮ Weak bisimilarity and regularity of context-free processes is EXPTIME-hard ⋮ On the computational complexity of bisimulation, redux ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hardness of equivalence checking for composed finite-state systems ⋮ Bisimilarity on basic parallel processes ⋮ Refinement checking on parametric modal transition systems ⋮ On the complexity of verifying concurrent transition systems

Cites Work

• Automated analysis of mutual exclusion algorithms using CCS
• CCS expressions, finite state processes, and three problems of equivalence
• A calculus of communicating systems
• A complete axiomatisation for observational congruence of finite-state behaviours
• On uniformity within \(NC^ 1\)
• P-uniform circuit complexity
• Three Partition Refinement Algorithms
• Formal verification of parallel programs
• New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deciding bisimilarity is P-complete