Skip to Main content Skip to Navigation
New interface
Conference papers

Learning Substitutable Binary Plane Graph Grammars

Abstract : While some heuristics exist for the learning of graph grammars, few has been done on the theoretical side. Due to complexity issues, the class of graphs has to be restricted: this paper deals with the subclass of plane graphs, which correspond to drawings of planar graphs. This allows us to introduce a new kind of graph grammars, using a face-replacement mechanism. To learn them, we extend recent successful techniques developed for string grammars, and based on a property on target languages: the substitutability property. We show how this property can be extended to plane graph languages and nally state the rst identi cation in the limit result for a class of graph grammars, as far as we know.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Rémi Eyraud Connect in order to contact the contributor
Submitted on : Tuesday, March 11, 2014 - 3:53:10 PM
Last modification on : Sunday, June 26, 2022 - 12:19:57 AM
Long-term archiving on: : Wednesday, June 11, 2014 - 12:51:12 PM


Files produced by the author(s)


  • HAL Id : hal-00958063, version 1



Rémi Eyraud, Jean-Christophe Janodet, Tim Oates. Learning Substitutable Binary Plane Graph Grammars. International Colloquium in Grammatical Inference, Sep 2012, College Park, United States. ⟨hal-00958063⟩



Record views


Files downloads