zbMATH — the first resource for mathematics

Undecidable equivalences for basic process algebra. (English) Zbl 0834.68069
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.

68Q55 Semantics in the theory of computing
68Q42 Grammars and rewriting systems
Full Text: DOI