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