Learning tree languages from positive examples and membership queries

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 E 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 E.