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)

Full work available at URL https://doi.org/10.1007/BF03180566

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

(30)

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

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)