Access Restriction

Author Wagner, Robert A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Errors ♦ Nondeterministic finite-state automata ♦ Regular languages ♦ Spelling correction ♦ Corrector ♦ Compiler error recovery ♦ Finite state automata ♦ Regular events ♦ Error correction ♦ Correction ♦ String best match problem
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 α. B is viewed as a reasonable “correction” for the possibly erroneous string α, where α was originally intended to be a string of L. The calculation of B by the method presented requires time proportional to |α|, the number of characters in α. The method should find applications in information retrieval, artificial intelligence, and spelling correction systems.
Description Affiliation: Vanderbilt Univ., Nashville, TN (Wagner, Robert A.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 17
Issue Number 5
Page Count 4
Starting Page 265
Ending Page 268

Open content in new tab

   Open content in new tab
Source: ACM Digital Library