Fusion Grammars: A Novel Approach to the Generation of Graph Languages
2017
In this paper, we introduce the notion of fusion grammars as a novel device for the generation of (hyper)graph languages. Fusion grammars are motivated by the observation that many large and complex structures can be seen as compositions of a large number of small basic pieces. A fusion grammar is a hypergraph grammar that provides the small pieces as connected components of the start hypergraph. To get arbitrary large numbers of them, they can be copied multiple times. To get large connected hypergraphs, they can be fused by the application of fusion rules. As the first main results, we show that fusion grammars can simulate hyperedge replacement grammars that generate connected hypergraphs, that the membership problem is decidable, and that fusion grammars are more powerful than hyperedge replacement grammars.
Keywords:
- Combinatorics
- Tree-adjoining grammar
- Discrete mathematics
- Computer science
- L-attributed grammar
- Embedded pushdown automaton
- Graph rewriting
- Connected component
- Context-sensitive grammar
- Stochastic context-free grammar
- Context-free grammar
- Theoretical computer science
- Natural language processing
- Constraint graph
- Artificial intelligence
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
9
Citations
NaN
KQI