The search functionality is under construction.

The search functionality is under construction.

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

Satoshi MATSUMOTO

Tokai University

Tomoyuki UCHIDA

Hiroshima City University

Takayoshi SHOUDAI

Kyushu International University

Yusuke SUZUKI

Hiroshima City University

Tetsuhiro MIYAHARA

Hiroshima City University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Satoshi MATSUMOTO, Tomoyuki UCHIDA, Takayoshi SHOUDAI, Yusuke SUZUKI, Tetsuhiro MIYAHARA, "An Efficient Learning Algorithm for Regular Pattern Languages Using One Positive Example and a Linear Number of Membership Queries" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 3, pp. 526-539, March 2020, doi: 10.1587/transinf.2019FCP0009.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019FCP0009/_p

Copy

@ARTICLE{e103-d_3_526,

author={Satoshi MATSUMOTO, Tomoyuki UCHIDA, Takayoshi SHOUDAI, Yusuke SUZUKI, Tetsuhiro MIYAHARA, },

journal={IEICE TRANSACTIONS on Information},

title={An Efficient Learning Algorithm for Regular Pattern Languages Using One Positive Example and a Linear Number of Membership Queries},

year={2020},

volume={E103-D},

number={3},

pages={526-539},

abstract={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.},

keywords={},

doi={10.1587/transinf.2019FCP0009},

ISSN={1745-1361},

month={March},}

Copy

TY - JOUR

TI - An Efficient Learning Algorithm for Regular Pattern Languages Using One Positive Example and a Linear Number of Membership Queries

T2 - IEICE TRANSACTIONS on Information

SP - 526

EP - 539

AU - Satoshi MATSUMOTO

AU - Tomoyuki UCHIDA

AU - Takayoshi SHOUDAI

AU - Yusuke SUZUKI

AU - Tetsuhiro MIYAHARA

PY - 2020

DO - 10.1587/transinf.2019FCP0009

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E103-D

IS - 3

JA - IEICE TRANSACTIONS on Information

Y1 - March 2020

AB - 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.

ER -