Containment Problems for Pattern Languages

Yasuhito MUKOUCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.4   pp.420-425
Publication Date: 1992/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)
Category: 
Keyword: 
pattern language,  containment,  generalization,  decision problem,  

Full Text: PDF(474.9KB)
>>Buy this Article


Summary: 
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.