A polynomial-time algorithm for learning k-variable pattern languages from examples
Michael J. Kearns, Leonard Pitt · 1989
In this paper we give, for each constant k, a polynomial-time algorithm for learning the class of k-variable pattern languages in the learning model introduced by Valiant [?]. A pattern is a string of constant and variable symbols, for instance the 3-variable pattern p = 10x1x2x21x300x1. The associated language L(p) is obtained by substituting for each variable in the pattern any constant