<テクニカルレポート>
Language Learning with Characteristic Examples and Membership Queries

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 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.続きを見る

本文情報を非表示

rifis-tr-108 pdf 726 KB 106  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2017.01.20