Decidability of bisimulation equivalence for normed pushdown processes

DOI10.1007/3-540-61604-7_57zbMath1514.68183OpenAlexW4244180300MaRDI QIDQ6104375

Colin Stirling

Publication date: 28 June 2023

Published in: CONCUR '96: Concurrency Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61604-7_57

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (10)

Bisimulation equivalence is decidable for one-counter processes ⋮ The equivalence problem for deterministic pushdown automata is decidable ⋮ Bisimulation collapse and the process taxonomy ⋮ Pushdown automata, multiset automata, and Petri nets ⋮ Ensuring completeness of symbolic verification methods for infinite-state systems ⋮ A general theory of action languages ⋮ Complete formal systems for equivalence problems ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ Model checking of systems with many identical timed processes ⋮ Decidability of bisimilarity for one-counter processes.

Cites Work

• On the regular structure of prefix rewriting
• 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
• The equivalence problem for real-time strict deterministic languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Decidability of bisimulation equivalence for normed pushdown processes