Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes

DOI10.1007/11821069_56MaRDI QIDQ5756723zbMATH OpenOpenAlexFDO

Authors Sławomir Lasota, Wojciech Rytter

Publication date 5 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11821069_56

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Fast equivalence-checking for normed context-free processes
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Bisimulation equivalence is decidable for all context-free processes
• Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)
• Partially-commutative context-free processes: expressibility and tractability

Cited in

(11)

• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Complexity of deciding bisimilarity between normed BPA and normed BPP
• The complexity of compressed membership problems for finite automata
• Fast equivalence-checking for normed context-free processes
• Partially-Commutative Context-Free Processes
• Selected Ideas Used for Decidability and Undecidability of Bisimilarity
• Normed BPA vs. Normed BPP Revisited
• An elementary bisimulation decision procedure for arbitrary context-free processes
• Unification with Singleton Tree Grammars
• scientific article; zbMATH DE number 7301461 (Why is no real title available?)
• Partially-commutative context-free processes: expressibility and tractability

This page was built for publication: Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5756723)