Basic Process Algebra with Deadlocking States

• Authors: SRBA Jiří
• Year of publication: 2001
• Type: Article in Periodical
• Magazine / Source: Theoretical Computer Science
• MU Faculty or unit: Faculty of Informatics
• Field: Information theory
• Description: Bisimilarity and regularity are decidable properties for the class of BPA (or context--free) processes. We extend BPA with a deadlocking state obtaining BPA delta systems. We show that the BPA delta class is more expressive w.r.t. bisimilarity, but it remains language equivalent to BPA. We prove that bisimilarity and regularity remain decidable for BPAd delta. Finally we give a characterisation of those BPA delta processes that can be equivalently (up to bisimilarity) described within the ``pure'' BPA syntax.

Related projects

• Infinite state concurrent systems - models and verification
• Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing