A short proof of the decidability of bisimulation for normed BPA- processes
From MaRDI portal
Publication:1198053
DOI10.1016/0020-0190(92)90142-IzbMath0779.68029OpenAlexW2008587618MaRDI QIDQ1198053
Publication date: 16 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(92)90142-i
formal semanticsdecidabilitycontext-free processesbasic progress algebradecidability of bisimulation
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Semantics in the theory of computing (68Q55)
Related Items (16)
A note on the complexity of deciding bisimilarity of normed unary processes ⋮ A generic framework for checking semantic equivalences between pushdown automata and finite-state automata ⋮ Infinite results ⋮ Bisimulation collapse and the process taxonomy ⋮ The complexity of bisimilarity-checking for one-counter processes. ⋮ Deciding Bisimilarity of Full BPA Processes Locally ⋮ On deciding some equivalences for concurrent processes ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ Decidability of Weak Bisimilarity for a Subset of BPA ⋮ 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 ⋮ A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ Reflections on a Geometry of Processes
Cites Work
This page was built for publication: A short proof of the decidability of bisimulation for normed BPA- processes
