<テクニカルレポート>
Minimal Multiple Generalization for Unions of Pattern languages

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 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.続きを見る

本文情報を非表示

rifis-tr-71 pdf 1.09 MB 68  

詳細

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