Decidability of bisimulation equivalence for process generating context-free languages

DOI10.1145/174130.174141zbMath0801.68102OpenAlexW2142944765MaRDI QIDQ3140021

Jan Willem Klop, Jan A. Bergstra, Jos C. M. Baeten

Publication date: 9 December 1993

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/174130.174141

zbMATH Keywords

process algebradecidabilitycontext-free grammarscontext-free languagesbisimulation equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semantics in the theory of computing (68Q55) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

A note on the complexity of deciding bisimilarity of normed unary processes ⋮ A polynomial algorithm for deciding bisimilarity of normed context-free processes ⋮ Bisimilarity is not finitely based over BPA with interrupt ⋮ An equational axiomatization for multi-exit iteration ⋮ Nested semantics over finite trees are equationally hard ⋮ Axiomatizations for the perpetual loop in process algebra ⋮ A generic framework for checking semantic equivalences between pushdown automata and finite-state automata ⋮ Infinite results ⋮ The complexity of bisimilarity-checking for one-counter processes. ⋮ Equivalence of pushdown automata via first-order grammars ⋮ Unnamed Item ⋮ Selected Ideas Used for Decidability and Undecidability of Bisimilarity ⋮ A Context-Free Process as a Pushdown Automaton ⋮ Unnamed Item ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ Deciding the Bisimilarity of Context-Free Session Types ⋮ Decidability of Weak Bisimilarity for a Subset of BPA ⋮ On the computational complexity of bisimulation, redux ⋮ Pushdown automata, multiset automata, and Petri nets ⋮ Deciding bisimulation-like equivalences with finite-state processes ⋮ Algebraically complete semirings and Greibach normal form ⋮ Linearization in parallel pCRL ⋮ On the complexity of checking semantic equivalences between pushdown processes and finite-state processes ⋮ A general approach to comparing infinite-state systems with their finite-state specifications ⋮ Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time ⋮ Non-regular iterators in process algebra ⋮ Basic process algebra with deadlocking states ⋮ On the Expressive Power of Restriction and Priorities in CCS with Replication ⋮ Unnamed Item ⋮ A note on an expressiveness hierarchy for multi-exit iteration ⋮ A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes ⋮ A complete equational axiomatization for MPA with string iteration ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ Bisimilarity on basic parallel processes ⋮ Context-free event domains are recognizable ⋮ Effective decomposability of sequential behaviours ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ Decidable first-order transition logics for PA-processes ⋮ Model-Checking Games for Typed λ-Calculi ⋮ Reflections on a Geometry of Processes ⋮ Regular Strategies as Proof Tactics for CIRC