Decidability of bisimulation equivalence for process generating context-free languages
From MaRDI portal
Publication:3140021
DOI10.1145/174130.174141zbMath0801.68102MaRDI QIDQ3140021
Jan A. Bergstra, Jos C. M. Baeten, Jan Willem Klop
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
process algebra; decidability; context-free grammars; context-free languages; bisimulation equivalence
68Q45: Formal languages and automata
68Q55: Semantics in the theory of computing
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Related Items
A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes, Pushdown automata, multiset automata, and Petri nets, Deciding bisimulation-like equivalences with finite-state processes, Linearization in parallel pCRL, 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, Nested semantics over finite trees are equationally hard, On the computational complexity of bisimulation, redux, Bisimilarity is not finitely based over BPA with interrupt, On the complexity of checking semantic equivalences between pushdown processes and finite-state processes, A note on an expressiveness hierarchy for multi-exit iteration, A complete equational axiomatization for MPA with string iteration, Decidability of bisimulation equivalence for normed pushdown processes, Context-free event domains are recognizable, A note on the complexity of deciding bisimilarity of normed unary processes, A polynomial algorithm for deciding bisimilarity of normed context-free processes, An equational axiomatization for multi-exit iteration, The complexity of bisimilarity-checking for one-counter processes., Effective decomposability of sequential behaviours, \(L(A)=L(B)\)? decidability results from complete formal systems, Algebraically complete semirings and Greibach normal form, A general approach to comparing infinite-state systems with their finite-state specifications, Decidable first-order transition logics for PA-processes, Selected Ideas Used for Decidability and Undecidability of Bisimilarity, A Context-Free Process as a Pushdown Automaton, On the Expressive Power of Restriction and Priorities in CCS with Replication, Unnamed Item
