Searching for asymptotic error repair

Abstract. We work in the domain of a regional least-cost strategy with dynamic validation in order to avoid cascaded errors [3], extending the theoretical model to illustrate its asymptotic equivalence with global repair algorithms. This is an objective criterion to measure the quality of an error repair algorithm, since the point of reference is a technique that guarantees the best quality for a given error metric when all contextual information is available. To the best of our knowledge, it is the first time that such a discussion takes place. We also reformulate the parsing framework using parsing schemata [1], simplifying the description. 1 The parsing model Our aim is to parse a sentence w1...n = w1... wn according to an unrestricted context-free grammar G = (N, Σ, P, S), where the empty string is represented by ε. We generate from G a push-down automaton (pda) for the language L(G). In practice, we chose an lalr(1) device generated by Ice [2], although any shiftreduce strategy is adequate. A pda is a 7-tuple A = (Q, Σ, ∆, δ, q0, Z0, Qf