Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample
Summary :
We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.
- Publication
- IEICE TRANSACTIONS on Information Vol.E83-D No.4 pp.757-765
- Publication Date
- 2000/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Theory of Automata, Formal Language Theory
Authors
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, Etsuji TOMITA, Mitsuo WAKATSUKI, "Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 4, pp. 757-765, April 2000, doi: .
Abstract: We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_4_757/_p
Copy
@ARTICLE{e83-d_4_757,
author={Yasuhiro TAJIMA, Etsuji TOMITA, Mitsuo WAKATSUKI, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample},
year={2000},
volume={E83-D},
number={4},
pages={757-765},
abstract={We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample
T2 - IEICE TRANSACTIONS on Information
SP - 757
EP - 765
AU - Yasuhiro TAJIMA
AU - Etsuji TOMITA
AU - Mitsuo WAKATSUKI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2000
AB - We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.
ER -
English
