On the Learnability of Erasing Pattern Languages in the Query Model

Authors: Steffen Lange and Sandra Zilles.

Source: Lecture Notes in Artificial Intelligence Vol. 2842, 2003, 129 - 143.

Abstract. A pattern is a finite string of constant and variable symbols. The erasing language generated by a pattern p is the set of all strings that can be obtained by substituting (possibly empty) strings of constant symbols for the variables in p.

The present paper deals with the problem of learning the erasing pattern languages and natural subclasses thereof within Angluin's model of learning with queries. The paper extends former studies along this line of research. It provides new results concerning the principal learning capabilities of query learners as well as the power and limitations of polynomial-time query learners.

In addition, the paper focusses on a quite natural extension of Angluin's original model. In this extended model, the query learner is allowed to query languages which are themselves not object of learning. Query learners of the latter type are often more powerful and more efficient than standard query learners. Moreover, when studying this new model in a more general context, interesting relations to Gold's model of language learning from only positive data have been elaborated.

©Copyright 2003 Springer