The kappa-Lattice: Decidability Boundaries for Qualitative Analysis in Biological Languages
In CMSB 2009 volume 5684 of Lecture Notes in Bioinformatics, pages 158-172, 2009.
The k-calculus is a formalism for modelling molecular biology where molecules are terms with internal state and sites, bonds are represented by shared names labeling sites, and reactions are represented by rewriting rules. Depending on the shape of the rewriting rules, a lattice of dialects of k can be obtained. We analyze the expressive power of some of these dialects by focusing on the thin boundary between decidability and undecidability for problems like reachability and coverability.