An elementary bisimulation decision procedure for arbitrary context-free processes

DOI10.1007/3-540-60246-1_148zbMATH Open1193.68172OpenAlexW1555553717MaRDI QIDQ3569030FDOQ3569030

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

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

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)

Cited In (26)

• Equivalence of pushdown automata via first-order grammars
• Decidability of weak bisimilarity for a subset of BPA
• The complexity of bisimilarity-checking for one-counter processes.
• On the computational complexity of bisimulation, redux
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes
• Pushdown automata, multiset automata, and Petri nets
• Never-stop context-free learning
• Infinite results
• Decidability of bisimulation equivalence for normed pushdown processes
• Title not available (Why is that?)
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
• Bisimulation equivalence and regularity for real-time one-counter automata
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Bisimulation collapse and the process taxonomy
• Selected Ideas Used for Decidability and Undecidability of Bisimilarity
• Deciding Bisimilarity of Full BPA Processes Locally
• Deciding the bisimilarity of context-free session types
• Complexity of deciding bisimilarity between normed BPA and normed BPP
• Normed BPA vs. Normed BPP Revisited
• Polymorphic higher-order context-free session types
• Decidability of branching bisimulation on normed commutative context-free processes
• System \(F^\mu_\omega\) with context-free session types
• Basic process algebra with deadlocking states
• Expansive-Bisimulation for Context-Free Processes
• Bisimilarity on basic parallel 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)