HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
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

https://hal.inria.fr/hal-00958063
Contributor : Rémi Eyraud Connect in order to contact the contributor
Submitted on : Tuesday, March 11, 2014 - 3:53:10 PM
Last modification on : Tuesday, June 30, 2020 - 11:56:08 AM
Long-term archiving on: : Wednesday, June 11, 2014 - 12:51:12 PM

File

eyraud12a.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00958063, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

149

Files downloads

76