Learning regular tree languages with positive samples and queries

Jérôme Besombes (1) , Jean-Yves Marion (1)

1 CALLIGRAMME - Linear logic, proof networks and categorial grammars

We present an efficient learning algorithm IRTL for the class of regular tree languages. IRTL is based on the learner-theacher paradigm and works in quadratic time. The teacher give a characteristic sample of an unknown language L to the learner who tries to construct a minimal automata for L with help of queries. These queries are membership questions to the theacher. We give a proof of his correctness and terminaison and develop a full example.

Mots clés: grammatical inference; regular tree language; positifs samples; langage régulier d'arbre; exemples positifs; paradigme professeur/enseignant; learner/teacher paradigm; inférence grammaticale

Domaines: Autre [cs.OH]

Jérôme Besombes, Jean-Yves Marion. Learning regular tree languages with positive samples and queries. [Intern report] A02-R-201 || besombes02a, 2002, 10 p. ⟨inria-00101062⟩