ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
The String-to-String Correction Problem
Full text PdfPdf (598 KB)
Source Journal of the ACM (JACM) archive
Volume 21 ,  Issue 1  (January 1974) table of contents
Pages: 168 - 173  
Year of Publication: 1974
ISSN:0004-5411
Authors
Robert A. Wagner  System and Information Science Department, Vanderbilt University, Nashville, TN
Michael J. Fischer  Project MAC, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 44,   Downloads (12 Months): 398,   Citation Count: 239
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/321796.321811
What is a DOI?

ABSTRACT

The string-to-string correction problem is to determine the distance between two strings as measured by the minimum cost sequence of “edit operations” needed to change the one string into the other. The edit operations investigated allow changing one symbol of a string into another single symbol, deleting one symbol from a string, or inserting a single symbol into a string. An algorithm is presented which solves this problem in time proportional to the product of the lengths of the two strings. Possible applications are to the problems of automatic spelling correction and determining the longest subsequence of characters common to two strings.


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
Howard L. Morgan, Spelling correction in systems programs, Communications of the ACM, v.13 n.2, p.90-94, Feb 1970  [doi>10.1145/362007.362033]

CITED BY  240
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
H. Bunke , J. Csirik, Edit distance of run-length coded strings, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.137-143, April 1992, Kansas City, Missouri, United States
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
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
 
James Bradford, A metric space defined on English and its relation to error correction, Proceedings of the 9th conference on Computational linguistics, p.43-48, July 05-10, 1982, Prague, Czechoslovakia
 
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
 
Aïda Ouangraoua , Pascal Ferraro, A constrained edit distance algorithm between semi-ordered trees, Theoretical Computer Science, v.410 n.8-10, p.837-846, March, 2009
 
R. C. Agarwal , K. Gupta , S. Jain , S. Amalapurapu, An approximation to the greedy algorithm for differential compression, IBM Journal of Research and Development, v.50 n.1, p.149-166, January 2006
 
Shyong Jian Shyu , Chun-Yuan Tsai, Finding the longest common subsequence for multiple biological sequences by ant colony optimization, Computers and Operations Research, v.36 n.1, p.73-91, January, 2009
Karen Kukich, Spelling correction for the telecommunications network for the deaf, Communications of the ACM, v.35 n.5, p.80-90, May 1992
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
 
Mitra Basu , Horst Bunke , Alberto Del Bimbo, Guest Editors' Introduction to the Special Section on Syntactic and Structural Pattern Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1009-1012, July 2005
 
A. M. Sokolov, Vector representations for efficient comparison and search for similar strings, Cybernetics and Systems Analysis, v.43 n.4, p.484-498, July 2007
Kai-Tai Tang , Howard Leung , Taku Komura , Hubert P. H. Shum, Finding repetitive patterns in 3D human motion captured data, Proceedings of the 2nd international conference on Ubiquitous information management and communication, January 31-February 01, 2008, Suwon, Korea
 
Raghu Sastry , N. Ranganathan, A VLSI Architecture for Approximate Tree Matching, IEEE Transactions on Computers, v.47 n.3, p.346-352, March 1998
S. Kuo , G. R. Cross, An improved algorithm to find the length of the longest common subsequence of two strings, ACM SIGIR Forum, v.23 n.3-4, p.89-99, Spring 1989
 
Xinbo Gao , Bing Xiao , Dacheng Tao , Xuelong Li, Image categorization: Graph edit distance+edge direction histogram, Pattern Recognition, v.41 n.10, p.3179-3191, October, 2008
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
R. Anderson , P. Beame , W. Ruzzo, Low overhead parallel schedules for task graphs, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.66-75, July 02-06, 1990, Island of Crete, Greece
 
R. M. K. Sinha , B. Prasada , G. F. Houle , M. Sabourin, Hybrid Contextural Text Recognition with String Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.915-925, September 1993
Wen-Chen Hu , Gerhard X. Ritter , Mark S. Schmalz, Approximating the longest approximate common subsequence problem, Proceedings of the 36th annual Southeast regional conference, p.166-172, April 1998
 
Helena Cristina da Gama Leitão , Jorge Stolfi, A Multiscale Method for the Reassembly of Two-Dimensional Fragmented Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1239-1251, September 2002
 
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
 
Li Yujian , Liu Bo, A Normalized Levenshtein Distance Metric, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.6, p.1091-1095, June 2007
 
Luc De Raedt , Jan Ramon, Deriving distance metrics from generality relations, Pattern Recognition Letters, v.30 n.3, p.187-191, February, 2009
 
Venu Govindaraju , Petr Slavík , Hanhong Xue, Use of Lexicon Density in Evaluating Word Recognizers, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.6, p.789-800, June 2002
 
Horst Bunke , Simon Günter, Weighted mean of a pair of graphs, Computing, v.67 n.3, p.209-224, November 2001
 
Emmanuel Planas , Osamu Furuse, Multi-level similar segment matching algorithm for translation memories and Example-based Machine Translation, Proceedings of the 18th conference on Computational linguistics, July 31-August 04, 2000, Saarbrücken, Germany
 
