Grammatical inference based on hyperedge replacement: a summary

As a fundamental goal of pattern generation and recognition, one wants to find syntactic descriptions for certain types or sets of patterns in such a way that automatic generation or recognition of the patterns is provided. The types or sets of patterns, that are of interest, may not be known completely, but only by some samples. A grammatical-inference algorithm is introduced which constructs hyperedge replacement grammars from sets of patterns that are represented by undirected unlabelled graphs. Hyperedge replacement provides a context-free mode of rewriting on graphs and hypergraphs with nice structural, combinatoric and algorithmic properties. Essentially, the inference procedure iterates the application of an operation which decomposes hyperedge-replacement productions according to edge-disjoint coverings of the right-hand side of the productions. A characterization of all grammars that can be inferred from a set of samples and some further aspects are discussed.