Name
Abstract | ||
|---|---|---|
A graph grammar is a generative description of a graph language (a possibly infinite set of graphs). In this paper, we present a novel algorithm for inducing a graph grammar from a given set of 'positive' and 'negative' graphs. The algorithm is guaranteed to produce a grammar that can generate all of the positive and none of the negative input graphs. Driven by a heuristic specific-to-general search process, the algorithm tries to find a small grammar that generalizes beyond the positive input set. During the search, the algorithm employs a graph grammar parser to eliminate the candidate grammars that can generate at least one negative input graph. We validate our method by inducing grammars for chemical structural formulas and flowcharts and thereby show its potential applicability to chemical engineering and visual programming. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-34176-2_12 | AGTIVE |
Keywords | Field | DocType |
chemical structural formula,positive input set,small grammar,chemical engineering,graph grammar parser,graph language,negative input graph,graph grammar,novel algorithm,graph grammar induction,candidate grammar,parser-controlled heuristic search process,heuristic search | Link grammar,Attribute grammar,Line graph,Graph property,Computer science,Algorithm,Theoretical computer science,Null graph,Generative grammar,Graph (abstract data type),Mildly context-sensitive grammar formalism | Conference |
Citations | PageRank | References |
2 | 0.35 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luka Fürst | 1 | 19 | 2.72 |
| Marjan Mernik | 2 | 3256 | 154.23 |
| Viljan Mahnič | 3 | 42 | 2.31 |