Learning Tree Languages from Positive Examples and Membership Queries

Jérôme Besombes 1 Jean-Yves Marion 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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 to 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 [1] for the case of regular word language. 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 insured when the set of examples contains a representative sample of the language to guess.
Type de document :
Communication dans un congrès
Shai Ben-David and John Case and Akira Maruoka. 15th international conference on Algorithmic Learning Theory - ALT'2004, 2004, Padova, Italy, Springer, 3244, pp.440-453, 2004, Lecture notes in Artificial Intelligence
Liste complète des métadonnées

https://hal.inria.fr/inria-00101084
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:55:57
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00101084, version 1

Collections

Citation

Jérôme Besombes, Jean-Yves Marion. Learning Tree Languages from Positive Examples and Membership Queries. Shai Ben-David and John Case and Akira Maruoka. 15th international conference on Algorithmic Learning Theory - ALT'2004, 2004, Padova, Italy, Springer, 3244, pp.440-453, 2004, Lecture notes in Artificial Intelligence. 〈inria-00101084〉

Partager

Métriques

Consultations de la notice

116