{"id":15000,"date":"2022-06-16T19:40:20","date_gmt":"2022-06-16T23:40:20","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15000"},"modified":"2022-06-16T19:40:20","modified_gmt":"2022-06-16T23:40:20","slug":"tr-194-string-editing-with-substitution-insertion-deletion-squashing-and-expansion-operations","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-194-string-editing-with-substitution-insertion-deletion-squashing-and-expansion-operations\/","title":{"rendered":"TR-194: String Editing with Substitution, Insertion, Deletion, Squashing and Expansion Operations"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-194<\/strong>
\nSeptember 1991<\/p>\n

String Editing with Substitution, Insertion, Deletion, Squashing and Expansion Operations<\/h2>\n
B. John Oommen<\/div>\n
\n

Abstract<\/h3>\n

Let X and Y be any two strings of finite length. The problem of transforming X to Y using the edit operations of substitution, deletion and insertion has been extensively studied in the literature [l, 2, 6-11, 13, 15, 16, 18-21]. The problem can be solved in quadratic time if the edit operations are extended to include the operation of transposition of adjacent characters [24], but is generally reckoned to be NP-Hard if the transposition of arbitrary characters is permitted. In this paper we consider the problem of editing X to Y when the set of edit operations is extended to include the squashing and expansion operations. Whereas in the squashing operation two (or more) contiguous characters of X can be transformed into a single character of Y, in the expansion operation a single character in X may be expanded into two or more contiguous characters of Y. These operations are typically found in the recognition of cursive script. A quadratic time solution to the problem has been presented. We conjecture that this solution is optimal for the infinite alphabet case. The technique to compute the sequence of edit operations is also presented.<\/p>\n<\/div>\n

TR-194.pdf<\/a><\/p>\n