文章基本信息

标题：Exact Learning of Regular Pattern Languages from One Positive Example Using a Linear Number of Membership Queries
本地全文：下载
作者：Satoshi Matsumoto ; Tomoyuki Uchida ; Takayoshi Shoudai 等
期刊名称：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