Michel Neuhaus , Horst Bunke, Edit distance-based kernel functions for structural pattern classification, Pattern Recognition, v.39 n.10, p.1852-1863, October, 2006
 
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
 
Gabriel Castillo , Gerardo Sierra , John McNaught, An improved algorithm for semantic clustering, Proceedings of the 1st international symposium on Information and communication technologies, September 24-26, 2003, Dublin, Ireland
 
Yin-Te Tsai, The constrained longest common subsequence problem, Information Processing Letters, v.88 n.4, p.173-176, 30 November 2003
 
Leonard Berman, On logic comparison, Proceedings of the 18th conference on Design automation, p.854-861, June 29-July 01, 1981, Nashville, Tennessee, United States
Jussi Karlgren , Hans Karlgren , Paul Pettersson , Magnus Nordstrom , Bengt Wahrolen, DILEMMA: a tool for rapid manual translation, Conference companion on Human factors in computing systems, p.129-130, April 24-28, 1994, Boston, Massachusetts, United States
 
Francis Y. L. Chin , Alfredo De Santis , Anna Lisa Ferrara , N. L. Ho , S. K. Kim, A simple algorithm for the constrained sequence problems, Information Processing Letters, v.90 n.4, p.175-179, 31 May 2004
 
Mosleh Hmoud Al-Adhaileh , Tang Enya Kong, A flexible example-based parser based on the SSTC, Proceedings of the 17th international conference on Computational linguistics, August 10-14, 1998, Montreal, Quebec, Canada
 
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
James Gosling, A redisplay algorithm, ACM SIGPLAN Notices, v.16 n.6, p.123-129, June 1981
Hal Berghel , David Roach, An extension of Ukkonen's enhanced dynamic programming ASM algorithm, ACM Transactions on Information Systems (TOIS), v.14 n.1, p.94-106, Jan. 1996
F. Hadlock, An efficient algorithm for pattern detection and classification, Proceedings of the 1st international conference on Industrial and engineering applications of artificial intelligence and expert systems, p.645-653, June 1988, Tullahoma, Tennessee, United States
Kuo-chung Tai, Fault-tolerant string processing by pattern mapping, Proceedings of the 1977 annual conference, p.336-342, January 1977
 
Daniel Gildea , Daniel Jurafsky, Automatic induction of finite state transducers for simple phonological rules, Proceedings of the 33rd annual meeting on Association for Computational Linguistics, p.9-15, June 26-30, 1995, Cambridge, Massachusetts
 
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
 
Kyong-Ho Lee , Yoon-Chul Choy , Sung-Bae Cho, An Efficient Algorithm to Compute Differences between Structured Documents, IEEE Transactions on Knowledge and Data Engineering, v.16 n.8, p.965-979, August 2004
Paul Heckel, A technique for isolating differences between files, Communications of the ACM, v.21 n.4, p.264-268, April 1978
 
Richard Myers , Richard C. Wilson , Edwin R. Hancock, Bayesian Graph Edit Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.6, p.628-635, June 2000
 
Grzegorz Kondrak , Bonnie Dorr, Identification of confusable drug names: a new approach and evaluation methodology, Proceedings of the 20th international conference on Computational Linguistics, p.952-es, August 23-27, 2004, Geneva, Switzerland
 
Farooq Ahmad , Grzegorz Kondrak, Learning a spelling error model from search query logs, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.955-962, October 06-08, 2005, Vancouver, British Columbia, Canada
 
Muhammad Marwan Muhammad Fuad , Pierre-François Marteau, The multi-resolution extended edit distance, Proceedings of the 3rd international conference on Scalable information systems, June 04-06, 2008, Vico Equense, Italy
Ibrahim Kamel, Fast retrieval of cursive handwriting, Proceedings of the fifth international conference on Information and knowledge management, p.91-98, November 12-16, 1996, Rockville, Maryland, United States
 
Heikki Hyyrö, A bit-vector algorithm for computing Levenshtein and Damerau edit distances, Nordic Journal of Computing, v.10 n.1, p.29-39, Spring 2003
 
A. Mukherjee, Hardware Algorithms for Determining Similarity Between two Strings, IEEE Transactions on Computers, v.38 n.4, p.600-603, April 1989
 
Jens Gregor , Michael G. Thomason, Dynamic Programming Alignment of Sequences Representing Cyclic Patterns, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.2, p.129-135, February 1993
 
Yves Lepage , Ando Shin-ichi, Saussurian analogy: a theoretical account and its application, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark
 
Kenneth Sörensen , Marc Sevaux, MA|PM: memetic algorithms with population management, Computers and Operations Research, v.33 n.5, p.1214-1225, May 2006
 
Jianmin Yao , Ming Zhou , Tiejun Zhao , Hao Yu , Sheng Li, An automatic evaluation method for localization oriented lexicalised EBMT system, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan
 
Yih-Tay Tsay , Wen-Hsiang Tsai, Attributed String Matching by Split-and-Merge for On-Line Chinese Character Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.2, p.180-185, February 1993
 
Enrique Vidal , Andrés Marzal , Pablo Aibar, Fast Computation of Normalized Edit Distances, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.9, p.899-902, September 1995
 
