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.
Type de document :
Communication dans un congrès
International Colloquium in Grammatical Inference, Sep 2012, College Park, United States. 2012
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958063
Contributeur : Rémi Eyraud <>
Soumis le : mardi 11 mars 2014 - 15:53:10
Dernière modification le : jeudi 18 janvier 2018 - 02:08:21
Document(s) archivé(s) le : mercredi 11 juin 2014 - 12:51:12

Fichier

eyraud12a.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 2012. 〈hal-00958063〉

Partager

Métriques

Consultations de la notice

185

Téléchargements de fichiers

88