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

(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
• Decidability of bisimulation equivalence for normed pushdown processes
• Infinite results
• scientific article; zbMATH DE number 4035115 (Why is no real title available?)
• 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
• Expansive-Bisimulation for Context-Free Processes
• Basic process algebra with deadlocking states
• 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)