On Reachability and Spatial Reachability in Fragments of BioAmbients | Zendy

Giorgio Delzanno | Zendy; Roberto Montagna | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On Reachability and Spatial Reachability in Fragments of BioAmbients

Author(s) -

Giorgio Delzanno,

Roberto Montagna

Publication year - 2007

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2007.05.008

Subject(s) - reachability , petri net , decidability , merge (version control) , computer science , theoretical computer science , commutative property , reachability problem , concurrency , rewriting , algorithm , programming language , mathematics , discrete mathematics , information retrieval

BioAmbients is a powerful model for representing various aspects of living cells. The model provides a rich set of operations for the movement and interaction of molecules. The richness of the language motivates the study of dialects of the full model and the comparison with other computational models. In this paper we investigate the limit between decidability and undecidability of two decision problems, namely reachability and spatial reachability, for semantic and syntactic fragments of BioAmbients providing movement capabilities and merge. Our results illustrate the power of merge with respect to the other movement operations of BA for properties like reachability. Furthermore, they establish an interesting connection between BioAmbients and other computational models like associative-commutative term rewriting and Petri nets with transfer arcs

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research