Fusion grammars are a novel approach to the generation of hypergraph languages. A fusion grammar is a hypergraph grammar which provides a start hypergraph of small connected components. To get large connected hypergraphs, they can be copied multiple times and can be fused by the application of fusion rules. In this paper, we analyze the non-emptiness problem for connection-preserving fusion grammars and show that this is an NP complete problem. We show this by relating language generation by connection-preserving fusion grammars to some variant of integer linear programming.
展开▼
