An elementary bisimulation decision procedure for arbitrary context-free processes

DOI10.1007/3-540-60246-1_148MaRDI QIDQ3569030zbMATH OpenOpenAlexFDO

Authors Olaf Burkart, Bernhard Steffen, Didier Caucal

Publication date 17 June 2010

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

Full work available at URL https://doi.org/10.1007/3-540-60246-1_148

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)
• Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes
• Bisimulation equivalence is decidable for all context-free processes
• Partially-Commutative Context-Free Processes
• Actions speak louder than words: proving bisimilarity for context-free processes

Cited in

(31)

• Decidability of bisimulation equivalence for normed pushdown processes
• Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)
• The complexity of bisimilarity-checking for one-counter processes.
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
• Bisimulation equivalence is decidable for all context-free processes
• Complexity of deciding bisimilarity between normed BPA and normed BPP
• Bisimilarity on basic parallel processes
• Equivalence of pushdown automata via first-order grammars
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Bisimulation equivalence and regularity for real-time one-counter automata
• Decidability of branching bisimulation on normed commutative context-free processes
• Expansive-Bisimulation for Context-Free Processes
• Selected Ideas Used for Decidability and Undecidability of Bisimilarity
• Deciding Bisimilarity of Full BPA Processes Locally
• Normed BPA vs. Normed BPP Revisited
• scientific article; zbMATH DE number 4035115 (Why is no real title available?)
• Actions speak louder than words: proving bisimilarity for context-free processes
• Deciding the bisimilarity of context-free session types
• Decidability of weak bisimilarity for a subset of BPA
• Pushdown automata, multiset automata, and Petri nets
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• Basic process algebra with deadlocking states
• Never-stop context-free learning
• Infinite results
• Bisimulation collapse and the process taxonomy
• Polymorphic higher-order context-free session types
• System \(F^\mu_\omega\) with context-free session types
• Subtyping context-free session types
• Subtyping context-free session types
• On the computational complexity of bisimulation, redux
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes

This page was built for publication: An elementary bisimulation decision procedure for arbitrary context-free processes

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