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

DOI10.1093/LOGCOM/8.4.485zbMath0904.68129OpenAlexW2147830331MaRDI QIDQ4209294

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) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42)

Related Items (12)

A generic framework for checking semantic equivalences between pushdown automata and finite-state automata ⋮ The complexity of bisimilarity-checking for one-counter processes. ⋮ A Coinductive Reformulation of Milner's Proof System for Regular Expressions Modulo Bisimilarity ⋮ Deciding Bisimilarity of Full BPA Processes Locally ⋮ On deciding some equivalences for concurrent processes ⋮ A short proof of the decidability of bisimulation for normed BPA- processes ⋮ Decidability of Weak Bisimilarity for a Subset of BPA ⋮ On the complexity of checking semantic equivalences between pushdown processes and finite-state processes ⋮ Silence is golden: Branching bisimilarity is decidable for context-free processes ⋮ Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ Regular Strategies as Proof Tactics for CIRC

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