INCLUSION PROBLEMS OF LANGUAGES GENERATED BY REGULAR PATTERNS AND CO-REGULAR PATTERNS
Mikiharu Terada · Scientiae mathematicae Japonicae · 2005
A pattern is a finite string consisting of constant symbols and variables. A pattern is regular if each variable appears in the pattern at most once. The language generated by a pattern is the set of constant strings obtained from the pattern by substituting nonempty strings for variables in the pattern. This paper deals with inclusion problems of unions or intersections of languages defined by regular patterns and co-regular patterns. The semantics of a co-pattern is defined by a particular subset of the complement of the original pattern language. We show the equivalence between the semantic inclusion and the syntactic inclusion. 1 Introduction. A pattern is a nonempty finite string consisting of constant symbols and variables. A pattern is regular if each variable appears in the pattern at most once. The language L(p) generated by a pattern p is the set of constant strings obtained from p by substituting nonempty constant strings for variables in p. The inclusion problem for pattern languages is shown to be undecidable (Jiang et al.(6)) and the membership problem is NP complete (Angluin (2)), while both problems for regular pattern languages are polynomial time computable (Shinohara (13)). The class PL of pattern languages has been introduced by Angluin (2) as a learnable class from positive examples in the Gold's framework (5). Pattern languages merely are not used for applications because of their simplicity. From a practical point of view, various kinds of languages generated by patterns have been investigated in Gold's framework, PAC learning and so on. Languages generated by decision trees over regular patterns are paid much attention in some practical applications such as genome informatics (Arikawa et al.(3)). The previous paper (17) due to the present author dealt with learning problem of decision trees over regular patterns with bounded depth from positive example. For each regular pattern p, we introduced a particular type of string p c called co-pattern of p, and defined its semantics as the subset of the complement L(p) c consisting of strings with lengths more than or equal to that of p. In terms of languages L(p)s and L(p c )s, we gave expressions for languages generated by decision trees, and showed the learnability of such decision trees from positive examples. In designing an efficient learning algorithm for decision trees over regular patterns, it is an important key to solve the inclusion problem for unions or intersections of regular pattern languages and co-regular pattern languages. In the present paper, we investigate such inclusion problems. We introduce two kinds of partially ordered syntactic relations on generalizations and instances of finite sets of patterns, and show the equivalence between the semantic inclusion and the syntactic inclu- sion, under some assumption of the cardinality of the alphabet. We obtain some results about relations between the semantic inclusion L(π1) ∩ L(π2) ⊆ L(τ1) ∪ L(τ2) and the syn- tactic inclusion for the pairs (π1 ,π 2) and (τ1 ,τ 2), where π1 ,π 2 ,τ 1 and τ2 are patterns or co-patterns.