Finding patterns common to a set of strings (Extended Abstract)
Dana Angluin · 1979
We motivate, formalize, and study a computational problem in concrete inductive inference. A “pattern” is defined to be a concatenation of constants and variables, and the language of a pattern is defined to be the set of strings obtained by substituting constant strings for the variables. The problem we consider is, given a set of strings, find a minimal pattern language containing this set. This problem is shown to be effectively solvable in the general case and to lead to correct inference in the limit of the pattern languages. There exists a polynomial time algorithm for it in the restricted case of one-variable patterns. Inference from positive data is re-examined, and a characterization given of when it is possible for a family of recursive languages. Various collateral results about patterns and pattern languages are obtained.