Michael Strube , Stefan Rapp , Christoph Müller, The influence of minimum edit distance on reference resolution, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.312-319, July 06, 2002
 
Laurent Blin , Laurent Miclet, Generating synthetic speech prosody with lazy learning in tree structures, Proceedings of the 2nd workshop on Learning language in logic and the 4th conference on Computational natural language learning, September 13-14, 2000, Lisbon, Portugal
 
Rahim Khoja , Mehul Marolia , Tinku Acharya , Chaitali Chakrabarti, A coprocessor architecture for fast protein structure prediction, Pattern Recognition, v.39 n.12, p.2494-2505, December, 2006
 
Tien-Lung Sun , Wen-Lin Kuo, Visual exploration of production data using small multiples design with non-uniform color mapping, Computers and Industrial Engineering, v.43 n.4, p.751-764, September 2002
B. John Oommen , R. S. Valiveti , J. Zgierski, A fast learning automaton solution to the keyboard optimization problem, Proceedings of the 3rd international conference on Industrial and engineering applications of artificial intelligence and expert systems, p.981-990, June 1990, Charleston, South Carolina, United States
 
Gerardo Sierra , John McNaught, Extracting semantic clusters from the alignment of definitions, Proceedings of the 18th conference on Computational linguistics, July 31-August 04, 2000, Saarbrücken, Germany
 
H. Bunke, Error Correcting Graph Matching: On the Influence of the Underlying Cost Function, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.9, p.917-922, September 1999
Kuo-Chung Tai, The Tree-to-Tree Correction Problem, Journal of the ACM (JACM), v.26 n.3, p.422-433, july 1979
 
Yves Lepage, Non-directionality and self-assessment in an example-based system using genetic algorithms, Proceedings of the 15th conference on Computational linguistics, August 05-09, 1994, Kyoto, Japan
 
A. Marzal , E. Vidal, Computation of Normalized Edit Distance and Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.926-932, September 1993
 
Xiaobo Ren , François Perrault, The typology of unknown words: an experimental study of two corpora, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France
 
Hiyan Alshawi , Shona Douglas, Variant transduction: a method for rapid development of interactive spoken interfaces, Proceedings of the Second SIGdial Workshop on Discourse and Dialogue, p.1-9, September 01-02, 2001, Aalborg, Denmark
Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, ACM SIGMOD Record, v.26 n.2, p.26-37, June 1997
James C. French , Allison L. Powell , Eric Schulman, Applications of approximate word matching in information retrieval, Proceedings of the sixth international conference on Information and knowledge management, p.9-15, November 10-14, 1997, Las Vegas, Nevada, United States
 
Serkan Kaygin , M. Mete Bulut, Shape recognition using attributed string matching with polygon vertices as the primitives, Pattern Recognition Letters, v.23 n.1-3, p.287-294, January 2002
Christoph Reichenberger, Delta storage for arbitrary non-text files, Proceedings of the 3rd international workshop on Software configuration management, p.144-152, June 12-14, 1991, Trondheim, Norway
 
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
 
Hans Karlgren , Jussi Karlgren , Magnus Nordström , Paul Pettersson , Bengt Wahrolén, Dilemma: an instant lexicographer, Proceedings of the 15th conference on Computational linguistics, August 05-09, 1994, Kyoto, Japan
 
Yves Lepage, Solving analogies on words: an algorithm, Proceedings of the 17th international conference on Computational linguistics, August 10-14, 1998, Montreal, Quebec, Canada
 
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
 
B. J. Oommen , K. Zhang, The Normalized String Editing Problem Revisited, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.6, p.669-672, June 1996
Hal Berghel, On seamless prototyping, ACM SIGICE Bulletin, v.19 n.3, p.10-17, Feb. 1994
 
Masaaki Nagata, Context-based spelling correction for Japanese OCR, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark
 
Eric Brill , Robert C. Moore, An improved error model for noisy channel spelling correction, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, p.286-293, October 03-06, 2000, Hong Kong
 
Abdullah N. Arslan, An algorithm with linear expected running time for string editing with substitutions and substring reversals, Information Processing Letters, v.106 n.5, p.213-218, May, 2008
Lian'en Huang , Lei Wang , Xiaoming Li, Achieving both high precision and high recall in near-duplicate detection, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
Leslie G. Valiant, On non-linear lower bounds in computational complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.45-53, May 05-07, 1975, Albuquerque, New Mexico, United States
Gene Myers, A Four Russians algorithm for regular expression pattern matching, Journal of the ACM (JACM), v.39 n.2, p.432-448, April 1992
Michael Nashvili , Markus Olhofer , Bernhard Sendhoff, Morphing methods in evolutionary design optimization, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
 
Eva Gómez-Ballester , Luisa Micó , Jose Oncina, Some approaches to improve tree-based nearest neighbour search algorithms, Pattern Recognition, v.39 n.2, p.171-179, February, 2006
 
Sudarshan S. Chawathe, Comparing Hierarchical Data in External Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.90-101, September 07-10, 1999
 
