An elementary bisimulation decision procedure for arbitrary context-free processes

DOI10.1007/3-540-60246-1_148zbMath1193.68172OpenAlexW1555553717MaRDI QIDQ3569030

Bernhard Steffen, Olaf Burkart, 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)

Related Items

Bisimulation equivalence and regularity for real-time one-counter automata, A generic framework for checking semantic equivalences between pushdown automata and finite-state automata, Never-stop context-free learning, Infinite results, Bisimulation collapse and the process taxonomy, The complexity of bisimilarity-checking for one-counter processes., Equivalence of pushdown automata via first-order grammars, Complexity of deciding bisimilarity between normed BPA and normed BPP, Selected Ideas Used for Decidability and Undecidability of Bisimilarity, Deciding Bisimilarity of Full BPA Processes Locally, Normed BPA vs. Normed BPP Revisited, Deciding the Bisimilarity of Context-Free Session Types, Decidability of Weak Bisimilarity for a Subset of BPA, Weak bisimilarity and regularity of context-free processes is EXPTIME-hard, On the computational complexity of bisimulation, redux, Pushdown automata, multiset automata, and Petri nets, On the complexity of checking semantic equivalences between pushdown processes and finite-state processes, Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time, Basic process algebra with deadlocking states, Decidability of bisimulation equivalence for normed pushdown processes, Bisimilarity on basic parallel processes