IEICE TRANSACTIONS on Information
Teachability of a Subclass of Simple Deterministic Languages
Summary :
We show teachability of a subclass of simple deterministic languages. The subclass we define is called stack uniform simple deterministic languages. Teachability is derived by showing the query learning algorithm for this language class. Our learning algorithm uses membership, equivalence and superset queries. Then, it terminates in polynomial time. It is already known that simple deterministic languages are polynomial time query learnable by context-free grammars. In contrast, our algorithm guesses a hypothesis by a stack uniform simple deterministic grammar, thus our result is strict teachability of the subclass of simple deterministic languages. In addition, we discuss parameters of the polynomial for teachability. The “thickness” is an important parameter for parsing and it should be one of parameters to evaluate the time complexity.
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.12 pp.2733-2742
- Publication Date
- 2013/12/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.2733
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Yasuhiro TAJIMA
Okayama Prefectural 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
Yasuhiro TAJIMA, "Teachability of a Subclass of Simple Deterministic Languages" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 12, pp. 2733-2742, December 2013, doi: 10.1587/transinf.E96.D.2733.
Abstract: We show teachability of a subclass of simple deterministic languages. The subclass we define is called stack uniform simple deterministic languages. Teachability is derived by showing the query learning algorithm for this language class. Our learning algorithm uses membership, equivalence and superset queries. Then, it terminates in polynomial time. It is already known that simple deterministic languages are polynomial time query learnable by context-free grammars. In contrast, our algorithm guesses a hypothesis by a stack uniform simple deterministic grammar, thus our result is strict teachability of the subclass of simple deterministic languages. In addition, we discuss parameters of the polynomial for teachability. The “thickness” is an important parameter for parsing and it should be one of parameters to evaluate the time complexity.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.2733/_p
Copy
@ARTICLE{e96-d_12_2733,
author={Yasuhiro TAJIMA, },
journal={IEICE TRANSACTIONS on Information},
title={Teachability of a Subclass of Simple Deterministic Languages},
year={2013},
volume={E96-D},
number={12},
pages={2733-2742},
abstract={We show teachability of a subclass of simple deterministic languages. The subclass we define is called stack uniform simple deterministic languages. Teachability is derived by showing the query learning algorithm for this language class. Our learning algorithm uses membership, equivalence and superset queries. Then, it terminates in polynomial time. It is already known that simple deterministic languages are polynomial time query learnable by context-free grammars. In contrast, our algorithm guesses a hypothesis by a stack uniform simple deterministic grammar, thus our result is strict teachability of the subclass of simple deterministic languages. In addition, we discuss parameters of the polynomial for teachability. The “thickness” is an important parameter for parsing and it should be one of parameters to evaluate the time complexity.},
keywords={},
doi={10.1587/transinf.E96.D.2733},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - Teachability of a Subclass of Simple Deterministic Languages
T2 - IEICE TRANSACTIONS on Information
SP - 2733
EP - 2742
AU - Yasuhiro TAJIMA
PY - 2013
DO - 10.1587/transinf.E96.D.2733
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2013
AB - We show teachability of a subclass of simple deterministic languages. The subclass we define is called stack uniform simple deterministic languages. Teachability is derived by showing the query learning algorithm for this language class. Our learning algorithm uses membership, equivalence and superset queries. Then, it terminates in polynomial time. It is already known that simple deterministic languages are polynomial time query learnable by context-free grammars. In contrast, our algorithm guesses a hypothesis by a stack uniform simple deterministic grammar, thus our result is strict teachability of the subclass of simple deterministic languages. In addition, we discuss parameters of the polynomial for teachability. The “thickness” is an important parameter for parsing and it should be one of parameters to evaluate the time complexity.
ER -
English
