The String-to-String Correction Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The String-to-String Correction Problem

Full text

Pdf (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): 41, Downloads (12 Months): 407, Citation Count: 251

Additional Information:

abstract 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/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.

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 251

	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
	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
	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
	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
	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
	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
	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
	James L. Peterson, Computer programs for detecting and correcting spelling errors, Communications of the ACM, v.23 n.12, p.676-687, Dec. 1980
	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
	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
	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
	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
	James Gosling, A redisplay algorithm, ACM SIGPLAN Notices, v.16 n.6, p.123-129, June 1981
	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
	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
	Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001
	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
	Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992
	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
	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
	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
	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
	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
	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
	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
	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
	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
	Karen Kukich, Spelling correction for the telecommunications network for the deaf, Communications of the ACM, v.35 n.5, p.80-90, May 1992
	Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980
	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
	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
	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
	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, 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
	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
	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
	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
	Kuo-chung Tai, Fault-tolerant string processing by pattern mapping, Proceedings of the 1977 annual conference, p.336-342, January 1977
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	Yin-Te Tsai, The constrained longest common subsequence problem, Information Processing Letters, v.88 n.4, p.173-176, 30 November 2003
	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
	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
	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
	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
	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
	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
	Menno van Zaanen, ABL: alignment-based learning, Proceedings of the 18th conference on Computational linguistics, July 31-August 04, 2000, Saarbrücken, Germany
	Yves Lepage, Solving analogies on words: an algorithm, Proceedings of the 17th international conference on Computational linguistics, August 10-14, 1998, Montreal, Quebec, Canada
	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
	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
	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
	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
	Kuo-Chung Tai, The Tree-to-Tree Correction Problem, Journal of the ACM (JACM), v.26 n.3, p.422-433, july 1979
	Paul Heckel, A technique for isolating differences between files, Communications of the ACM, v.21 n.4, p.264-268, April 1978
	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
	Robert P. Nix, Editing by example, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.600-621, Oct. 1985
	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
	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
	Steve Meyer, CAD tool interchangeability through Net list translation, ACM SIGDA Newsletter, v.20 n.1, p.51-59, June 1990
	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
	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
	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
	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
	Pierre Courrieu, Straight monotonic embedding of data sets in Euclidean spaces, Neural Networks, v.15 n.10, p.1185-1196, December 2002
	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
	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
	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
	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
	A. Mukherjee, Hardware Algorithms for Determining Similarity Between two Strings, IEEE Transactions on Computers, v.38 n.4, p.600-603, April 1989
	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
	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
	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
	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
	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
	Daniel Gildea , Daniel Jurafsky, Learning bias and phonological-rule induction, Computational Linguistics, v.22 n.4, p.497-530, December 1996
	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
	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
	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
	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
	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
	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
	Hal Berghel, On seamless prototyping, ACM SIGICE Bulletin, v.19 n.3, p.10-17, Feb. 1994
	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
	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
	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
	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
	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
	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
	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
	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
	Jie Wei, Markov Edit Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.3, p.311-321, March 2004
	Masaaki Nagata, Context-based spelling correction for Japanese OCR, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark
	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
	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
	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
	Raghu Sastry , N. Ranganathan, A VLSI Architecture for Approximate Tree Matching, IEEE Transactions on Computers, v.47 n.3, p.346-352, March 1998
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	Pierre Courrieu, Function approximation on non-Euclidean spaces, Neural Networks, v.18 n.1, p.91-102, January 2005
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	Kurt Driessens , Sašo Džeroski, Integrating Guidance into Relational Reinforcement Learning, Machine Learning, v.57 n.3, p.271-304, December 2004
	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
	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
	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
	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
	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
	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
	Veli Mäkinen , Gonzalo Navarro , Esko Ukkonen, Transposition invariant string matching, Journal of Algorithms, v.56 n.2, p.124-153, August 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
	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
	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
	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
	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
	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
	Sébastien L’haire, FipsOrtho: A spell checker for learners of French, ReCALL, v.19 n.2, p.137-161, May 2007
	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
	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
	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
	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
	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
	Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, ACM SIGMOD Record, v.26 n.2, p.26-37, June 1997
	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
	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
	Stoyan Mihov , Klaus U. Schulz, Fast Approximate Search in Large Dictionaries, Computational Linguistics, v.30 n.4, p.451-477, December 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
	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
	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
	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
	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
	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
	Michel Neuhaus , Horst Bunke, Edit distance-based kernel functions for structural pattern classification, Pattern Recognition, v.39 n.10, p.1852-1863, October, 2006
	Huaijun Qiu , Edwin R. Hancock, Graph matching and clustering using spectral partitions, Pattern Recognition, v.39 n.1, p.22-34, January, 2006
	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
	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
	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
	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
	Gary Benson, Tandem cyclic alignment, Discrete Applied Mathematics, v.146 n.2, p.124-133, 1 March 2005
	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
	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
	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
	Joseph A. Brown , Sheridan K. Houghten , Daniel A. Ashlock, Edit metric decoding: a new hope, Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering, May 19-21, 2009, Montreal, Quebec, Canada
	Joystone Gbadamosi , Wolfgang H. Zangemeister, Visual Imagery in Hemianopic Patients, Journal of Cognitive Neuroscience, v.13 n.7, p.855-866, October 2001
	Scott E. Coull , Boleslaw K. Szymanski, Sequence alignment for masquerade detection, Computational Statistics & Data Analysis, v.52 n.8, p.4116-4131, April, 2008
	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
	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
	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
	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
	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
	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
	David Wakeling, EDUCATIONAL PEARL: Biological sequence similarity, Journal of Functional Programming, v.16 n.1, p.1-12, January 2006
	Roland H. C. Yap, Parametric Sequence Alignment with Constraints, Constraints, v.6 n.2-3, p.157-172, June 2001
	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
	Martin Jansche, Learning Local Transductions Is Hard, Journal of Logic, Language and Information, v.13 n.4, p.439-455, March 2004
	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
	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
	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
	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
	Harold Somers, Review Article: Example-based Machine Translation, Machine Translation, v.14 n.2, p.113-157, June 1999
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	Philip Bille , Martin Farach-Colton, Fast and compact regular expression matching, Theoretical Computer Science, v.409 n.3, p.486-496, December, 2008
	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
	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
	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
	Roger Mitton, Ordering the suggestions of a spellchecker without using context*, Natural Language Engineering, v.15 n.2, p.173-192, April 2009
	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
	Stuart Hacking , Benoît Hudzia, Improving the live migration process of large enterprise applications, Proceedings of the 3rd international workshop on Virtualization technologies in distributed computing, June 15-15, 2009, Barcelona, Spain
	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
	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
	Alexander M. Bronstein , Michael M. Bronstein , Alfred M. Bruckstein , Ron Kimmel, Partial Similarity of Objects, or How to Compare a Centaur to a Horse, International Journal of Computer Vision, v.84 n.2, p.163-183, August 2009
	Maria Ruiz-Casado , Enrique Alfonseca , Manabu Okumura , Pablo Castells, Information Extraction and Semantic Annotation of Wikipedia, Proceeding of the 2008 conference on Ontology Learning and Population: Bridging the Gap between Text and Knowledge, p.145-169, June 16, 2008
	Abel Garcia-Najera , John A. Bullinaria, Comparison of similarity measures for the multi-objective vehicle routing problem with time windows, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada
	Marcus Liwicki , Horst Bunke, Combining diverse on-line and off-line systems for handwritten text line recognition, Pattern Recognition, v.42 n.12, p.3254-3263, December, 2009
	Tsuyoshi Kitani , Yoshio Eriguchi , Masami Hara, Pattern matching and discourse processing in information extraction from Japanese text, Journal of Artificial Intelligence Research, v.2 n.1, p.89-110, August 1994
	Bruce Johnson, A bioinformatics-inspired adaptation to Ukkonen's edit distance calculating algorithm, Proceedings of the 46th Annual Southeast Regional Conference on XX, March 28-29, 2008, Auburn, Alabama
	Un Yong Nahm , Raymond J. Mooney, Mining soft-matching rules from textual data, Proceedings of the 17th international joint conference on Artificial intelligence, p.979-984, August 04-10, 2001, Seattle, WA, USA
	Zhenchang Xing , Eleni Stroulia, Analyzing the Evolutionary History of the Logical Design of Object-Oriented Software, IEEE Transactions on Software Engineering, v.31 n.10, p.850-868, October 2005
	G. K. Gupta , R. C. Joyce, Using position extrema points to capture shape in on-line handwritten signature verification, Pattern Recognition, v.40 n.10, p.2811-2817, October, 2007