Minimal Multiple Generalization for Unions of Pattern Languages
Hiroki Arimura, Takeshi Shinohara, Setsuko Otsuki, Hiroki Arilnura, Takeshi Shiliohara, 説乎 大槻 · QIR (Kyushu University Institutional Repository) (Kyushu University) · 1993
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. 1