{"id":15010,"date":"2022-06-16T19:50:02","date_gmt":"2022-06-16T23:50:02","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15010"},"modified":"2022-06-16T19:50:02","modified_gmt":"2022-06-16T23:50:02","slug":"tr-199-constrained-tree-editing","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-199-constrained-tree-editing\/","title":{"rendered":"TR-199: Constrained Tree Editing"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-199<\/strong>
\nDecember 1991<\/p>\n

Constrained Tree Editing<\/h2>\n
B. John Oommen & William Lee<\/div>\n
\n

Abstract<\/h3>\n

The distance between two ordered labeled trees is considered to be the minimum sum of the weights associated with the edit operations (insertion, deletion, and substitution) required to transform one tree to another. The problem of computing this distance and the optimal transformation using no edit constraints has been studied in the literature [3,4,7,8,9,11]. In this paper, we consider the problem of transforming one tree T1 to another tree T2 using any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm to compute this constrained distance is presented. If for a tree T, Span(T) is defined as the Min {Depth(T), Leaves(T)}, the time and space complexities of this algorithm are:<\/p>\n

Time: O(IT1l * IT2l * (Min{IT1I, IT21})2 * Span(T1) * Span(T2)) Space : O(IT1I * IT2I * Min{IT1I, IT2I}).<\/p>\n<\/div>\n

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