An Extension of the String-to-String Correction Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Extension of the String-to-String Correction Problem

Full text

Pdf (445 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 2 (April 1975) table of contents

Pages: 177 - 183

Year of Publication: 1975

ISSN:0004-5411

Authors

Robert A. Wagner	Department of Systems and Information Sciences, Vanderbilt University, Nashville, TN
Roy Lowrance	255 West Squire Drive, Rochester, NY and Vanderbilt University, Nashville, Tennessee

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 131, Citation Count: 45

Additional Information:

references cited by index terms collaborative colleagues

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

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

REFERENCES

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

Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]

CITED BY 46

	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
	Kuo-chung Tai, Fault-tolerant string processing by pattern mapping, Proceedings of the 1977 annual conference, p.336-342, January 1977
	Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992
	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
	Amihood Amir , Richard Cole , Ramesh Hariharan , Moshe Lewenstein , Ely Porat, Overlap matching, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.279-288, January 07-09, 2001, Washington, D.C., United States
	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
	Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980
	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
	Gonzalo Navarro , Ricardo Baeza-Yates , João Marcelo Azevedo Arcoverde, Matchsimile: a flexible approximate matching tool for searching proper names, Journal of the American Society for Information Science and Technology, v.54 n.1, p.3-15, January 2003
	Amihood Amir , Moshe Lewenstein , Ely Porat, Faster algorithms for string matching with k mismatches, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.794-803, January 09-11, 2000, San Francisco, California, United States
	Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985
	Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001
	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
	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
	W. J. Hsu, New algorithms for comparing symbol sequences, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.381-389, December 1987, Dallas, Texas, United States
	Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977
	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
	Amihood Amir , Moshe Lewenstein , Ely Porat, Approximate swapped matching, Information Processing Letters, v.83 n.1, p.33-39, 16 July 2002
	Amihood Amir , Richard Cole , Ramesh Hariharan , Moshe Lewenstein , Ely Porat, Overlap matching, Information and Computation, v.181 n.1, p.57-74, 25 February 2003
	Kuo-Chung Tai, The Tree-to-Tree Correction Problem, Journal of the ACM (JACM), v.26 n.3, p.422-433, july 1979
	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
	Amihood Amir , Moshe Lewenstein , Ely Porat, Faster algorithms for string matching with k mismatches, Journal of Algorithms, v.50 n.2, p.257-275, February 2004
	James L. Peterson, Computer programs for detecting and correcting spelling errors, Communications of the ACM, v.23 n.12, p.676-687, Dec. 1980
	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
	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
	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
	Hal Berghel, On seamless prototyping, ACM SIGICE Bulletin, v.19 n.3, p.10-17, Feb. 1994
	Jie Wei, Markov Edit Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.3, p.311-321, March 2004
	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
	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
	Pierre Courrieu, Function approximation on non-Euclidean spaces, Neural Networks, v.18 n.1, p.91-102, January 2005
	R. S. Valiveti , B. J. Oommen, Recognizing Sources of Random Strings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.4, p.386-394, April 1991
	Amihood Amir , Yonatan Aumann , Gary Benson , Avivit Levy , Ohad Lipsky , Ely Porat , Steven Skiena , Uzi Vishne, Pattern matching with address errors: rearrangement distances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1221-1229, January 22-26, 2006, Miami, Florida
	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
	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
	Amihood Amir , Eran Chencinski , Costas Iliopoulos , Tsvi Kopelowitz , Hui Zhang, Property matching and weighted matching, Theoretical Computer Science, v.395 n.2-3, p.298-310, May, 2008
	Amihood Amir , Gad M. Landau , Moshe Lewenstein , Dina Sokol, Dynamic text and static pattern matching, ACM Transactions on Algorithms (TALG), v.3 n.2, p.19-es, 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
	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
	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
	Ely Porat , Klim Efremenko, Approximating general metric distances between a pattern and a text, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.419-427, January 20-22, 2008, San Francisco, California
	Benny Porat , Ely Porat , Asaf Zur, Note: Pattern matching with pair correlation distance, Theoretical Computer Science, v.407 n.1-3, p.587-590, November, 2008
	Amihood Amir , Yonatan Aumann , Gary Benson , Avivit Levy , Ohad Lipsky , Ely Porat , Steven Skiena , Uzi Vishne, Pattern matching with address errors: Rearrangement distances, Journal of Computer and System Sciences, v.75 n.6, p.359-370, September, 2009