Learning Substitutable Binary Plane Graph Grammars

Rémi Eyraud, Jean-Christophe Janodet, Tim Oates
Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:114-128, 2012.

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 finally state the first identification in the limit result for a class of graph grammars, as far as we know.

Cite this Paper

BibTeX
@InProceedings{pmlr-v21-eyraud12a, title = {Learning Substitutable Binary Plane Graph Grammars}, author = {Eyraud, Rémi and Janodet, Jean-Christophe and Oates, Tim}, booktitle = {Proceedings of the Eleventh International Conference on Grammatical Inference}, pages = {114--128}, year = {2012}, editor = {Heinz, Jeffrey and Higuera, Colin and Oates, Tim}, volume = {21}, series = {Proceedings of Machine Learning Research}, address = {University of Maryland, College Park, MD, USA}, month = {05--08 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v21/eyraud12a/eyraud12a.pdf}, url = {https://proceedings.mlr.press/v21/eyraud12a.html}, 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 finally state the first identification in the limit result for a class of graph grammars, as far as we know.} }
Endnote
%0 Conference Paper %T Learning Substitutable Binary Plane Graph Grammars %A Rémi Eyraud %A Jean-Christophe Janodet %A Tim Oates %B Proceedings of the Eleventh International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2012 %E Jeffrey Heinz %E Colin Higuera %E Tim Oates %F pmlr-v21-eyraud12a %I PMLR %P 114--128 %U https://proceedings.mlr.press/v21/eyraud12a.html %V 21 %X 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 finally state the first identification in the limit result for a class of graph grammars, as far as we know.
RIS
TY - CPAPER TI - Learning Substitutable Binary Plane Graph Grammars AU - Rémi Eyraud AU - Jean-Christophe Janodet AU - Tim Oates BT - Proceedings of the Eleventh International Conference on Grammatical Inference DA - 2012/08/16 ED - Jeffrey Heinz ED - Colin Higuera ED - Tim Oates ID - pmlr-v21-eyraud12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 21 SP - 114 EP - 128 L1 - http://proceedings.mlr.press/v21/eyraud12a/eyraud12a.pdf UR - https://proceedings.mlr.press/v21/eyraud12a.html AB - 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 finally state the first identification in the limit result for a class of graph grammars, as far as we know. ER -
APA
Eyraud, R., Janodet, J. & Oates, T.. (2012). Learning Substitutable Binary Plane Graph Grammars. Proceedings of the Eleventh International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 21:114-128 Available from https://proceedings.mlr.press/v21/eyraud12a.html.

Related Material