Title: Learning node label controlled graph grammars: Extended abstract
Authors: Costa Florencio, Cristovao #
Issue Date: 2008
Publisher: Springer-Verlag
Series Title: Grammatical inference: Algorithms and applications vol:LNAI 5278 pages:286-288
Conference: International Colloquium on Grammatical Inference edition:9 location:St Malo, Britanny, France date:22-24 September 2008
Abstract: Within the data mining community, there has been a lot of interest the last few years in mining and learning from graphs. Most work in this area has been of a pragmatic nature, and has focussed on finding algorithms that help solve real-world problems reasonably well, without too much concern for more fundamental issues like learnability properties.
This kind of work also tends not to be informed by graph grammar theory, even though some approaches aim at inducing grammars from collections of graphs.

This paper is intended as a step towards an approach that is theoretically more sound. We present results concerning learnable classes of graph grammars. We consider identification in the limit from positive data only, from both derivation trees and graphs.

We show that, by imposing certain bounds on the complexity of grammars, a class of derivation trees is obtained that has finite elasticity, which implies learnability. Using an existing invariance result for finite elasticity, this class
is extended to a richer family of classes learnable just from graphs.

Algorithmic and complexity issues are briefly discussed.
ISBN: 978-3-540-88008-0
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
# (joint) last author

Files in This Item:
File Description Status SizeFormat
costafl_abstr_final.pdf Published 64KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.