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.E103-D   No.3   pp.526-539
Publication Date: 2020/03/01
Online ISSN: 1745-1361
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)>>
Buy this Article




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 non-empty 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.