Order-n Correction for Regular Languages

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 a.  B is viewed as a reasonable 
"correction" for the possibly erroneous string a, where
a was originally intended to be a string of L. 
 The calculation of B by the method presented requires
time proportional to |a|, the number of characters 
in a.  The method should find applications in information
retrieval, artificial intelligence, and spelling 
correction systems.

CACM May, 1974

Wagner, R. A.

error correction, regular languages, regular events,
finite state automata, compiler error recovery, 
spelling correction, string best match problem, correction,
corrector, errors, nondeterministic finite-state 
automata

4.12 4.20 5.22 5.23 5.42

CA740503 JB January 17, 1978  4:26 PM

1179	4	2650
1225	4	2650
1288	4	2650
1350	4	2650
1544	4	2650
1646	4	2650
1646	4	2650
1781	4	2650
1846	4	2650
1945	4	2650
2111	4	2650
2534	4	2650
2534	4	2650
2556	4	2650
2556	4	2650
2630	4	2650
2650	4	2650
2650	4	2650
2650	4	2650
2650	4	2650
2698	4	2650
2708	4	2650
2708	4	2650
2887	4	2650
3093	4	2650
2111	5	2650
2650	5	2650
2650	5	2650
2650	5	2650
576	5	2650
680	5	2650
830	5	2650