Bonding Grammars

We introduce bonding grammars, a graph grammar formalism developed to model DNA computation. It is a modification of fusion grammars introduced by Kreowski, Kuske and Lye in 2017. Bonding is a graph transformation that consists of merging two hyperedges into a single larger one. We show why bonding models DNA pairing better than fusion. Then, we investigate properties of bonding grammars. First, we study the relationship between bonding grammars and hyperedge replacement grammars proving that the classes of languages generated by them are incomparable. Secondly, we prove that bonding grammars naturally generalise regular sticker systems. Finally, we prove that the membership problem for bonding grammars is NP-complete.