Undecidable Equivalence for Basic Process Algebra

Hans Hüttell and J F Groote

Abstract: A recent theorem shows that strong bisimilarity is decidable for the class of normed BPA processes, which correspond to context-free grammars. 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 and show that none of them are decidable for normed BPA processes.

LFCS report ECS-LFCS-91-169

This report is available in the following formats:

Previous | Index | Next