Shortest Common Supersequence (SCS)

From GM-RKB
Jump to navigation Jump to search

A Shortest Common Supersequence (SCS) is a string [math]\displaystyle{ S_1 }[/math] in a supersequence relation with every member of string set [math]\displaystyle{ S }[/math] and with no other string [math]\displaystyle{ (S_2\in S) }[/math] in a supersequence relation with the string set is shorter than [math]\displaystyle{ S_1 }[/math].



References

2019

  • (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Shortest_common_supersequence_problem Retrieved:2019-12-12.
    • In computer science, the shortest common supersequence of two sequences X and Y is the shortest sequence which has X and Y as subsequences. This is a problem closely related to the longest common subsequence problem. Given two sequences X = < x1,...,xm > and Y = < y1,...,yn >, a sequence U = < u1,...,uk > is a common supersequence of X and Y if items can be removed from U to produce X or Y.

      A shortest common supersequence (SCS) is a common supersequence of minimal length. In the shortest common supersequence problem, the two sequences X and Y are given and the task is to find a shortest possible common supersequence of these sequences. In general, an SCS is not unique.

      For two input sequences, an SCS can be formed from a longest common subsequence (LCS) easily. For example, if X [math]\displaystyle{ [1..m] = abcbdab }[/math] and Y [math]\displaystyle{ [1..n] = bdcaba }[/math], the lcs is Z [math]\displaystyle{ [1..r] = bcba }[/math] . By inserting the non-lcs symbols while preserving the symbol order, we get the SCS: U [math]\displaystyle{ [1..t] = abdcabdab }[/math] .

      It is quite clear that [math]\displaystyle{ r + t = m + n }[/math] for two input sequences. However, for three or more input sequences this does not hold. Note also, that the LCS and the SCS problems are not dual problems.

2007

  • (Westling, 2007) ⇒ Andreas Westling. (2007). “The Shortest Common Supersequence Problem." In: Andreas Westling's Webpage.
    • QUOTE: (...)
      • A sequence of length [math]\displaystyle{ n }[/math] is a concatenation of [math]\displaystyle{ n }[/math] symbols taken from an alphabet.
      • If [math]\displaystyle{ S }[/math] is a sequence of length [math]\displaystyle{ n }[/math] and [math]\displaystyle{ T }[/math] is a sequence of length [math]\displaystyle{ m }[/math] and [math]\displaystyle{ n \leq m }[/math] then [math]\displaystyle{ S }[/math] is a subsequence of [math]\displaystyle{ T }[/math] if [math]\displaystyle{ S }[/math] can be obtained by deleting [math]\displaystyle{ m-n }[/math] symbols from [math]\displaystyle{ T }[/math]. The symbols need not be contiguous.
      • A sequence [math]\displaystyle{ T }[/math] of length [math]\displaystyle{ m }[/math] is a supersequence of [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math] if [math]\displaystyle{ T }[/math] can be obtained by inserting [math]\displaystyle{ m-n }[/math] symbols. That is, [math]\displaystyle{ T }[/math] is a supersequence of [math]\displaystyle{ S }[/math] if and only if [math]\displaystyle{ S }[/math] is a subsequence of [math]\displaystyle{ T }[/math].
      • A sequence [math]\displaystyle{ T }[/math] is a common supersequence of the sequences [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_2 }[/math] of [math]\displaystyle{ T }[/math] is a supersequence of both [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_2 }[/math].
(...)

The problem is to find a shortest common supersequence (SCS), which is a common supersequence of minimal length. There could be more than one SCS for a given problem.

2002

1996

  1. Foulser, D. E., Li, M., & Yang, Q. (1992). Theory and algorithms for plan merging. Artificial Intelligence, 57(2-3), 143-181.
  2. Timkovskii, V. G. (1989). Complexity of common subsequence and supersequence problems and related problems. Cybernetics, 25(5), 565-580.

1993

1981

1978

  • (Garey & Johnson, 1979) ⇒ Michael R. Garey, and David S. Johnson (1979). “Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. pg.228.