Decidability of bisimulation equivalence for process generating context-free languages
From MaRDI portal
Publication:3140021
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
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
