Identification of Hyperedge-Replacement graph grammars

The last few years have seen an increasing interest in mining and learning from graphs. Most work in this area has aimed at finding approximate solutions to real-world problems, without much concern for more fundamental issues. This paper is intended as a step towards an approach that is theoretically more sound, by applying ideas from the field of grammar induction. We present results concerning the learning of hypergraph grammars. We consider identification in the limit from both derivation trees and graphs. We show that, by restricting the complexity of grammars, a learnable class of derivation languages is obtained. By exploiting a known invariance result this class is extended to a class that is learnable from hypergraphs.status: publishe