| 作成者 |
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
The present paper deals with the problem of finding a consistent one-variable pattern from incomplete positive and negative examples. The studied problems are called an extension, a consistent extensi...on and a robust extension, denoted by E, CE and RE, respectively. The E corresponds an ordinary decision problem of finding a consistent one-variable patterns for given positive and negative examples. On the other hand, an example string is allowed to contain some unsettled symbols that is potentially matching with every constant symbol. For CE, we must settle a suitable assignment for these symbols as well as we must find a one-variable pattern consistent with the examples w.r.t the assignment. The RE requires more universal consistency, i.e., a correct one-variable pattern must be consistent with the examples w.r.t every assignment. The decision problems are closely connected with the learnability of one-variable pattern languages from positive and negative examples. Then, we estimate the computational complexity of the problems.続きを見る
|
Mendeley出力
trcs149.ps
trcs149