For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Containment Problems for Pattern Languages
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/07/25
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)
pattern language, containment, generalization, decision problem,
Full Text: PDF(474.9KB)>>
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 nonnull constant string for each variable symbol in the pattern. The class of pattern languages was introduced by Angluin in 1979 as a concrete class 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 languages, which was posed by Angluin and its decidability remains open. We give some sufficient conditions to make this problem decidable. We also introduce the notions of generalizations and minimal generalizations common to a set of patterns. We characterize the above open problem using the minimal generalization.