Decidability of bisimulation equivalence for normed pushdown processes

DOI10.1016/S0304-3975(97)00216-8zbMath0915.68119OpenAlexW2118539487MaRDI QIDQ1276237

Colin Stirling

Publication date: 20 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00216-8

zbMATH Keywords

bisimulation equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Linearly bounded infinite graphs ⋮ The complexity of bisimilarity-checking for one-counter processes. ⋮ Selected Ideas Used for Decidability and Undecidability of Bisimilarity ⋮ 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 ⋮ Decidability of DPDA equivalence ⋮ Deciding bisimulation-like equivalences with finite-state processes ⋮ Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems ⋮ On the complexity of checking semantic equivalences between pushdown processes and finite-state processes ⋮ Bisimulation-based Non-deterministic Admissible Interference and its Application to the Analysis of Cryptographic Protocols

Cites Work

• On the regular structure of prefix rewriting
• Recursive process definitions with the state operator
• The theory of ends, pushdown automata, and second-order logic
• A short proof of the decidability of bisimulation for normed BPA- processes
• Undecidable equivalences for basic process algebra
• Bisimulation equivalence is decidable for all context-free processes
• Decidability of bisimulation equivalence for process generating context-free languages
• Graphes canoniques de graphes algébriques
• An elementary bisimulation decision procedure for arbitrary context-free processes
• The equivalence problem for real-time strict deterministic languages
• Actions speak louder than words: proving bisimilarity for context-free processes
• Infinite results
• Bisimulation collapse and the process taxonomy
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item