Identification of pattern languages from examples and queries (Q1097709)

Pattern languages are defined by \textit{D. Angluin} [J. Comput. Syst. Sci. 21, 46-62 (1980; Zbl 0454.68108)] as an abstract model of learning one- dimensional patterns. A pattern is defined to be a string of variables and constants, and its associated language is defined to be all constant strings obtained by substituting constant strings for variables in the pattern. The pattern-finding problem is to identify a mysterious pattern from examples of and queries about strings in the pattern language. This is a specific problem of the general theory of learning as publicized by \textit{L. G. Valiant} [Commun. ACM 27, 1134-1142 (1984; Zbl 0587.68077)]. The main difference is that this paper uses the worst-case model, while Valiant uses a probabilistic model. The main result of this paper states that the number of queries necessary to precisely identify a pattern could be bounded by a polynomial in the length of the pattern if the initial sample of strings in the pattern language satisfies certain structural properties. This property is found to be necessary also for patterns of only one variable.