Groote, Jan Friso; Hüttel, Hans Undecidable equivalences for basic process algebra. (English) Zbl 0834.68069 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. Cited in 14 Documents MSC: 68Q55 Semantics in the theory of computing 68Q42 Grammars and rewriting systems Keywords:strong bisimilarity; normed BPA processes; context-free grammars Citations:Zbl 0826.68049 PDF BibTeX XML Cite \textit{J. F. Groote} and \textit{H. Hüttel}, Inf. Comput. 115, No. 2, 354--371 (1994; Zbl 0834.68069) Full Text: DOI Link OpenURL