{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:30:33Z","timestamp":1742927433902,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540958901"},{"type":"electronic","value":"9783540958918"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-540-95891-8_12","type":"book-chapter","created":{"date-parts":[[2009,1,22]],"date-time":"2009-01-22T01:19:21Z","timestamp":1232587161000},"page":"93-104","source":"Crossref","is-referenced-by-count":2,"title":["Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes"],"prefix":"10.1007","author":[{"given":"Taku","family":"Aratsu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kouichi","family":"Hirata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tetsuji","family":"Kuboyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.ipl.2006.06.002","volume":"100","author":"T. Akutsu","year":"2006","unstructured":"Akutsu, T.: A relationship between edit distance for ordered trees and edit distance for Euler strings. Inform. Proc. Let.\u00a0100, 105\u2013109 (2006)","journal-title":"Inform. Proc. Let."},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/11940128_11","volume-title":"Algorithms and Computation","author":"T. Akutsu","year":"2006","unstructured":"Akutsu, T., Fukagawa, D., Takasu, A.: Approximating tree edit distance through string edit distance. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 90\u201399. Springer, Heidelberg (2006)"},{"key":"12_CR3","unstructured":"Aratsu, T., Hirata, K., Kuboyama, T.: Sibling distance for rooted ordered trees. In: Proc.\u00a0ALSIP 2008, Working Notes of PAKDD Workshops, pp. 101\u2013112 (2008)"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P. Bille","year":"2005","unstructured":"Bille, P.: A survey on tree edit distance and related problems. Theoret. Comput. Sci.\u00a0337, 217\u2013239 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-540-73420-8_15","volume-title":"Automata, Languages and Programming","author":"E.D. Demaine","year":"2007","unstructured":"Demaine, E.D., Mozes, S., Rossman, B., Weimann, O.: An optimal decomposition algorithm for tree edit distance. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 146\u2013157. Springer, Heidelberg (2007)"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1145\/1061318.1061326","volume":"30","author":"M. Garofalakis","year":"2006","unstructured":"Garofalakis, M., Kumar, A.: XML stream processing using tree-edit distance embedding. ACM Trans. Database System\u00a030, 279\u2013332 (2006)","journal-title":"ACM Trans. Database System"},{"key":"12_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1007\/978-3-540-24741-8_39","volume-title":"Advances in Database Technology - EDBT 2004","author":"K. Kailing","year":"2004","unstructured":"Kailing, K., Kriegel, H.-P., Sch\u00f6nauer, S., Seidl, T.: Efficient similarity search for hierarchical data in large databases. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., B\u00f6hm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol.\u00a02992, pp. 676\u2013693. Springer, Heidelberg (2004)"},{"key":"12_CR8","series-title":"Fundamental algorithms","volume-title":"The art of computer programing","author":"D.E. Knuth","year":"1997","unstructured":"Knuth, D.E.: The art of computer programing, 3rd edn. Fundamental algorithms, vol.\u00a01. Addison-Wesley, Reading (1997)","edition":"3"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s00453-007-9028-3","volume":"42","author":"F. Magniez","year":"2007","unstructured":"Magniez, F., de Rougemont, M.: Property testing of regular tree languages. Algorithmica\u00a042, 127\u2013146 (2007)","journal-title":"Algorithmica"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Valiente, G.: An efficient bottom-up distance between trees. In: Proc. SPIRE 2001, pp. 212\u2013219 (2001)","DOI":"10.1109\/SPIRE.2001.989761"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Yang, R., Kalnis, P., Tung, A.K.H.: Similarity evaluation on tree-structed data. In: Proc. SIGMOD 2005, pp. 754\u2013765 (2005)","DOI":"10.1145\/1066157.1066243"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K. Zhang","year":"1989","unstructured":"Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput.\u00a018, 1245\u20131262 (1989)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2009: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-95891-8_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T08:22:17Z","timestamp":1558081337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-95891-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783540958901","9783540958918"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-95891-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}