Charge and reduce

A fixed-parameter algorithm for String-to-String Correction

Faisal Abu Khzam, Henning Fernau, M Langston, S Lee-Cultura, Ulrike Stege

Research output: Contribution to journalArticleResearchpeer-review

Abstract

String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NPcomplete String-to-String Correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string x into string y with at most k operations on x, where permitted operations are single-character deletions and adjacent character exchanges. We prove that String-to-String Correction is fixedparameter tractable, for parameter k, and present a simple fixed-parameter algorithm that solves the problem in O(2kn) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is O(1.6181kn).
Original languageEnglish
Pages (from-to)41-49
Number of pages9
JournalDiscrete Optimization
Volume8
Issue number1
DOIs
Publication statusPublished - 2011
Externally publishedYes

Fingerprint

Fixed-parameter Algorithms
Strings
Charge
Speech recognition
Transform
Error-correcting Codes
Computational Biology
Search Trees
Tree Algorithms
Parsing
Speech Recognition
Deletion
Search Algorithm
Adjacent

Cite this

Abu Khzam, Faisal ; Fernau, Henning ; Langston, M ; Lee-Cultura, S ; Stege, Ulrike. / Charge and reduce : A fixed-parameter algorithm for String-to-String Correction. In: Discrete Optimization. 2011 ; Vol. 8, No. 1. pp. 41-49.
@article{4cc0754df73e47c4a5ba57bf60dffbfb,
title = "Charge and reduce: A fixed-parameter algorithm for String-to-String Correction",
abstract = "String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NPcomplete String-to-String Correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string x into string y with at most k operations on x, where permitted operations are single-character deletions and adjacent character exchanges. We prove that String-to-String Correction is fixedparameter tractable, for parameter k, and present a simple fixed-parameter algorithm that solves the problem in O(2kn) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is O(1.6181kn).",
author = "{Abu Khzam}, Faisal and Henning Fernau and M Langston and S Lee-Cultura and Ulrike Stege",
year = "2011",
doi = "10.1016/j.disopt.2010.10.003",
language = "English",
volume = "8",
pages = "41--49",
journal = "Discrete Optimization",
issn = "1572-5286",
publisher = "Elsevier",
number = "1",

}

Abu Khzam, F, Fernau, H, Langston, M, Lee-Cultura, S & Stege, U 2011, 'Charge and reduce: A fixed-parameter algorithm for String-to-String Correction', Discrete Optimization, vol. 8, no. 1, pp. 41-49. https://doi.org/10.1016/j.disopt.2010.10.003

Charge and reduce : A fixed-parameter algorithm for String-to-String Correction. / Abu Khzam, Faisal; Fernau, Henning; Langston, M; Lee-Cultura, S; Stege, Ulrike.

In: Discrete Optimization, Vol. 8, No. 1, 2011, p. 41-49.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Charge and reduce

T2 - A fixed-parameter algorithm for String-to-String Correction

AU - Abu Khzam, Faisal

AU - Fernau, Henning

AU - Langston, M

AU - Lee-Cultura, S

AU - Stege, Ulrike

PY - 2011

Y1 - 2011

N2 - String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NPcomplete String-to-String Correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string x into string y with at most k operations on x, where permitted operations are single-character deletions and adjacent character exchanges. We prove that String-to-String Correction is fixedparameter tractable, for parameter k, and present a simple fixed-parameter algorithm that solves the problem in O(2kn) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is O(1.6181kn).

AB - String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NPcomplete String-to-String Correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string x into string y with at most k operations on x, where permitted operations are single-character deletions and adjacent character exchanges. We prove that String-to-String Correction is fixedparameter tractable, for parameter k, and present a simple fixed-parameter algorithm that solves the problem in O(2kn) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is O(1.6181kn).

U2 - 10.1016/j.disopt.2010.10.003

DO - 10.1016/j.disopt.2010.10.003

M3 - Article

VL - 8

SP - 41

EP - 49

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

IS - 1

ER -