Normed BPA vs. Normed BPP Revisited

DOI10.1007/978-3-540-85361-9_34zbMath1160.68468MaRDI QIDQ3541036

Petr Jančar, Zdeněk Sawa, Martin Kot

Publication date: 25 November 2008

Published in: CONCUR 2008 - Concurrency Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85361-9_34

zbMATH Keywords

verification; equivalence checking; bisimulation equivalence; basic process algebra; basic parallel processes

Mathematics Subject Classification ID

68Q60: Specification and verification (program logics, model checking, etc.)

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Related Items

Partially-commutative context-free processes: expressibility and tractability, Partially-Commutative Context-Free Processes, Selected Ideas Used for Decidability and Undecidability of Bisimilarity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparing expressibility of normed BPA and normed BPP processes
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• An elementary bisimulation decision procedure for arbitrary context-free processes
• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
• Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes
• CONCUR 2003 - Concurrency Theory
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time