{"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":"2026-06-09T10:08:35","modified_gmt":"2026-06-09T14:08:35","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":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-194: String Editing with Substitution, Insertion, Deletion, Squashing and Expansion Operations\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/\">Technical Report<\/a>&nbsp;<strong>TR-194<\/strong><br>September 1991<\/p>\n\n\n\n<h2 id=\"string-editing-with-substitution-insertion-deletion-squashing-and-expansion-operations\" class=\"wp-block-heading\">String Editing with Substitution, Insertion, Deletion, Squashing and Expansion Operations<\/h2>\n\n\n\n<p>B. John Oommen<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>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\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-194.pdf\">TR-194.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-194September 1991 String Editing with Substitution, Insertion, Deletion, Squashing and Expansion Operations B. John Oommen Abstract 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, [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11908,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-15000","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15000","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=15000"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15000\/revisions"}],"predecessor-version":[{"id":24516,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15000\/revisions\/24516"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11908"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=15000"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15000"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}