Result: Learning tree languages from positive examples and membership queries

Title:
Learning tree languages from positive examples and membership queries
Authors:
BESOMBES, Jérome, MARION, Jean-Yves
Source:
Algorithmic learning theoryTheoretical computer science. 382(3):183-197
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 30 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Divers, Miscellaneous, Intelligence artificielle, Artificial intelligence, Apprentissage et systèmes adaptatifs, Learning and adaptive systems, Algorithme, Algorithm, Algoritmo, Arbre minimal, Minimal tree, Arbol mínimo, Automate arbre, Tree automaton, Autómata árbol, Contrôle information, Information control, Control información, Convergence, Convergencia, Echantillon, Sample, Muestra, Entrée ordinateur, Input, Entrada ordenador, Equivalence, Equivalencia, Grammaire, Grammar, Gramática, Informatique théorique, Computer theory, Informática teórica, Inférence grammaticale, Grammatical inference, Inferencia gramatical, Langage rationnel, Regular language, Lenguaje racional, Mot, Word, Palabra, Oracle, Paradigme, Paradigm, Paradigma, Polynôme, Polynomial, Polinomio, Requête, Query, Pregunta documental, Transition, Transición, 05C05, 68Q42, 68Q45, 68T05, 68Wxx, Apprentissage exact, Exact learning, Apprentissage langage, Automate minimal, Interrogation appartenance, Langage L, Langage arbre, Langage régulier, Learning, Positive example, Queries, Regular tree language
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
ONERA, 29 avenue de la Division Leclerc, 92322 Châtillon, France
LORIA, 615, rue du jardin botanique, 54602 Villers-lès-Nancy, France
INPL-Ecole Nationale Supérieure des Mines de Nancy, Parc de Saurupt, 54042 Nancy, France
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=19034084
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.19034084
Database:
PASCAL Archive

Further Information

We investigate regular tree languages' exact learning from positive examples and membership queries. Input data are trees of the language to infer. The learner computes new trees from the inputs and asks the oracle whether or not they belong to the language. From the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. This paradigm was introduced by Angluin in the seminal work [D. Angluin, A note on the number of queries needed to identify regular languages, Information and Control 51 (1981) 76-87] for the case of regular word languages. Neither negative examples, equivalence queries nor counter-examples are allowed in this paradigm. We describe an efficient algorithm which is polynomial in the size of the examples for learning the whole class of regular tree languages. The convergence is ensured when the set of examples contains a representative sample of the language to guess. A finite subset £ of a regular tree language L is representative for L if every transition of the minimal tree automaton for L is used at least once for the derivation of an element of the set ε.