Study on Inductive Learning Based on Positive Examples

模式是由常量符号和变量组成的字符串。模式的语言是通过用非空常量字符串替换模式中的变量而获得的常量字符串的集合。对于任何固定的k，已经证明了至多k个模式语言的并类可以从正数据中推断出来，我们应用模式语言的学习算法从氨基酸序列中发现一个基元。在字母表索引的帮助下，该算法仅从正例中成功地找到了可以被认为是基元的模式集。任意有限个模式语言的所有并的类都是不可推断的，因为任何常量字符串定义了一个由它自己组成的单元集，并且并类包含了所有有限语言。正确的模式是至少包含一个变量的模式。恰当模式的语言是无限的。在本文中，我们考虑了当模式被限制为素数时的并类，并证明了这类并是不可由正数据推断的。当模式被限制为不包含超过L连续出现的恒定符号时，对于某些L，并类被证明是可以从正数据推断的。

A pattern is a string consisting of constant symbols and variables. The language of a pattern is the set of constant strings obtained by substituting nonempty constant strings for variables in the pattern. For any fixed k, the class of unions of at most k pattern languages is already shown to be inferable from positive data.We apply a learning algorithm for pattern languages to discover a motif from amino-acid sequences. From only positive examples with the help of an alphsbet indexing, the algorithm succesfully finds sets of patterns, that can be considered as motifs.The class of all the unions of arbitrarily finitely many pattern languages in not inferable, because any constant string defines a singleton set consisting of itself, and the class of unions contains all the finite languages. A proper pattern is a pattern that contains at least one variable. The language of a proper pattern is infinite. In this paper, we consider the class of unions when patterns are restricted to be priper and show that the class is not inferable from positive data. When patterns are restricted not to contain more than l consecutive occurrences of constant symbols for some l, the class of unions is shown to be inferable from positive data.