Complexity of Weak Bisimilarity and Regularity for BPA and BPP

DOI10.1016/S1571-0661(05)82505-8zbMath1260.68278OpenAlexW2074867134MaRDI QIDQ4917028

Jiří Srba

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

Mathematics Subject Classification ID

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