Undecidable Equivalences for Basic Parallel Processes

Hans Hüttel

Abstract: Recent results show that strong bisimilarity is decidable for the class of Basic Parallel Processes (BPP), which corresponds to the subset of CCS definable using recursion, action prefixing, nondeterminism and the full merge operator. In this paper we examine all other equivalences in the linear/branching time hierarchy and show that none of them are decidable for BPP.

LFCS report ECS-LFCS-93-276

This report is available in the following formats:

Previous | Index | Next