Order- n correction for regular languages
- 1 May 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 17 (5) , 265-268
- https://doi.org/10.1145/360980.360995
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.Keywords
This publication has 4 references indexed in Scilit:
- Spelling correction in systems programsCommunications of the ACM, 1970
- An error-correcting parse algorithmCommunications of the ACM, 1963
- CORC—the Cornell computing languageCommunications of the ACM, 1963
- Algorithm 97: Shortest pathCommunications of the ACM, 1962