Polynomial Time Learnability of Simple Deterministic Languages |
| |
Authors: | Ishizaka Hiroki |
| |
Affiliation: | (1) ICOT Research Center, 21F, Mita Kokusai Bldg., 1-4-28 Mita, Minato-ku, Tokyo, 108, Japan |
| |
Abstract: | This paper is concerned with the problem of learning simple deterministic languages. The algorithm described in this paper is based on the theory of model inference given by Shapiro. In our setting, however, nonterminal membership queries, except for the start symbol, are not permitted. Extended equivalence queries are used instead. Nonterminals that are necessary for a correct grammar and their intended models are introduced automatically. We give an algorithm that, for any simple deterministic language L, outputs a grammar G in 2-standard form, such that L = L(G), using membership queries and extended equivalence queries. We also show that the algorithm runs in time polynomial in the length of the longest counterexample and the number of nonterminals in a minimal grammar for L. |
| |
Keywords: | Language learning Polynomial time learning Simple deterministic languages Generating nonterminals |
本文献已被 SpringerLink 等数据库收录! |
|