Abstract
The article examines polynomial-time and intractable longest common subsequence and subword problems and shortest common supersequence and superword problems, both old and new. The results provide a more complete complexity characterization of these problems. Some applications are discussed, as well as the dual problems of common nonsubwords, nonsuperwords, nonsubsequences, and nonsupersequences.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Literature Cited
M. R. Garey and D. S. Johnson, Computers and Intractability, Freeman, San Francisco (1979).
A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass. (1974).
M. L. Fredman, “On computing the length of the longest increasing subsequences,” Discr. Math.,11, No. 1, 29–36 (1975).
M. O. Dayhoff, “Computer aids to protein sequence determination,” J. Theor. Biol.,8, No. 1, 97–112 (1965).
M. O. Dayhoff, “Computer analysis of protein evolution,” Sci. Am.,221, No. 1, 86–95 (1969).
S. B. Needleman and C. S. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” J. Molec. Biol.,48, 443–453 (1970).
D. Sunkoff and R. J. Cedergren, “A test for nucleotide sequence homology,” J. Molec. Biol.,77, 159–164 (1973).
R. A. Wagner and M. J. Fischer, “The string-to-string correction problem,” J. ACM,21, No. 1, 168–173 (1974).
R. Lowrance and R. W. Wagner, “An extension of the string-to-string correction problem,” J. ACM,22, No. 2, 177–183 (1975).
M. Rodeh, V. R. Pratt, and S. Even, “Linear algorithm for data compression via string matching,” J. ACM,28, No. 1, 16–27 (1981).
S. Y. Lu and K. S. Fu, “A sentence-to-sentence clustering procedure for pattern analysis,” IEEE Trans. Syst. Man, Cybern., SMC-8, 381–389 (1978).
N. M. Kapustin, Development of Technological Parts Machining Processes by Computer [in Russian], Mashinostroenie, Moscow (1976).
K. Tempelhof and H. Lichtenberg, “Technological standardization as a prerequisite for computer-aided design of technological processes,” in: N. M. Kapustin (ed.), Computer-Aided Design of Technological Processes [in Russian], Mashinostroenie, Moscow (1985), pp. 109–153.
A. M. Basin, V. N. Balabolin, V. V. Kryukov, et al., “An interactive system for multilevel design of technological processes of flexible production,” Vestn. Mashinostr., No. 2, 42–44 (1987).
P. H. Sellers, “An algorithm for the distance between two finite sequences,” J. Combin. Theory,16, 253–258 (1974).
D. S. Hirschberg, “A linear space algorithm for computing maximal sequences,” Commun. ACM,18, No. 6, 341–343 (1975).
D. S. Hirschberg, “Algorithms for longest common subsequence problem,” J. ACM,24, No. 4, 664–675 (1977).
J. W. Hunt and T. G. Szymanski, “A fast algorithm for computing longest common subsequences,” Commun. ACM,20, No. 5, 350–353 (1977).
W. J. Masek and M. S. Paterson, “A faster algorithm computing string edit distance,” J. Comput. Syst., Sci.,20, 18–31 (1980).
N. Nakatsu, Y. Kambayashi, and S. Yajima, “A longest common subsequence algorithm suitable for similar text strings,” Acta Inf.,18, 171–179 (1982).
A. Mukhopadhyay, “A fast algorithm for longest-common-subsequence problem,” Inform. Sci.,20, 69–82 (1980)
C. K. Wong and A. K. Chandra, “Bounds for the string editing problem,” J. ACM,23, No. 1, 13–16 (1976).
L. Allison and T. I. Dix, “A bit-string longest-common-subsequence algorithm,” Inform. Process. Lett.,23, 305–310 (1986).
C. B. Yang and R. C. T. Lee, “The mapping of 2-D array processors to 1-D array processors,” Parallel Comput.,3, 217–229 (1986).
W. J. Hsu and M. W. Du, “New algorithms for LCS problem,” J. Comput. Syst. Sci.,29, No. 2, 133–152 (1984).
S. K. Kumar and C. P. Rangan, “A linear space algorithm for the LCS problem,” Acta Inf.,24, 353–362 (1987).
A. V. Aho, D. S. Hirschberg, and J. D. Ullman, “Bounds on the complexity of the longest common subsequence problem,” J. ACM,23, No. 1, 1–12 (1976).
D. Maier, “The complexity of some problems on subsequences and supersequences,” J. ACM,25, No. 2, 322–336 (1978).
Yu. V. Matiyasevich, “On real-time recognition of the inclusion relation,” Zap. Nauch. Sem. LOMI AN SSSR,20, 104–114 (1971).
P. Weiner, “Linear pattern matching algorithms,” IEEE 14th Ann. Symp. on Switching and Automata Theory (1973), pp. 1–11.
E. M. McCreight, “space-economical suffix tree construction algorithm,” J. ACM,23, 262–272 (1976).
Z. Galil, “String matching in real time,” J. ACM,28, No. 1, 134–146 (1981).
E. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms. Theory and Practice, Prentice-Hall, Englewood Cliffs, NJ (1977).
J. Gallant, D. Maier, and J. A. Storer, “On finding minimal length superstring,” J. Comput. Syst. Sci.,20, No. 1, 50–58 (1980).
M. Aigner, Combinatorial Theory, Springer, Berlin (1979).
C. Wrathall, “Complete sets and the polynomial-time hierarchy,” Theor. Comput. Sci.,3, 23–33 (1976).
A. Salomaa, Jewels of Formal Language Theory [Russian translation], Mir, Moscow (1986).
M. L. Gerver, “Three-valued numbers and digraphs,” Kvant., No. 2, 32–35 (1987).
Additional information
Translated from Kibernetika, No. 5, pp. 1–13, September–October, 1989.
Rights and permissions
About this article
Cite this article
Timkovskii, V.G. Complexity of common subsequence and supersequence problems and related problems. Cybern Syst Anal 25, 565–580 (1989). https://doi.org/10.1007/BF01075212
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01075212