<テクニカルレポート>
Which Classes of Elementary Formal Systems Are Polynomial-Time Learnable?

作成者
本文言語
出版者
発行日
収録物名
出版タイプ
アクセス権
概要 Elementary formal systems (EFSs) are investigated with respect to polynomialtime learnability. First we show the polynomial-time learnability of the class LB-REFS(m, k) of languages definable by lengt...h-bounded hereditary EFSs with at most m clauses each of whose head contains at most k variable occurrences, where m and k are arbitrarily fixed positive integers. This result gives an interesting series of polynomial-time learnable classes of EFS-languages. Then we show that the class of regular pattern languages is not polynomial-time learnable under the assumption of RP,fNP although the class of pattern languages has been already known to be not polynomial-time learnable under reasonable assumptions. This result suggests that it is natural to restrict the number k of variable occurrences in the definition of LB-H-EFS( m, k ). We also discuss some related problems.続きを見る

本文ファイル

pdf rifis-tr-cs-37 pdf 1.26 MB 5  

詳細

レコードID
査読有無
タイプ
登録日 2024.02.09
更新日 2024.02.09