The search functionality is under construction.
The search functionality is under construction.

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

  • Full Text Views

    0

  • Cite this

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.

Publication
IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.526-539
Publication Date
2020/03/01
Publicized
2019/12/23
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

Authors

Satoshi MATSUMOTO
  Tokai University
Tomoyuki UCHIDA
  Hiroshima City University
Takayoshi SHOUDAI
  Kyushu International University
Yusuke SUZUKI
  Hiroshima City University
Tetsuhiro MIYAHARA
  Hiroshima City University

Keyword