The Tree-to-Tree Correction Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

The Tree-to-Tree Correction Problem

Full text

Pdf (612 KB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 3 (July 1979) table of contents

Pages: 422 - 433

Year of Publication: 1979

ISSN:0004-5411

Author

Kuo-Chung Tai

Department of Computer Science, North Carolina State University, P O Box 5972, Raleigh, NC

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 217, Citation Count: 73

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322139.322143 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. D. Ullman , A. V. Aho , D. S. Hirschberg, Bounds on the Complexity of the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.23 n.1, p.1-12, Jan. 1976 [doi>10.1145/321921.321922]
	2	Fu, K S, AND BHARGAVA, B K Tree systems for syntactic pattern recogmtlon IEEE Trans Comptrs C-22, 12 (Dec 1973), 1087-1099
	3	D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
	4	Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977 [doi>10.1145/322033.322044]
	5	James W. Hunt , Thomas G. Szymanski, A fast algorithm for computing longest common subsequences, Communications of the ACM, v.20 n.5, p.350-353, May 1977 [doi>10.1145/359581.359603]
	6	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	7	Robert A. Wagner , Roy Lowrance, An Extension of the String-to-String Correction Problem, Journal of the ACM (JACM), v.22 n.2, p.177-183, April 1975 [doi>10.1145/321879.321880]
	8	SANKO~F, D Matching sequences under deletlonAnsertlon constraints Proc Nat Aead Scl USA 69, 1 (Jan 1974), 4-6
	9	SELKOW, S M The tree-to-tree editing problem inform Processing Letters 6, 6 (Dec 1977), 184-186
	10	SELLERS, P H An algorithm for the d~stance between two fimte sequences J Combm Theory, Set A, 16 (1974), 253-258
	11	Kuo-Chung Tai, Syntactic error correction in programming languages., 1977
	12	Robert A. Wagner, On the complexity of the Extended String-to-String Correction Problem, Proceedings of seventh annual ACM symposium on Theory of computing, p.218-223, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803771]
	13	Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
	14	C. K. Wong , Ashok K. Chandra, Bounds for the String Editing Problem, Journal of the ACM (JACM), v.23 n.1, p.13-16, Jan. 1976 [doi>10.1145/321921.321923]

