Order-n correction for regular languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Order-n correction for regular languages

Full text

Pdf (389 KB)

Source

Communications of the ACM archive
Volume 17 , Issue 5 (May 1974) table of contents

Pages: 265 - 268

Year of Publication: 1974

ISSN:0001-0782

Author

Robert A. Wagner

Vanderbilt Univ., Nashville, TN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 30, Citation Count: 11

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/360980.360995 What is a DOI?

ABSTRACT

A method is presented for calculating a string B, belonging to a given regular language L, which is “nearest” (in number of edit operations) to a given input string &agr;. B is viewed as a reasonable “correction” for the possibly erroneous string &agr;, where &agr; was originally intended to be a string of L. The calculation of B by the method presented requires time proportional to |&agr;|, the number of characters in &agr;. The method should find applications in information retrieval, artificial intelligence, and spelling correction systems.

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	R. W. Conway , W. L. Maxwell, CORC—the Cornell computing language, Communications of the ACM, v.6 n.6, p.317-321, June 1963 [doi>10.1145/366604.366651]
	2	Morgan, H.L., and Wagner, R.A. PL/C--A high performance compiler for PL/I. Proc. 1971 SJCC, Vol. 38, AFIPS Press, Montvale, N.J., pp. 503-510.
	3	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]
	4	Wagner, R.A. An n 3 minimum edit distance correction algorithm for context free languages. Tech. Rep., Systems and Information Science Dep., Vanderbilt U., Nashville, Tenn., 1972.
	5	Nemhauser, G,L. introduction to Dynamic Programming. Wiley, New York, 1966.
	6	Wagner, R.A. The string-to-string correction problem. Tech. Rep., Systems and Information Sciences Dep., Vanderbilt U., Nashville, Tenn., 1971.
	7	Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
	8	David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
	9	Jacques Emmett Lafrance, Syntax-directed error recovery for compilers, 1971
	10	E. T. Irons, An error-correcting parse algorithm, Communications of the ACM, v.6 n.11, p.669-673, Nov. 1963 [doi>10.1145/368310.368385]
	11	Ronald Paul Leinius, Error detection and recovery for syntax directed compiler systems, 1970
	12	Jean-Pierre Levy, Automatic correction of syntax errors in programming languages, 1971

CITED BY 11

	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
	G. K. Gupta, Technical correspondence: measuring the level of computerization in a country, Communications of the ACM, v.24 n.9, p.607-608, Sept. 1981
	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976
	J. C. Winterton, Technical correspondence: on price/performance in U.S. computer systems, Communications of the ACM, v.24 n.9, p.606, Sept. 1981
	Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992
	Michael R. Dunlavey , Lance A. Miller, Technical corrections: Onspelling correction and beyond, Communications of the ACM, v.24 n.9, p.608-609, Sept. 1981
	William F. Opdyke , Ralph E. Johnson, Creating abstract superclasses by refactoring, Proceedings of the 1993 ACM conference on Computer science, p.66-73, February 16-18, 1993, Indianapolis, Indiana, United States
	Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980
	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
	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
	Stavros Konstantinidis, Computing the edit distance of a regular language, Information and Computation, v.205 n.9, p.1307-1316, September, 2007