Undecidable equivalences for basic process algebra

DOI10.1006/inco.1994.1101zbMath0834.68069OpenAlexW2003477691MaRDI QIDQ1342523

Hans Hüttel, Jan Friso Groote

Publication date: 16 February 1995

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/632b249a53dfb71562af0100ae937c4082badd27

zbMATH Keywords

context-free grammarsstrong bisimilaritynormed BPA processes

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Grammars and rewriting systems (68Q42)

Related Items (17)

A note on the complexity of deciding bisimilarity of normed unary processes ⋮ Undecidable equivalences for basic parallel processes ⋮ Nested semantics over finite trees are equationally hard ⋮ Infinite results ⋮ The complexity of bisimilarity-checking for one-counter processes. ⋮ Undecidability of domino games and hhp-bisimilarity. ⋮ The different shades of infinite session types ⋮ On deciding some equivalences for concurrent processes ⋮ Deciding bisimulation and trace equivalences for systems with many identical processes ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ On the computational complexity of bisimulation, redux ⋮ Pushdown automata, multiset automata, and Petri nets ⋮ Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems ⋮ Basic process algebra with deadlocking states ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ A NOTE ON LIMITED PUSHDOWN ALPHABETS IN STATELESS DETERMINISTIC PUSHDOWN AUTOMATA ⋮ Simulation preorder over simple process algebras

This page was built for publication: Undecidable equivalences for basic process algebra