CITED BY 74

	Tamás Horváth , Stefan Wrobel , Uta Bohnebeck, Relational Instance-Based Learning with Lists and Terms, Machine Learning, v.43 n.1-2, p.53-80, April-May 2001
	B. John Oommen , Richard K.S. Loke, On the Pattern Recognition of Noisy Subsequence Trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.9, p.929-946, September 2001
	Mikio Aoyama, Metrics and analysis of software architecture evolution with discontinuity, Proceedings of the International Workshop on Principles of Software Evolution, May 19-20, 2002, Orlando, Florida
	Bernhard Westfechtel, Structure-oriented merging of revisions of software documents, Proceedings of the 3rd international workshop on Software configuration management, p.68-79, June 12-14, 1991, Trondheim, Norway
	Philip Klein , Srikanta Tirthapura , Daniel Sharvit , Ben Kimia, A tree-edit-distance algorithm for comparing simple, closed shapes, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.696-704, January 09-11, 2000, San Francisco, California, United States
	Alfredo Ferro , Giovanni Gallo , Rosalba Giugno , Alfredo Pulvirenti, Best-Match Retrieval for Structured Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.7, p.707-718, July 2001
	Cecilia Mascolo , Licia Capra , Wolfgang Emmerich, Mobile computing middleware, Advanced lectures on networking, Springer-Verlag New York, Inc., New York, NY, 2002
	Bin Ma , Lusheng Wang , Kaizhong Zhang, Computing similarity between RNA structures, Theoretical Computer Science, v.276 n.1-2, p.111-132, April 6, 2002
	Dirk Ohst , Michael Welle , Udo Kelter, Differences between versions of UML diagrams, ACM SIGSOFT Software Engineering Notes, v.28 n.5, September 2003
	Sachindra Joshi , Neeraj Agrawal , Raghu Krishnapuram , Sumit Negi, A bag of paths model for measuring structural similarity in Web documents, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Andrea Torsello , Edwin R. Hancock, Computing approximate tree edit distance using relaxation labeling, Pattern Recognition Letters, v.24 n.8, p.1089-1097, May 2003
	Serge Dulucq , Laurent Tichit, RNA Secondary structure comparison: exact analysis of the Zhang--Shasha tree edit algorithm, Theoretical Computer Science, v.306 n.1-3, p.471-484, 5 September 2003
	Jesper Jansson , Andrzej Lingas, A fast algorithm for optimal alignment between similar ordered trees, Fundamenta Informaticae, v.56 n.1,2, p.105-120, July 2003
	Jianwei Zhang , Bernd Rössler, Grasp learning by active experimentation using continuous B-spline model, Autonomous robotic systems: soft computing and hard computing methodologies and applications, Physica-Verlag GmbH, Heidelberg, Germany, 2003
	Peter Buneman , Sanjeev Khanna , Keishi Tajima , Wang-Chiew Tan, Archiving scientific data, ACM Transactions on Database Systems (TODS), v.29 n.1, p.2-42, March 2004
	J. T. -L. Wang , K. Zhang , K. Jeong , D. Shasha, A System for Approximate Tree Matching, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.559-571, August 1994
	Susan Horwitz, Identifying the semantic and textual differences between two versions of a program, ACM SIGPLAN Notices, v.25 n.6, p.234-245, Jun. 1990
	D. C. Reis , P. B. Golgher , A. S. Silva , A. F. Laender, Automatic web news extraction using tree edit distance, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA
	Pascal Ferraro , Christophe Godin, Optimal mappings with minimum number of connected components in tree-to-tree comparison problems, Journal of Algorithms, v.48 n.2, p.385-406, September 2003
	Matthias Höchsmann , Björn Voss , Robert Giegerich, Pure Multiple RNA Secondary Structure Alignments: A Progressive Profile Approach, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.53-62, January 2004
	Thomas B. Sebastian , Philip N. Klein , Benjamin B. Kimia, Recognition of Shapes by Editing Their Shock Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.5, p.550-571, May 2004
	S. B. Davidson , J. Crabtree , B. P. Brunk , J. Schug , V. Tannen , G. C. Overton , C. J. Stoeckert, Jr., K2/Kleisli and GUS: experiments in integrated access to genomic data sources, IBM Systems Journal, v.40 n.2, p.512-531, February 2001
	Eiichi Tanaka, A Metric Between Unrooted and Unordered Trees and its Bottom-Up Computing Method, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.12, p.1233-1238, December 1994
	Kiyoko F. Aoki , Nobuhisa Ueda , Atsuko Yamaguchi , Tatsuya Akutsu , Minoru Kanehisa , Hiroshi Mamitsuka, Managing and analyzing carbohydrate data, ACM SIGMOD Record, v.33 n.2, June 2004
	Cecilia Mascolo , Licia Capra , Stefanos Zachariadis , Wolfgang Emmerich, XMIDDLE: A Data-Sharing Middleware for Mobile Computing, Wireless Personal Communications: An International Journal, v.21 n.1, p.77-103, April 2002
	Raghu Sastry , N. Ranganathan, A VLSI Architecture for Approximate Tree Matching, IEEE Transactions on Computers, v.47 n.3, p.346-352, March 1998
	B. J. Oommen , K. Zhang , W. Lee, Numerical Similarity and Dissimilarity Measures Between Two Trees, IEEE Transactions on Computers, v.45 n.12, p.1426-1434, December 1996
	Lev Goldfarb, Metric data models and associated search strategies, ACM SIGIR Forum, v.20 n.1-4, p.7-11, Spring-Summer 1986
	Andrew Hogue , David Karger, Thresher: automating the unwrapping of semantic content from the World Wide Web, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Yanhong Zhai , Bing Liu, Web data extraction based on partial tree alignment, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Nikolaus Augsten , Michael Böhlen , Johann Gamper, Approximate matching of hierarchical data using pq-grams, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Julien Allali , Marie-France Sagot, A New Distance for High Level RNA Secondary Structure Comparison, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.1, p.3-14, January 2005
	James Bailey, Transformation and reaction rules for data on the web, Proceedings of the sixteenth Australasian database conference, p.17-23, January 01, 2005, Newcastle, Australia
	Philip Bille, A survey on tree edit distance and related problems, Theoretical Computer Science, v.337 n.1-3, p.217-239, 9 June 2005
	Raihan Al-Ekram , Archana Adma , Olga Baysal, diffX: an algorithm to detect changes in multi-version XML documents, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.1-11, October 17-20, 2005, Toranto, Ontario, Canada
	Theodore Dalamagas , Tao Cheng , Klaas-Jan Winkel , Timos Sellis, A methodology for clustering XML documents by structure, Information Systems, v.31 n.3, p.187-228, May 2006
	Carol J. Romanowski , Rakesh Nagi , Moises Sudit, Data mining in an engineering design environment: OR applications from graph matching, Computers and Operations Research, v.33 n.11, p.3150-3160, November 2006
	Lin Xu , Curtis Dyreson, Approximate retrieval of XML data with ApproXPath, Proceedings of the nineteenth conference on Australasian database, December 03-04, 2007, Gold Coast, Australia
	Tancred Lindholm , Jaakko Kangasharju , Sasu Tarkoma, Fast and simple XML tree differencing by sequence alignment, Proceedings of the 2006 ACM symposium on Document engineering, October 10-13, 2006, Amsterdam, The Netherlands
	David F. Huynh , Robert C. Miller , David R. Karger, Enabling web browsers to augment web sites' filtering and sorting functionalities, Proceedings of the 19th annual ACM symposium on User interface software and technology, October 15-18, 2006, Montreux, Switzerland
	Aïda Ouangraoua , Pascal Ferraro , Laurent Tichit , Serge Dulucq, Local similarity between quotiented ordered trees, Journal of Discrete Algorithms, v.5 n.1, p.23-35, March, 2007
	Karane Vieira , Altigran S. da Silva , Nick Pinto , Edleno S. de Moura , João M. B. Cavalcanti , Juliana Freire, A fast and robust method for web page template detection and removal, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Tatsuya Akutsu, A relation between edit distance for ordered trees and edit distance for Euler strings, Information Processing Letters, v.100 n.3, p.105-109, 15 November 2006
	Arnoldo José Müller Molina , Takeshi Shinohara, On approximate matching of programs for protecting libre software, Proceedings of the 2006 conference of the Center for Advanced Studies on Collaborative research, October 16-19, 2006, Toronto, Ontario, Canada
	Jie Han , Dingyi Han , Chenxi Lin , Hua-Jun Zeng , Zheng Chen , Yong Yu, Homepage live: automatic block tracing for web personalization, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Sven Helmer, Measuring the structural similarity of semistructured documents using entropy, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	K. Selçuk Candan , Prakash Yamuna, Similarity-Based Retrieval of Temporal Specifications and its Application to the Retrieval of Multimedia Documents, Multimedia Tools and Applications, v.27 n.1, p.143-180, September 2005
	D. Shasha , K. Zhang, Fast parallel algorithms for the unit cost editing distance between trees, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.117-126, June 18-21, 1989, Santa Fe, New Mexico, United States
	Praveen Lakkaraju , Susan Gauch , Mirco Speretta, Document similarity based on concept tree distance, Proceedings of the nineteenth ACM conference on Hypertext and hypermedia, June 19-21, 2008, Pittsburgh, PA, USA
	Kemal Oflazer, Error-Tolerant Retrieval of Trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.12, p.1376-1380, December 1997
	Yanhong Zhai , Bing Liu, Structured Data Extraction from the Web Based on Partial Tree Alignment, IEEE Transactions on Knowledge and Data Engineering, v.18 n.12, p.1614-1628, December 2006
	Jason T. L. Wang , Bruce A. Shapiro , Dennis Shasha , Kaizhong Zhang , Kathleen M. Currey, An Algorithm for Finding the Largest Approximately Common Substructures of Two Trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.8, p.889-895, August 1998
	Aïda Ouangraoua , Pascal Ferraro, A new constrained edit distance between quotiented ordered trees, Journal of Discrete Algorithms, v.7 n.1, p.78-89, March, 2009
	Hélène Touzet, Comparing similar ordered trees in linear-time, Journal of Discrete Algorithms, v.5 n.4, p.696-705, December, 2007
	Mostafa Haghir Chehreghani , Masoud Rahgozar , Caro Lucas , Morteza Haghir Chehreghani, A heuristic algorithm for clustering rooted ordered trees, Intelligent Data Analysis, v.11 n.4, p.355-376, September 2007
	Venkata Snehith Cherukuri , Kasim Selçuk Candan, Propagation-vectors for trees (PVT): concise yet effective summaries for hierarchical data and trees, Proceeding of the 2008 ACM workshop on Large-Scale distributed systems for information retrieval, October 30-30, 2008, Napa Valley, California, USA
	Julien Allali , Marie-France Sagot, A multiple layer model to compare RNA secondary structures, Software—Practice & Experience, v.38 n.8, p.775-792, July 2008
	Beat Fluri , Michael Wuersch , Martin PInzger , Harald Gall, Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction, IEEE Transactions on Software Engineering, v.33 n.11, p.725-743, November 2007
	Kilho Shin , Tetsuji Kuboyama, A generalization of Haussler's convolution kernel: mapping kernel, Proceedings of the 25th international conference on Machine learning, p.944-951, July 05-09, 2008, Helsinki, Finland
	Dekel Tsur, Faster algorithms for guided tree edit distance, Information Processing Letters, v.108 n.4, p.251-254, October, 2008
	Tatsuya Akutsu , Daiji Fukagawa , Atsuhiro Takasu, Improved approximation of the largest common subtree of two unordered trees of bounded height, Information Processing Letters, v.109 n.2, p.165-170, December, 2008
	Luc De Raedt , Jan Ramon, Deriving distance metrics from generality relations, Pattern Recognition Letters, v.30 n.3, p.187-191, February, 2009
	Michel Rougemont , Adrien Vieilleribière, Approximate schemas, source-consistency and query answering, Journal of Intelligent Information Systems, v.31 n.2, p.127-146, October 2008
	Karane Vieira , André Luiz Costa Carvalho , Klessius Berlt , Edleno S. Moura , Altigran S. Silva , Juliana Freire, On Finding Templates on Web Collections, World Wide Web, v.12 n.2, p.171-211, June 2009
	Elisa Bertino , Giovanna Guerrini , Marco Mesiti, Measuring the structural similarity among XML documents and DTDs, Journal of Intelligent Information Systems, v.30 n.1, p.55-92, February 2008
	Cui Tao , David W. Embley, Automatic hidden-web table interpretation, conceptualization, and semantic annotation, Data & Knowledge Engineering, v.68 n.7, p.683-703, July, 2009
	Fausto Giunchiglia , Mikalai Yatskevich , Fiona McNeill , Pavel Shvaiko , Juan Pane , Paolo Besana, Approximate structure preserving semantic matching, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.743-744, June 27, 2008
	Shay Mozes , Dekel Tsur , Oren Weimann , Michal Ziv-Ukelson, Fast algorithms for computing tree LCS, Theoretical Computer Science, v.410 n.43, p.4303-4314, October, 2009
	Rüdiger Gleim , Alexander Mehler , Matthias Dehmer, Web corpus mining by instance of Wikipedia, Proceedings of the 2nd International Workshop on Web as Corpus, p.67-74, April 01-01, 2006, Trento, Italy
	Sebastian Rönnau , Geraint Philipp , Uwe M. Borghoff, Efficient change control of XML documents, Proceedings of the 9th ACM symposium on Document engineering, September 16-18, 2009, Munich, Germany
	Leonardo A. Ribeiro , Theo Härder , Fernanda S. Pimenta, A cluster-based approach to XML similarity joins, Proceedings of the 2009 International Database Engineering & Applications Symposium, September 16-18, 2009, Cetraro - Calabria, Italy
	Seokhwan Kim , Minwoo Jeong , Gary Geunbae Lee, A local tree alignment-based soft pattern matching approach for information extraction, Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Short Papers, May 31-June 05, 2009, Boulder, Colorado
	Bo Wu , Xueqi Cheng , Yu Wang , Gang Zhang , Guodong Ding, Facilitating wrapper generation with page analysis, Proceedings of the 2009 IEEE international conference on Intelligence and security informatics, p.191-193, June 08-11, 2009, Richardson, Texas, USA
	Bengi Karacali , Mark Karol, Estimating topological distances based on end-to-end path sharing, Proceedings of the 32nd international conference on Sarnoff symposium, p.121-125, March 30-April 01, 2009, Princeton, New Jersey, USA