Splicing/Fusion Grammars and Their Relation to Hypergraph Grammars

摘要

In this paper, we introduce splicing/fusion grammars as a device for generating hypergraph languages. They generalize the formerly introduced notion of fusion grammars by adding splicing rules that split node sets into two node sets and equip them with complementary hyper-edges. As a result a derivation step in such a grammar is either a fusion of complementary hyperedges, a multiplication of a connected component or a splicing. We prove two main results demonstrating the generative power of splicing/fusion grammars. First, Chomsky grammars are transformed into splicing/fusion grammars where the transformation mimics a corresponding transformation of Chomsky grammars into splicing systems as studied in the context of DNA computing. Second, hypergraph grammars are transformed into splicing/fusion grammars.