On the complexity of the Extended String-to-String Correction Problem

ABSTRACT

The Extended String-to-String Correction Problem [ESSCP] is defined as the problem of determining, for given strings A and B over alphabet V, a minimum-cost sequence S of edit operations such that S(A) &equil; B. The sequence S may make use of the operations: Change, Insert, Delete and Swaps, each of constant cost WC, WI, WD, and WS respectively. Swap permits any pair of adjacent characters to be interchanged. The principal results of this paper are: (1) a brief presentation of an algorithm (the CELLAR algorithm) which solves ESSCP in time Ø(¦A¦* ¦B¦* ¦V¦s*s), where s &equil; min(4WC, WI+WD)/WS + 1; (2) presentation of polynomial time algorithms for the cases (a) WS &equil; 0, (b) WS > 0, WC&equil; WI&equil; WD&equil; @@@@; (3) proof that ESSCP, with WI < WC &equil; WD &equil; @@@@, 0 < WS < @@@@, suitably encoded, is NP-complete. (The remaining case, WS&equil; @@@@, reduces ESSCP to the string-to-string correction problem of [1], where an Ø( ¦A¦* ¦B¦) algorithm is given.) Thus, “almost all” ESSCP's can be solved in deterministic polynomial time, but the general problem is NP-complete.

REFERENCES

• 1: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 2: Robert A. Wagner , Roy Lowrance, An Extension of the String-to-String Correction Problem, Journal of the ACM (JACM), v.22 n.2, p.177-183, April 1975 [doi>10.1145/321879.321880]
• 3: Wagner, R. A. & Brown, T. P., "Swap-extended minimum edit distance correction for regular languages", Technical Report, Systems and Information Science Program, Vanderbilt University (January 1975).
• 4: Karp, R. M., "Reducibility among combinatorial problems" in Complexity of Computer Computations, Miller, R. E. & Thatcher, J. W. (ed.), Plenum Press (1972), pp. 85-104.
• 5: Wagner, R. A., "Generalized correction of context-free languages", Technical Report, Systems and Information Science Program, Vanderbilt Univeristy (1973).
• 6: Gaver, G. P. & Thompson, G. L., Mathematical Models: Programming and Probability (1966).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory