Complexity of Weak Bisimilarity and Regularity for BPA and BPP
From MaRDI portal
Publication:4917028
DOI10.1016/S1571-0661(05)82505-8zbMath1260.68278OpenAlexW2074867134MaRDI QIDQ4917028
Publication date: 26 April 2013
Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s1571-0661(05)82505-8
Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Complexity of Weak Bisimilarity and Regularity for BPA and BPP, Weak bisimilarity and regularity of context-free processes is EXPTIME-hard, Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time, Unnamed Item
Cites Work
- A polynomial algorithm for deciding bisimilarity of normed context-free processes
- Deciding true concurrency equivalences on safe, finite nets
- Process rewrite systems.
- Bisimulation equivalence is decidable for all context-free processes
- Process Algebra
- A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
- Complexity of Weak Bisimilarity and Regularity for BPA and BPP
- On the Ehrenfeucht-Fraïssé game in theoretical computer science
- Deciding bisimulation-like equivalences with finite-state processes
- Infinite results
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item