Deciding bisimilarity is P-complete

DOI10.1007/BF03180566MaRDI QIDQ1203120zbMATH OpenWikidataFDO

Authors José L. Balcázar, Joaquim Gabarró, 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)

Recommendations

• On the parallel complexity of bisimulation on finite systems
• Completeness results for undecidable bisimilarity problems
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• Deciding bisimilarity and similarity for probabilistic processes.
• Deciding orthogonal bisimulation

Cites work

• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• A calculus of communicating systems
• A complete axiomatisation for observational congruence of finite-state behaviours
• Automated analysis of mutual exclusion algorithms using CCS
• CCS expressions, finite state processes, and three problems of equivalence
• Formal verification of parallel programs
• New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
• On uniformity within \(NC^ 1\)
• P-uniform circuit complexity
• Three Partition Refinement Algorithms

Cited in

(29)

• Bisimilarity on basic parallel processes
• The strength of extensionality. II: Weak weak set theories without infinity
• Refinement checking on parametric modal transition systems
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
• Selected Ideas Used for Decidability and Undecidability of Bisimilarity
• Compressed tree canonization
• Hardness of equivalence checking for composed finite-state systems
• Deciding bisimulation and trace equivalences for systems with many identical processes
• On the complexity of verifying concurrent transition systems
• Bisimulation equivalence and regularity for real-time one-counter automata
• scientific article; zbMATH DE number 2080931 (Why is no real title available?)
• Two lower bounds for BPA
• EXPTIME-completeness of thorough refinement on modal transition systems
• On the complexity of verifying concurrent transition systems
• Distributed coalgebraic partition refinement
• On the parallel complexity of bisimulation on finite systems
• Deciding bisimulation equivalences for a class of non-finite-state programs
• scientific article; zbMATH DE number 2102770 (Why is no real title available?)
• On the axiomatisability of priority. III: Priority strikes again
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• Deciding bisimulation equivalences for a class of non-finite-state programs
• Behavioural equivalences on finite-state systems are PTIME-hard
• On the computational complexity of bisimulation, redux
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• Exploring the tractability border in epistemic tasks
• Hardness of preorder checking for basic formalisms
• A connection between concurrency and language theory
• Lattice-valued simulations for quantitative transition systems
• On the complexity of decision problems for parameterized finite state synchronous transducers

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

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