Deciding bisimilarity is P-complete
DOI10.1007/BF03180566zbMATH Open0758.68033WikidataQ130991537 ScholiaQ130991537MaRDI QIDQ1203120FDOQ1203120
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)
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
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)
Cites Work
- On uniformity within \(NC^ 1\)
- Title not available (Why is that?)
- Three Partition Refinement Algorithms
- A calculus of communicating systems
- CCS expressions, finite state processes, and three problems of equivalence
- Title not available (Why is that?)
- Formal verification of parallel programs
- Title not available (Why is that?)
- P-uniform circuit complexity
- A complete axiomatisation for observational congruence of finite-state behaviours
- Automated analysis of mutual exclusion algorithms using CCS
- New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
Cited In (29)
- Behavioural equivalences on finite-state systems are PTIME-hard
- Title not available (Why is that?)
- EXPTIME-completeness of thorough refinement on modal transition systems
- Title not available (Why is that?)
- A connection between concurrency and language theory
- 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
- Title not available (Why is that?)
- Compressed tree canonization
- Two lower bounds for BPA
- Deciding bisimulation equivalences for a class of non-finite-state programs
- Deciding bisimulation equivalences for a class of non-finite-state programs
- Hardness of preorder checking for basic formalisms
- 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
- Distributed coalgebraic partition refinement
- On the parallel complexity of bisimulation on finite systems
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- Bisimilarity on basic parallel processes
- Deciding bisimulation and trace equivalences for systems with many identical processes
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)
