| 作成者 |
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 概要 |
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.続きを見る
|
Mendeley出力
rifis-tr-cs-37