Connexion

English version

PPS UMR 7126 – Laboratoire
Preuves, Programmes et Systèmes

Accueil · Présentation · Membres · Publications · Séminaire · Groupes de travail · Projets · πr²

22/1/09 Cosimo Laneve (Univ. Bologna),

Reachability analysis in the k-family

The $\Kappa$-calculus is a formalism for modelling molecular biology where molecules are terms with internal states and with sites, bonds are represented by shared names labelling sites, and reactions are represented by rewriting rules. Depending on the shape of the rewrite rules, several dialects of the calculus can be obtained. We analyze the expressive power of some of these dialects by focusing on the thin boundary between decidability and undecidabiity for problems like reachability and coverability. This analysis is a first step towards the design of algorithms for the qualitative analysis of languages of the $\Kappa$-family.