作成者 |
|
|
|
本文言語 |
|
出版者 |
|
|
発行日 |
|
収録物名 |
|
巻 |
|
出版タイプ |
|
アクセス権 |
|
関連DOI |
|
|
関連URI |
|
|
関連情報 |
|
|
概要 |
The k-minimal multiple generalization (k-mmg) is a natural extension of the least generalization (lg) given by Plotkin in 1970. The k-ming generalizes given first order terms by at most k-terms, while... the 1g does by a single term. Thus, k-mmg gives a more precise approximation of a given set of examples. In this paper, we extend the algorithm for as more abstract class of objects by abstracting a generalization structure of first-order terms. We present a general design of a polynomial time k-mmg algorithm for the wider classes of objects, and prove the correctness. Using the algorithm, we prove the polynomial time inferability from positive data of unions of at most k languages in a subclass of pattern languages. One class is the class of one-variable pattern languages, and another is the class of regular pattern languages with a bounded number of variables. We also discuss the use of refinement operator and NC-learnability from positive data.続きを見る
|