Hsing-Yen Ann , Chang-Biau Yang , Chiou-Ting Tseng , Chiou-Yi Hor, A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings, Information Processing Letters, v.108 n.6, p.360-364, November, 2008
Manish Kumar , Shane Moriah , Srikumar Krishnamoorthy, Performance evaluation of similarity join for real time information integration, Proceedings of the 2nd Bangalore Annual Compute Conference on 2nd Bangalore Annual Compute Conference, January 09-10, 2009, Bangalore, India
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
J. Veronis, Correction of phonographic errors in natural language interfaces, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.101-115, May 1988, Grenoble, France
Hal Berghel , David Roach , George Balogh , Carroll Hyatt, “Tuning” an ASM metric: a case study in metric ASM optimization, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.131-136, April 1992, Kansas City, Missouri, United States
 
Oscar H. Ibarra , Tao Jiang , Hui Wang, String Editing on a One-Way Linear Array of Finite-State Machines, IEEE Transactions on Computers, v.41 n.1, p.112-118, January 1992
 
Masaaki Nagata, Japanese OCR error correction using character shape similarity and statistical language model, Proceedings of the 17th international conference on Computational linguistics, p.922-928, August 10-14, 1998, Montreal, Quebec, Canada
 
Raghu Sastry , N. Ranganathan , Klinton Remedios, CASM: A VLSI Chip for Approximate String Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.8, p.824-830, August 1995
Kurt Driessens , Sašo Džeroski, Combining model-based and instance-based learning for first order regression, Proceedings of the 22nd international conference on Machine learning, p.193-200, August 07-11, 2005, Bonn, Germany
 
Christoph Müller , Stefan Rapp , Michael Strube, Applying Co-Training to reference resolution, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania
 
Hiyan Alshawi , Shona Douglas, Speech translation performance of statistical dependency transduction and semantic similarity transduction, Proceedings of the ACL-02 workshop on Speech-to-speech translation: algorithms and systems, p.31-38, July 11, 2002
 
Paola Bonizzoni , Gianluca Della Vedova , Riccardo Dondi , Guillaume Fertin , Raffaella Rizzi , Stephane Vialette, Exemplar Longest Common Subsequence, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.4, p.535-543, October 2007
Byung-Ju Kang , Key-Sun Choi, Two approaches for the resolution of word mismatch problem caused by English words and foreign words in Korean information retrieval, Proceedings of the fifth international workshop on on Information retrieval with Asian languages, p.133-140, September 30-October 01, 2000, Hong Kong, China
Walter F. Tichy, The string-to-string correction problem with block moves, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.309-321, Nov. 1984
 
Juan Ramón Rico-Juan , Luisa Micó, Comparison of AESA and LAESA search algorithms using string and tree-edit-distances, Pattern Recognition Letters, v.24 n.9-10, p.1417-1426, 01 June 2003
 
Masayuki Takeda , Tomoko Fukuda , Ichiro Nanri , Mayumi Yamasaki , Koichi Tamari, Discovering instances of poetic allusion from anthologies of classical Japanese poems, Theoretical Computer Science, v.292 n.2, p.497-524, 27 January 2003
Matthias Robine , Pierre Hanna , Pascal Ferraro, Music similarity: improvements of edit-based algorithms by considering music theory, Proceedings of the international workshop on Workshop on multimedia information retrieval, September 24-29, 2007, Augsburg, Bavaria, Germany
 
Timothy Baldwin , Hozumi Tanaka, The effects of word order and segmentation on translation retrieval performance, Proceedings of the 18th conference on Computational linguistics, p.35-41, July 31-August 04, 2000, Saarbrücken, Germany
 
Campbell B. Fraser , Robert W. Irving, Approximation algorithms for the shortest common supersequence, Nordic Journal of Computing, v.2 n.3, p.303-325, Fall 1995
 
Grzegorz Kondrak, A new algorithm for the alignment of phonetic sequences, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.288-295, April 29-May 04, 2000, Seattle, Washington
 
Menno van Zaanen, ABL: alignment-based learning, Proceedings of the 18th conference on Computational linguistics, July 31-August 04, 2000, Saarbrücken, Germany
 
Jean Veronis, Morphosyntactic correction in natural language interfaces, Proceedings of the 12th conference on Computational linguistics, p.708-713, August 22-27, 1988, Budapest, Hungry
 
Timothy Baldwin, Low-cost, high-performance translation retrieval: dumber is better, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.18-25, July 06-11, 2001, Toulouse, France
 
Y.-C. Cheng , S.-Y. Lu, The Binary Consistency Checking Scheme and Its Applications to Seismic Horizon Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.4, p.439-447, April 1989
 
Huaijun Qiu , Edwin R. Hancock, Graph matching and clustering using spectral partitions, Pattern Recognition, v.39 n.1, p.22-34, January, 2006
 
Costas S. Iliopoulos , M. Sohel Rahman, New efficient algorithms for the LCS and constrained LCS problems, Information Processing Letters, v.106 n.1, p.13-18, March, 2008
 
Kenneth Sörensen, Distance measures based on the edit distance for permutation-type representations, Journal of Heuristics, v.13 n.1, p.35-47, February 2007
 
