String noninclusion optimization problems

作     者：Rubinov, AR Timkovsky, VG 

作者机构：Natl Transport Inst Moscow Russia Russian Acad Sci Econ Forecasting Inst Dept Comp Sci Moscow 117418 Russia 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1998年第11卷第3期

页      面：456-467页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：string inclusion longest shortest common subsequence substring supersequence superstring polynomial-time algorithm NP-hard problem 

摘      要：For every string inclusion relation there are two optimization problems: find a longest string included in every string of a given finite language, and find a shortest string including every string of a given finite language. As an example, the two well-known pairs of problems, the 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 problems connected with string noninclusion relations: find a shortest string included in no string of a given finite language and find a longest string including no string of a given finite language. The predicate string alpha is not included in string beta is interpreted as either alpha is not a substring of beta or alpha is not a subsequence of beta. The main purpose is to determine the complexity status of the string noninclusion optimization problems. Using graph approaches we present polynomial-time algorithms for the first interpretation and NP-hardness proofs for the second. We also discuss restricted versions of the problems, correlations between the string inclusion and noninclusion problems, and generalized problems which are the string inclusion problems for one language and the string noninclusion problems for another. In applications the string inclusion problems are used to find a similarity between any structures which can be represented by strings. 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. The above generalized problems arise naturally in all of these applied areas. Apart from this practical reason, we hope that studying the string noninclusion problems will yield deeper understanding of the string inclusion problems.