Inductive Identification of Pattern Languages Restricted Substitutions

Abstract

ABSTRACT Angluin defined a pattern as a string containing variables, and the language generated by the pattern as the set of strings that result from uniform substitution of strings for the variables. She proved that the class of pattern languages is identifiable from text, and the class of one-variable pattern languages is efficiently identifiable. At first the definition of a pattern language seems arbitrary, but we give natural examples of languages that are similar to pattern languages. These examples differ from the original definition in that the strings that may be substituted for variables are not all of σ*, but are drawn from some “base language”.We prove that the class of one-variable patterns languages over a base language given by oracle is poly-time identifiable. We then go on to investigate inductive inference of one-variable pattern languages over an unknown base where the base language is assumed to be drawn from some identifiable class. We give a “Pumping Lemma” for solutions of equations between one-variable patterns. We demonstrate the utility of the Pumping Lemma by using it to prove some simple sufficient conditions for polynomial time identifiability from text. Finally we give a couple of examples of language classes that satisfy these conditions and hence are poly-time identifiable from text.