A short proof of the decidability of bisimulation for normed BPA- processes

DOI10.1016/0020-0190(92)90142-IMaRDI QIDQ1198053zbMATH OpenOpenAlexFDO

Authors Jan Friso Groote

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

zbMATH Keywords

basic progress algebracontext-free processesdecidabilitydecidability of bisimulationformal semantics

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Semantics in the theory of computing (68Q55)

Recommendations

• scientific article; zbMATH DE number 1231554
• Bisimulation equivalence is decidable for all context-free processes
• Undecidable equivalences for basic process algebra
• scientific article; zbMATH DE number 1701362
• Branching bisimilarity of normed BPA processes is in NExpTime

Cites work

• Actions speak louder than words: proving bisimilarity for context-free processes
• Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)
• Graphes canoniques de graphes algébriques
• scientific article; zbMATH DE number 4035115 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)

Cited in

(24)

• Decidability of bisimulation equivalence for normed pushdown processes
• A note on the complexity of deciding bisimilarity of normed unary processes
• The complexity of bisimilarity-checking for one-counter processes.
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Regularity of normed PA processes
• Deciding Bisimilarity of Full BPA Processes Locally
• scientific article; zbMATH DE number 1231554 (Why is no real title available?)
• scientific article; zbMATH DE number 1232246 (Why is no real title available?)
• A menagerie of non-finitely based process semantics over BPA* – from ready simulation to completed traces
• On deciding some equivalences for concurrent processes
• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
• Reflections on a Geometry of Processes
• Decidability of weak bisimilarity for a subset of BPA
• Algebra and Coalgebra in Computer Science
• Pushdown automata, multiset automata, and Petri nets
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• Basic process algebra with deadlocking states
• Infinite results
• Decidability of bisimulation equivalence for normed pushdown processes
• Bisimulation collapse and the process taxonomy
• Regularity is decidable for normed BPA and normed BPP processes in polynomial time
• Decidability results in automata and process theory
• Regularity is decidable for normed PA processes in polynomial time
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes

This page was built for publication: A short proof of the decidability of bisimulation for normed BPA- processes

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