Parameterized string correction decision problems investigate the possibility of transforming a given string X into a target string Y using a fixed number of edit operations, k. There are four possible edit operations: swap, delete, insert and substi- tute. In this work we consider the NP--complete STRING-TO-STRING CORREC- TION problem restricted to deletes and swaps and parameterized by the number of allowed operations. Specifically, the problem asks whether there exists a trans- formation from X into Y consisting of at most k deletes or swaps. We present a fixed parameter algorithm that runs in O(2k(k + m)), where m is the length of the destination string. Further, we present an implementation of an extended version of the algorithm that constructs the transformation sequence ! of length ay most k, given its existence. This thesis concludes with a discussion comparing the practical run times obtained from our implementation with the proposed theoretical results. Efficient string correction algorithms have applications in several areas, for example computational linguistics, error detection and correction, and computational biology. / Graduate

The StringToStringCorrection problem asks, given mutable string M, target string T, and positive integer k, can M be mutated into T using at most k operations (single symbol deletions or swaps of adjacent symbols) applied to M? The problem is known to be NP-complete. Abu-Khzam et al. give the first fixed-parameter algorithm for the problem when the parameter is the number of operations permitted. Their technique, charge and reduce, gives a O^∗(1.612k) bounded search tree algorithm, but leaves open whether a poly-size kernel exists. We show, using two polynomial time reduction rules on large regions of the input strings, that the problem has a problem kernel of size O(k^4). Our algorithm achieves this in a polynomial running time. Additionally, we introduce the problem k-MultiStringToStringCorrection (k-MS2SC), a generalized version of StringToStringCorrection, and prove it to be fixed-parameter tractable. / Graduate / 0984 / nwatt@uvic.ca

String-to-String Correction is the process of transforming some mutable string M into an exact copy of some other string (the target string T), using a shortest sequence of well-defined edit operations. The formal STRING-TO-STRING CORRECTION problem asks for the optimal solution using just two operations: symbol deletion, and swap of adjacent symbols. String correction problems using only swaps and deletions are computationally interesting; in his paper On the Complexity of the Extended String-to-String Correction Problem (1975), Robert Wagner proved that the String-to-String Correction problem under swap and deletion operations only is NP-complete for unbounded alphabets. In this thesis, we present the first careful examination of the binary-alphabet case, which we call Binary String-to-String Correction (BSSC). We present several special cases of BSSC for which an optimal solution can be found in polynomial time; in particular, the case where T and M have an equal number of occurrences of a given symbol has a polynomial-time solution. As well, we demonstrate and prove several properties of BSSC, some of which do not necessarily hold in the case of String-to-String Correction. For instance: that the order of operations is irrelevant; that symbols in the mutable string, if swapped, will only ever swap in one direction; that the length of the Longest Common Subsequence (LCS) of the two strings is monotone nondecreasing during the execution of an optimal solution; and that there exists no correlation between the effect of a swap or delete operation on LCS, and the optimality of that operation. About a dozen other results that are applicable to Binary String-to-String Correction will also be presented. / Graduate / 0984 / 0715 / tspreen@gmail.com