期刊名称：Lecture Notes in Engineering and Computer Science
印刷版ISSN：2078-0958
电子版ISSN：2078-0966
出版年度：2019
卷号：2239
页码：204-209
出版社：Newswood and International Association of Engineers
摘要：A query learning model is an established mathematical
model of learning via queries in computational learning
theory. A regular pattern is a string consisting of constant
symbols and distinct variable symbols. The language of a
regular pattern is the set of all constant strings obtained by
replacing all variable symbols in the regular pattern with
constant strings. In a query learning model, it is known that
the class of languages of regular patterns is identifiable from
one positive example using a polynomial number of membership
queries. In this paper, we show that the class is identifiable from
one positive example using a linear number of membership
queries. This result means that the number of membership
queries is reduced to be linear with respect to the length of the
positive example.
关键词：pattern language; membership query; query;
learning; computational learning theory
