Undecidable Equivalences for Basic Process Algebra
Jan Friso Groote, Hans Hüttel, Edinburgh Univ. (United Kingdom). Lab. for Foundations of Computer Science · 1991
A recent theorem [3, 7, 19] shows that strong bisimilarity is decidable for the class of normed BPA processes, which correspond to a class of context-free grammars generating the ffl-free context-free languages. In [21] Huynh and Tian 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 [13] and show that none of them are decidable for normed BPA processes. 1 Introduction In the field of process theory much attention has been devoted to the study of process calculi and in particular to behavioural semantics for these calculi. A variety of equiv- Supported by the European Communities under RACE project no. 1046 (SPECS) and ESPRIT Basic Research Action 3006 (CONCUR).This paper was written during a visit of the first author to Edinburgh. y Supported via a position at Aalborg University and by the Danish Research Academy. 2 1 Introduction alences have been propose...