Complexity of deciding bisimilarity between normed BPA and normed BPP

DOI10.1016/j.ic.2009.10.012zbMath1209.68338OpenAlexW2134172292MaRDI QIDQ1959482

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

Publication date: 7 October 2010

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2009.10.012

zbMATH Keywords

complexitybisimulation equivalencebasic process algebrabasic parallel processes

Mathematics Subject Classification ID

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

Cites Work

• Comparing expressibility of normed BPA and normed BPP processes
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• A lattice-theoretical fixpoint theorem and its applications
• 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

This page was built for publication: Complexity of deciding bisimilarity between normed BPA and normed BPP