Undecidable equivalences for basic process algebra. (English) Zbl 0834.68069

Groote, Jan Friso; Hüttel, Hans

Inf. Comput. 115, No. 2, 354-371 (1994).

Summary: A recent theorem shows that strong bisimilarity is decidable for the class of normed BPA processes, which correspond to a class of context- free grammars generating the \(\varepsilon\)-free context-free languages. D. T. Huynh and L. Tian [ibid. 117, No. 2, 193-205 (1995; Zbl 0826.68049)] have shown that readiness and failure equivalence are undecidable for BPA processes. In this paper we examine all other equivalences in the linear/branching time hierarchy and show that none of them are decidable for normed BPA processes.

MSC:

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

Keywords:

strong bisimilarity; normed BPA processes; context-free grammars