Technical Reports

The report FIMU-RS-98-05

Comparing the Classes BPA and BPA with Deadlocks

by Jiøí Srba, This is a full version of the paper accepted to MFCS`98. June 1998, 36 pages.

FIMU-RS-98-05. Available as Postscript, PDF.

Abstract:

The class of BPA (or context-free) processes has been intensively studied and bisimilarity and regularity appeared to be decidable. We extend these processes with a deadlocking state into BPA_delta systems. We show that the BPA_delta class is more expressive w.r.t. bisimulation equivalence but it remains language equivalent to BPA. We prove that bisimilarity and regularity remain decidable in the BPA_delta class. Finally we give a characterisation of those BPA_delta processes which can be equivalently (up to bisimilarity) described within the "pure" BPA syntax.