IEICE TRANSACTIONS on Information
An Efficient Learning Algorithm for Regular Pattern Languages Using One Positive Example and a Linear Number of Membership Queries
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
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
