Skip to content
Publications

Talk · International Conference on Implementation and application of automata · July 3, 2002

Searching for asymptotic error repair

Jesús Vilares, Víctor Manuel Darriba Bilbao, Miguel Á. Alonso

Abstract

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)

Natural Language Processing Techniquessemigroups and automata theoryLogic, programming, and type systemserror repairdynamic validationasymptotic equivalence

More by Miguel Alonso