
For FullText 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.

An Efficient Learning Algorithm for Regular Pattern Languages Using One Positive Example and a Linear Number of Membership Queries
Satoshi MATSUMOTO Tomoyuki UCHIDA Takayoshi SHOUDAI Yusuke SUZUKI Tetsuhiro MIYAHARA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E103D
No.3
pp.526539 Publication Date: 2020/03/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2019FCP0009
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —) Category: Keyword: pattern language, membership query, query learning, computational learning theory,
Full Text: PDF(1.1MB)>>
Summary:
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 nonempty strings. The present paper deals with the learning problem of languages of regular patterns within Angluin's query learning model, which is an established mathematical model of learning via queries in computational learning theory. The class of languages of regular patterns was known to be identifiable from one positive example using a polynomial number of membership queries, in the query learning model. In present paper, we show that the class of languages of regular patterns is identifiable from one positive example using a linear number of membership queries, with respect to the length of the positive example.

