Actions speak louder than words: proving bisimilarity for context-free processes

DOI10.1093/LOGCOM/8.4.485MaRDI QIDQ4209294zbMATH OpenOpenAlexFDO

Authors Hans Hüttel, Colin Stirling

Publication date 27 September 1998

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/8.4.485

zbMATH Keywords

bisimulation equivalencetableau decision methodgoal-directed rulesirredundant context-free grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Decidability of theories and sets of sentences (03B25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Bisimulation equivalence is decidable for all context-free processes
• scientific article; zbMATH DE number 4035115
• An elementary bisimulation decision procedure for arbitrary context-free processes
• Decidability of bisimulation equivalence for process generating context-free languages

Cited in

(17)

• Decidability of weak bisimilarity for a subset of BPA
• The complexity of bisimilarity-checking for one-counter processes.
• 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
• A short proof of the decidability of bisimulation for normed BPA- processes
• Decidability of bisimulation equivalence for normed pushdown processes
• A Coinductive Reformulation of Milner's Proof System for Regular Expressions Modulo Bisimilarity
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Deciding Bisimilarity of Full BPA Processes Locally
• Deciding the bisimilarity of context-free session types
• On deciding some equivalences for concurrent processes
• Silence is golden: Branching bisimilarity is decidable for context-free processes
• An elementary bisimulation decision procedure for arbitrary context-free processes
• Deciding Weak Bisimilarity of Normed Context-Free Processes Using Tableau
• Expansive-Bisimulation for Context-Free Processes
• Decidability of bisimulation equivalence for process generating context-free languages
• Regular strategies as proof tactics for \textsf{CIRC}

This page was built for publication: Actions speak louder than words: proving bisimilarity for context-free processes

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