Normed BPA vs. Normed BPP Revisited

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

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

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

verificationequivalence checkingbisimulation equivalencebasic process algebrabasic parallel processes

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item