Characterization of Pattern Languages

Abstract

A pattern is a finite string of constant symbols and variable symbols. The language of a pattern is the set of all strings obtained by substituting any non-null constant string for each variable symbol in the pattern. A pattern language was introduced by Angluin in 1979 as a concrete class of languages which is inferable from positive data. In this paper, we consider the decision problem, whether for given two patterns there is a containment relation between their pattern languages, which was posed by Angluin and remains open. We give some sufficient conditions to make this problem decidable. We introduce the notions of a generalization, an instance, a minimal generalization and a maximal instance for a set of patterns. We also show that a set of patterns with a same length forms a lattice under the operations which take a minimal generalization and a maximal instance. Further, we characterize the above open problem using the minimal generalization.