STRING NONINCLUSION OPTIMIZATION PROBLEMS

For every string inclusion relation there are two optimization problem s: find a longest string included in every string of a given finite la nguage, and find a shortest string including every string of a given f inite language. As an example, the two well-known pairs of problems, t he longest common substring (or subsequence) problem and the shortest common superstring (or supersequence) problem, are interpretations of these two problems. In this paper we consider a class of opposite prob lems connected with string noninclusion relations: find a shortest str ing included in no string of a given finite language and find a longes t string including no string of a given finite language. The predicate ''string alpha is not included in string beta'' is interpreted as eit her ''alpha is not a substring of beta'' or ''alpha is not a subsequen ce of beta''. The main purpose is to determine the complexity status o f the string noninclusion optimization problems. Using graph approache s we present polynomial-time algorithms for the first interpretation a nd NP-hardness proofs for the second. We also discuss restricted versi ons of the problems, correlations between the string inclusion and non inclusion problems, and generalized problems which are the string incl usion problems for one language and the string noninclusion problems f or another. In applications the string inclusion problems are used to find a similarity between any structures which can be represented by s trings. Respectively, the noninclusion problems can be used to find a nonsimilarity. Such problems occur in computational molecular biology, data compression, pattern recognition, and flexible manufacturing. Th e above generalized problems arise naturally in all of these applied a reas. Apart from this practical reason, we hope that studying the stri ng noninclusion problems will yield deeper understanding of the string inclusion problems.