H. Blume , H.-M. Blüthgen , C. Henning , P. Osterloh , T. G. Noll, Embedding of Dedicated High-Performance ASICs into Reconfigurable Systems Providing Additional Multimedia Functionality, Journal of VLSI Signal Processing Systems, v.31 n.2, p.117-126, June 2002
Krishnendu Chatterjee , Luca de Alfaro , Ian Pye, Robust content-driven reputation, Proceedings of the 1st ACM workshop on Workshop on AISec, October 27-27, 2008, Alexandria, Virginia, USA
 
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
 
Keh-Yih Su , Ming-Wen Wu , Jing-Shin Chang, A new quantitative quality measure for machine translation systems, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France
 
C. D. Martínez-Hinarejos , A. Juan , F. Casacuberta, Median strings for k-nearest neighbour classification, Pattern Recognition Letters, v.24 n.1-3, p.173-181, January 2003
 
Grzegorz Kondrak, Determining recurrent sound correspondences by inducing translation models, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan
 
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
 
J. J. Astrain , J. R. Garitagoitia , J. R. Gonzalez De Mendivil , J. Villadangos , F. Fariña, Approximate String Matching Using Deformed Fuzzy Automata: A Learning Experience, Fuzzy Optimization and Decision Making, v.3 n.2, p.141-155, June 2004
Shaolei Feng , R. Manmatha, A hierarchical, HMM-based automatic evaluation of OCR accuracy for a digital library of books, Proceedings of the 6th ACM/IEEE-CS joint conference on Digital libraries, June 11-15, 2006, Chapel Hill, NC, USA
 
Scott E. Coull , Boleslaw K. Szymanski, Sequence alignment for masquerade detection, Computational Statistics & Data Analysis, v.52 n.8, p.4116-4131, April, 2008
 
David Wakeling, EDUCATIONAL PEARL: Biological sequence similarity, Journal of Functional Programming, v.16 n.1, p.1-12, January 2006
Eugene W. Meyers , Webb Miller, Row replacement algorithms for screen editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.33-56, Jan. 1989
 
Quang Minh Tieng , W. W. Boles, Space Curve Representation and Recognition Based on Wavelet Transform Zero-Crossings, Journal of Mathematical Imaging and Vision, v.13 n.1, p.5-16, August 2000
Gene Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, Journal of the ACM (JACM), v.46 n.3, p.395-415, May 1999
 
Maxime Crochemore , Costas S. Ilipoulos , Yoan J. Pinzon, Speeding-up Hirschberg and Hunt-Szymanski LCS algorithms, Fundamenta Informaticae, v.56 n.1,2, p.89-103, July 2003
Mikhail J. Atallah , Florian Kerschbaum , Wenliang Du, Secure and private sequence comparisons, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC
Eric A. Breimer , Mark K. Goldberg , Darren T. Lim, A learning algorithm for the longest common subsequence problem, Journal of Experimental Algorithmics (JEA), 8, 2003
 
Gemma Sánchez , Josep Lladós , Karl Tombre, A mean string algorithm to compute the average among a set of 2D shapes, Pattern Recognition Letters, v.23 n.1-3, p.203-213, January 2002
 
Yanhong Li , Daniel Lopresti , George Nagy , Andrew Tomkins, Validation of Image Defect Models for Optical Character Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.2, p.99-108, February 1996
Daniel Lopresti, Performance evaluation for text processing of noisy inputs, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
 
Karim Filali , Jeff Bilmes, A dynamic Bayesian framework to model context and memory in edit distance learning: an application to pronunciation classification, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.338-345, June 25-30, 2005, Ann Arbor, Michigan
 
Enrique Alfonseca , Pablo Castells , Manabu Okumura , Maria Ruiz-Casado, A rote extractor with edit distance-based generalisation and multi-corpora precision calculation, Proceedings of the COLING/ACL on Main conference poster sessions, p.9-16, July 17-18, 2006, Sydney, Australia
Benjamin Lerner , Dan Grossman , Craig Chambers, Seminal: searching for ML type-error messages, Proceedings of the 2006 workshop on ML, September 16-16, 2006, Portland, Oregon, USA
 
E. Baseski , A. Erdem , S. Tari, Dissimilarity between two skeletal trees in a context, Pattern Recognition, v.42 n.3, p.370-385, March, 2009
 
Kaspar Riesen , Horst Bunke, Approximate graph edit distance computation by means of bipartite graph matching, Image and Vision Computing, v.27 n.7, p.950-959, June, 2009
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
A. Aggarwal , D. Kravets , J. Park , S. Sen, Parallel searching in generalized Monge arrays with applications, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.259-268, July 02-06, 1990, Island of Crete, Greece
Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977
 
