Compactness and Learning of Classes of Unions of Erasing Regular Pattern Languages

Abstract

A regular pattern is a string of constant symbols and distinct variables. A semantics of a set P of regular patterns is a union L ( P ) of erasing pattern languages generated by patterns in P . The paper deals with the class RP^ k of sets of at most k regular patterns, and an efficient learning from positive examples of the language class defined by RP^ k . In efficient learning languages, the complexity for the MINL problem to find one of minimal languages containing a given sample is one of very important keys. Arimura et al.[ 5 ] introduced a notion of compactness w.r.t. containment for more general framework, called generalization systems, than RP^ k of language description which guarantees the equivalency between the semantic containment L(P) ⫅ L(Q) and the syntactic containment P ⊑ Q , where ⊑ is a syntactic subsumption over the generalization systems. Under the compactness, the MINL problem reduces to finding one of minimal sets in RP ^ k for a given sample under the subsumption ⊑. They gave an efficient algorithm to find such minimal sets under the assumption of compactness and some conditions. We first show that for each k ≥ 1, the class RP ^ k has compactness if and only if the number of constant symbols is greater than k +1. Moreover, we prove that for each P ∈, RP ^ k , a finite subset S _2( P ) is a characteristic set of L ( P ) within the class, where S _2( P ) consists of strings obtained from P by substituting strings with length two for each variable. Then our class RP ^ k is shown to be polynomial time inferable from positive examples using the efficient algorithm of the MINL problem due to Arimura et al.[ 5 ], provided the number of constant symbols is greater than k + 1.