| 作成者 |
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
This paper introduces the notion of characteristic examples for languages and shows that the notion contributes to language learning in polynomial time. A characteristic example of a language L is a s...tring of L which includes, in a sense, sufficient information to represent the language L. We show that any context-free language can be divided into a finite set of languages each of which has a characteristic example. We prove that it is solvable whether or not a context-free language has a characteristic example. Then, we propose a learning model with membership queries and characteristic examples for the class of parenthesis languages. We prove that, for this class, our learning algorithm runs in a polynomial time in the size of a minimal parenthesis grammar which generates the target language and in the length of a longest characteristic example given to the algorithm.続きを見る
|
Mendeley出力
rifis-tr-108