Some Remarks on Weak Bisimilarity of BPA-Processes

Jitka Stribrna and Ivana Cerna


Abstract

The purpose of this work is to examine the decidability problem of weak bisimilarity for BPA-processes. It has been known that strong bisimilarity, which may be considered a special case of weak bisimilarity, where the internal (silent) action tau is treated equally to observable actions, is decidable for BPA-processes. There are two closely related approaches to semidecidability of strong equivalence: construction of a (finite) bisimulation or expansion tree and construction of a finite Caucal base. We have attempted to find out if any of these approaches could be generalized to semi-decide weak bisimilarity. Our findings indicate that a direct generalization is not sufficient and an efficient semi-decision procedure cannot be obtained in this way.