<テクニカルレポート>
Inductive Inference of Monotonic Formal Systems from Positive Data

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 A formal system is a finite set of expressions, such as a grammar or a Prolog program. A semantic mapping from formal systems to concepts is said to be monotonic if it maps larger formal systems to la...rger concepts. A formal system $ Gamma $ is said to be reduced with respect to a finite set X if the concept defined by $ Gamma $ contains X but the concepts defined by any proper subset $ Gamma $ of $ Gamma $ cannot contain some part of X. Assume a semantic mapping is monotonic and formal systems consisting of at most n expressions that are reduced with respect to X can define only finitely many concepts for any finite set X and any n. Then, the class of concepts defined by formal systems consisting of at most n expressions is shown to be inferable from positive data. As corollaries, the class of languages defined by length-bounded elementary formal systems consisting of at most n axioms, the class of languages generated by context-sensitive grammars consisting of at most n productions, and the class of minimal models of linear Prolog programs consisting of at most n definite clauses are all shown to be inferable from positive data.続きを見る

本文情報を非表示

rifis-tr-29 pdf 964 KB 87  

詳細

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