{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T13:51:55Z","timestamp":1742392315663},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[1988,6]]},"abstract":"<jats:p> This paper describes the computing alogrithms for the tree distance based on the structure preserving mapping. The distance is defined as the minimum sum of the weights of edit operations needed to transform tree T<jats:sub>\u03b1<\/jats:sub> to tree T<jats:sub>\u03b2<\/jats:sub> under restriction of the structure preserving mapping. The edit operations allow substituting a vertex of a tree to another, deleting a vertex of a tree and inserting a vertex to a tree. Proposed algorithms determine the distance between T\u03b1 and T<jats:sub>\u03b2<\/jats:sub> in time O(N<jats:sub>\u03b1<\/jats:sub>N<jats:sub>\u03b2<\/jats:sub>L<jats:sub>\u03b1<\/jats:sub>) or O(N<jats:sub>\u03b1<\/jats:sub>N<jats:sub>\u03b2<\/jats:sub>L<jats:sub>\u03b2<\/jats:sub>), and in space O(N<jats:sub>\u03b1<\/jats:sub>N<jats:sub>\u03b2<\/jats:sub>), where N<jats:sub>\u03b1<\/jats:sub>, N<jats:sub>\u03b2<\/jats:sub>, L<jats:sub>\u03b1<\/jats:sub> and L<jats:sub>\u03b2<\/jats:sub> are the number of vertices of T<jats:sub>\u03b1<\/jats:sub>, T<jats:sub>\u03b2<\/jats:sub>, the number of\u2019 leaves of T<jats:sub>\u03b1<\/jats:sub> and T<jats:sub>\u03b2<\/jats:sub>, respectively. The time complexity is close to the unapproachable lowest bound O(N<jats:sub>\u03b1<\/jats:sub>N<jats:sub>\u03b2<\/jats:sub>). Improved algorithms are presented. This tree distance can be applied to any problems including pattern recognition, syntactic tree comparison and classification, and tree comparison whose structures are important in structure preserving mapping. <\/jats:p>","DOI":"10.1142\/s0218001488000157","type":"journal-article","created":{"date-parts":[[2004,11,28]],"date-time":"2004-11-28T21:14:37Z","timestamp":1101676477000},"page":"221-240","source":"Crossref","is-referenced-by-count":37,"title":["THE TREE-TO-TREE EDITING PROBLEM"],"prefix":"10.1142","volume":"02","author":[{"given":"EIICHI","family":"TANAKA","sequence":"first","affiliation":[{"name":"Department of Information Science, Utsunomiya University 2753 Ishiimachi, Utsunomiya 321, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KEIKO","family":"TANAKA","sequence":"additional","affiliation":[{"name":"Department of Information Science, Utsunomiya University 2753 Ishiimachi, Utsunomiya 321, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["International Journal of Pattern Recognition and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218001488000157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:16:40Z","timestamp":1565129800000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001488000157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1988,6]]}},"alternative-id":["10.1142\/S0218001488000157"],"URL":"https:\/\/doi.org\/10.1142\/s0218001488000157","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"value":"0218-0014","type":"print"},{"value":"1793-6381","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,6]]}}}