Gary Benson, Tandem cyclic alignment, Discrete Applied Mathematics, v.146 n.2, p.124-133, 1 March 2005
Judy Goldsmith , Robert H. Sloan, More theory revision with queries (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.441-448, May 21-23, 2000, Portland, Oregon, United States
Rodger J. McNab , Lloyd A. Smith , Ian H. Witten , Clare L. Henderson , Sally Jo Cunningham, Towards the digital music library: tune retrieval from acoustic input, Proceedings of the first ACM international conference on Digital libraries, p.11-18, March 20-23, 1996, Bethesda, Maryland, United States
Sam Y. Sung , Zhao Li , Peng Sun, A fast filtering scheme for large database cleansing, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
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
 
Roman Bertolami , Matthias Zimmermann , Horst Bunke, Rejection strategies for offline handwritten text line recognition, Pattern Recognition Letters, v.27 n.16, p.2005-2012, December, 2006
 
Roland H. C. Yap, Parametric Sequence Alignment with Constraints, Constraints, v.6 n.2-3, p.157-172, June 2001
 
Daniel P. Lopresti, A Comparison of Text-Based Methods for Detecting Duplication in Scanned Document Databases, Information Retrieval, v.4 n.2, p.153-173, July 2001
 
Zhenchang Xing , Eleni Stroulia, Differencing logical UML models, Automated Software Engineering, v.14 n.2, p.215-259, June 2007
 
Alan Messer , Anugeetha Kunjithapatham , Phuong Nguyen , Priyang Rathod , Mithun Sheshagiri , Doreen Cheng , Simon Gibbs, SeeNSearch: A context directed search facilitator for home entertainment devices, Pervasive and Mobile Computing, v.4 n.6, p.871-888, December, 2008
David Maier, The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM (JACM), v.25 n.2, p.322-336, April 1978
 
Marc Parizeau , Réjean Plamondon, A Fuzzy-Syntactic Approach to Allograph Modeling for Cursive Script Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.7, p.702-712, July 1995
 
Simon Günter , Horst Bunke, Self-organizing map for clustering in the graph domain, Pattern Recognition Letters, v.23 n.4, p.405-417, February 2002
Alexander M. Robertson , Peter Willett, Searching for historical word-forms in a database of 17th-century English text using spelling-correction methods, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.256-265, June 21-24, 1992, Copenhagen, Denmark
Cen Li , Jungsoon Yoo, A study of the effects of bias in criterion functions for temporal data clustering, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
 
Ilhwan Choi , Bongki Moon , Hyoung-Joo Kim, A clustering method based on path similarities of XML data, Data & Knowledge Engineering, v.60 n.2, p.361-376, February, 2007
 
Roman Bertolami , Matthias Zimmermann , Horst Bunke, Rejection strategies for offline handwritten text line recognition, Pattern Recognition Letters, v.27 n.16, p.2005-2012, December 2006
 
Bruno T. Messmer , Horst Bunke, A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.5, p.493-504, May 1998
 
Gary Lewandowski , Anne Condon , Eric Bach, Asynchronous Analysis of Parallel Dynamic Programming Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.7 n.4, p.425-438, April 1996
 
Horst Bunke , Peter Dickinson , Christophe Irniger , Miro Kraetzl, Recovery of missing information in graph sequences by means of reference pattern matching and decision tree learning, Pattern Recognition, v.39 n.4, p.573-586, April, 2006
 
Guohui Lin , Zhi-Zhong Chen , Tao Jiang , Jianjun Wen, The longest common subsequence problem for sequences with nested arc annotations, Journal of Computer and System Sciences, v.65 n.3, p.465-480, November 2002
 
Béatrice Daille, Morphological rule induction for terminology acquistion, Proceedings of the 18th conference on Computational linguistics, p.215-221, July 31-August 04, 2000, Saarbrücken, Germany
 
Claus Rick, A new flexible algorithm for the longest common subsequence problem, Nordic Journal of Computing, v.2 n.4, p.444-461, Winter 1995
 
Amihood Amir , Tzvika Hartman , Oren Kapah , B. Riva Shalom , Dekel Tsur, Generalized LCS, Theoretical Computer Science, v.409 n.3, p.438-449, December, 2008
Stephen W. Liddle , Douglas M. Campbell , Chad Crawford, Automatically extracting structure and data from business reports, Proceedings of the eighth international conference on Information and knowledge management, p.86-93, November 02-06, 1999, Kansas City, Missouri, United States
S. O. Anderson , R. C. Backhouse, Locally Least-Cost Error Recovery in Earley's Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.3, p.318-347, July 1981
Christian R. Prause , Stefan Apelt, An approach for continuous inspection of source code, Proceedings of the 6th international workshop on Software quality, May 10-10, 2008, Leipzig, Germany
Herng-Yow Chen , Sheng-Wei Li, Exploring many-to-one speech-to-text correlation for web-based language learning, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.3 n.3, p.13-es, August 2007
 
David Eppstein , Zvi Galil , Raffaele Giancarlo , Giuseppe F. Italiano, Sparse dynamic programming, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.513-522, January 22-24, 1990, San Francisco, California, United States
Miklos Ajtai , Randal Burns , Ronald Fagin , Darrell D. E. Long , Larry Stockmeyer, Compactly encoding unstructured inputs with differential compression, Journal of the ACM (JACM), v.49 n.3, p.318-367, May 2002
 
Joong Chae Na , Kangho Roh , Alberto Apostolico , Kunsoo Park, Alignment of biological sequences with quality scores, International Journal of Bioinformatics Research and Applications, v.5 n.1, p.97-113, January 2009
 
Derek Justice , Alfred Hero, A Binary Linear Programming Formulation of the Graph Edit Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.8, p.1200-1214, August 2006
 
Pierre Courrieu, Function approximation on non-Euclidean spaces, Neural Networks, v.18 n.1, p.91-102, January 2005
 
H. Shang , T. h. Merrettal, Tries for Approximate String Matching, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.540-547, August 1996
Kuo-Chung Tai, Locally minimum-distance correction of syntax errors in programming languages, Proceedings of the ACM 1980 annual conference, p.204-210, January 1980
 
Rodger J. McNab , Lloyd A. Smith , Ian H. Witten , Clare L. Henderson, Tune Retrieval in the Multimedia Library, Multimedia Tools and Applications, v.10 n.2-3, p.113-132, April 2000
Rafael Corchuelo , José A. Pérez, , Antonio Ruiz , Miguel Toro, Repairing syntax errors in LR parsers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.698-710, November 2002
G M Landau , U Vishkin, Introducing efficient parallelism into approximate string matching and a new serial algorithm, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.220-230, May 28-30, 1986, Berkeley, California, United States
 
Shirish Tatikonda , Srinivasan Parthasarathy , Matthew Goyder, LCS-TRIM: dynamic programming meets XML indexing and querying, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
 
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
 
M. -W. Du , S. C. Chang, An Approach to Designing Very Fast Approximate String Matching Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.620-633, August 1994
Qiaozhu Mei , Dong Xin , Hong Cheng , Jiawei Han , Chengxiang Zhai, Semantic annotation of frequent patterns, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.3, p.11-es, December 2007
 
Philip Bille , Martin Farach-Colton, Fast and compact regular expression matching, Theoretical Computer Science, v.409 n.3, p.486-496, December, 2008
 
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
 
Jaehwa Park, An Adaptive Approach to Offline Handwritten Word Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.920-931, July 2002
 
K. Y. Hung , R. W. P. Luk , D. Yeung , K. F. L. Chung , W. Shu, Detection of language (model) errors, Proceedings of the 2000 Joint SIGDAT conference on Empirical methods in natural language processing and very large corpora: held in conjunction with the 38th Annual Meeting of the Association for Computational Linguistics, p.87-94, October 07-08, 2000, Hong Kong
 
Pierre Courrieu, Straight monotonic embedding of data sets in Euclidean spaces, Neural Networks, v.15 n.10, p.1185-1196, December 2002
 
S. E. Levinson , A. Ljolje , L. G. Miller, Continuous speech recognition from a phonetic transcription, Proceedings of the workshop on Speech and Natural Language, p.190-199, June 24-27, 1990, Hidden Valley, Pennsylvania
 
Tysen Leckie , Alec Yasinsac, Metadata for Anomaly-Based Security Protocol Attack Deduction, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1157-1168, September 2004
 
Thomas B. Sebastian , Philip N. Klein , Benjamin B. Kimia, On Aligning Curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.1, p.116-125, January 2003
Steve Meyer, CAD tool interchangeability through Net list translation, ACM SIGDA Newsletter, v.20 n.1, p.51-59, June 1990
 
Eric Sven Ristad , Peter N. Yianilos, Learning String-Edit Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.5, p.522-532, May 1998
 
Trinh N. D. Huynh , Wing-Kai Hon , Tak-Wah Lam , Wing-Kin Sung, Approximate string matching using compressed suffix arrays, Theoretical Computer Science, v.352 n.1, p.240-249, 7 March 2006
Robert P. Nix, Editing by example, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.600-621, Oct. 1985
 
Samuel W. K. Chan, Shallow semantic labeling using two-phase feature-enhanced string matching, Expert Systems with Applications: An International Journal, v.36 n.6, p.9729-9736, August, 2009
 
Danny Z. Chen , Ovidiu Daescu , Xiaobo Hu , Jinhui Xu, Finding an optimal path without growing the tree, Journal of Algorithms, v.49 n.1, p.13-41, 1 October 2003
 
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
 
Y. P. Wang , T. Pavlidis, Optimal Correspondence of String Subsequences, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.11, p.1080-1087, November 1990
 
Roger Mitton, Ordering the suggestions of a spellchecker without using context*, Natural Language Engineering, v.15 n.2, p.173-192, April 2009
 
Chuan Xiao , Wei Wang , Xuemin Lin, Ed-Join: an efficient algorithm for similarity joins with edit distance constraints, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
 
Wilson Wong , Wei Liu , Mohammed Bennamoun, Integrated scoring for spelling error correction, abbreviation expansion and case restoration in dirty text, Proceedings of the fifth Australasian conference on Data mining and analystics, p.83-89, November 29-30, 2006, Sydney, Australia
Serdar Cabuk , Carla E. Brodley , Clay Shields, IP covert timing channels: design and detection, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA
 
Martin Jansche, Learning Local Transductions Is Hard, Journal of Logic, Language and Information, v.13 n.4, p.439-455, March 2004
Jacob O. Wobbrock , Brad A. Myers, Analyzing the input stream for character- level errors in unconstrained text entry evaluations, ACM Transactions on Computer-Human Interaction (TOCHI), v.13 n.4, p.458-489, December 2006
 
Josep Lladoós , Enric Martí , Juan Josée Villanueva, Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1137-1143, October 2001
 
Roman Bertolami , Horst Bunke, Hidden Markov model-based ensemble methods for offline handwritten text line recognition, Pattern Recognition, v.41 n.11, p.3452-3460, November, 2008
Jason Tsong-Li Wang , Gung-Wei Chirn , Thomas G. Marr , Bruce Shapiro , Dennis Shasha , Kaizhong Zhang, Combinatorial pattern discovery for scientific data: some preliminary results, ACM SIGMOD Record, v.23 n.2, p.115-125, June 1994
 
Costas S. Iliopoulos , M. Sohel Rahman, Algorithms for computing variants of the longest common subsequence problem, Theoretical Computer Science, v.395 n.2-3, p.255-267, May, 2008
 
M. Y. Chen , A. Kundu , J. Zhou, Off-Line Handwritten Word Recognition Using a Hidden Markov Model Type Stochastic Network, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.5, p.481-496, May 1994
 
Jie Wei, Markov Edit Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.3, p.311-321, March 2004
 
Yue Lu , Chew Lim Tan, Information Retrieval in Document Image Databases, IEEE Transactions on Knowledge and Data Engineering, v.16 n.11, p.1398-1410, November 2004
 
Panagiotis D. Michailidis , Konstantinos G. Margaritis, Processor array architectures for flexible approximate string matching, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.1-2, p.35-54, January, 2008
 
Veli Mäkinen , Gonzalo Navarro , Esko Ukkonen, Transposition invariant string matching, Journal of Algorithms, v.56 n.2, p.124-153, August 2005
 
Sabrina Mantaci , Antonio Restivo , Marinella Sciortino, Distance measures for biological sequences: Some recent approaches, International Journal of Approximate Reasoning, v.47 n.1, p.109-124, January, 2008
 
Kurt Driessens , Sašo Džeroski, Integrating Guidance into Relational Reinforcement Learning, Machine Learning, v.57 n.3, p.271-304, December 2004
Robert Nix, Editing by example, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.186-195, January 15-18, 1984, Salt Lake City, Utah, United States
 
Stoyan Mihov , Klaus U. Schulz, Fast Approximate Search in Large Dictionaries, Computational Linguistics, v.30 n.4, p.451-477, December 2004
 
Antonio Robles-Kelly , Edwin R. Hancock, Graph Edit Distance from Spectral Seriation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.365-378, March 2005
James L. Peterson, Computer programs for detecting and correcting spelling errors, Communications of the ACM, v.23 n.12, p.676-687, Dec. 1980
 
Fredy Amaya , José Miguel Benedí, Improvement of a Whole Sentence Maximum Entropy Language Model using grammatical features, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.10-17, July 06-11, 2001, Toulouse, France
 
Joystone Gbadamosi , Wolfgang H. Zangemeister, Visual Imagery in Hemianopic Patients, Journal of Cognitive Neuroscience, v.13 n.7, p.855-866, October 2001
 
Anita Prinzie , Dirk Van den Poel, Incorporating sequential information into traditional classification models by using an element/position-sensitive SAM, Decision Support Systems, v.42 n.2, p.508-526, November 2006
 
Sébastien L’haire, FipsOrtho: A spell checker for learners of French, ReCALL, v.19 n.2, p.137-161, May 2007
 
Gregory V. Bard, Spelling-error tolerant, order-independent pass-phrases via the damerau-levenshtein string-edit distance metric, Proceedings of the fifth Australasian symposium on ACSW frontiers, January 30-February 02, 2007, Ballarat, Australia
 
Leonor Becerra-Bonache , Colin de la Higuera , Jean-Christophe Janodet , Frédéric Tantini, Learning Balls of Strings from Edit Corrections, The Journal of Machine Learning Research, 9, p.1841-1870, 6/1/2008
 
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
 
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
 
Daniel Gildea , Daniel Jurafsky, Learning bias and phonological-rule induction, Computational Linguistics, v.22 n.4, p.497-530, December 1996
Paolo Ciaccia , Marco Patella, Searching in metric spaces with user-defined and approximate distances, ACM Transactions on Database Systems (TODS), v.27 n.4, p.398-437, December 2002
 
Panagiotis D. Michailidis , Konstantinos G. Margaritis, A programmable array processor architecture for flexible approximate string matching algorithms, Journal of Parallel and Distributed Computing, v.67 n.2, p.131-141, February, 2007
 
Maria Ruiz-Casado , Enrique Alfonseca , Pablo Castells, Automatising the learning of lexical patterns: An application to the enrichment of WordNet by extracting semantic relationships from Wikipedia, Data & Knowledge Engineering, v.61 n.3, p.484-499, June, 2007
Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980
Peter N. van den Bosch, A bibliography on syntax error handling in context free languages, ACM SIGPLAN Notices, v.27 n.4, p.77-86, April 1992
 
Harold Somers, Review Article: Example-based Machine Translation, Machine Translation, v.14 n.2, p.113-157, June 1999
Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001
Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING


General Terms:
Algorithms, Languages, Performance, Theory, Verification

Collaborative Colleagues:
Robert A. Wagner: colleagues
Michael J. Fischer: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player