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 An error occured whilst processing this directive