Minimal Change and Bounded Incremental Parsing

Minimal Change and Bounded Incremental Parsing Mats Wirdn Fachrichttmg 8.7, Computcrlinguistik Universit,~t des Saarlandes Postfach 1150 D-66041 Saarbr/icken, Germany wiren~coli.uni-sb.dc Abstract Ideally, the time that an incremental algorithm uses to process a change should be a fimction of the size of the change rather than, say, the size of the entire current input. Based on a formalization of "the set of things changed" by an increInental modification, this paper investigates how and to what extent it is possibh~' to give such a guarantee for a chart-ba.se(l parsing frmne- work and discusses the general utility of a tninlmality notion in incremental processing) 1 Introduction 1.1 Background Natural-language computing has traditionally been un- derstood as a "batch-mode" or "once-only" process, in which a problem instance P (shy, a text) is mapped as a whole to a solution S (such as air analysis of the text). IIowever, in highly interactive and real-time ap- plications -- for example, grammar checking, structure editing and on-line translation -- what is required is ef- ficient processing of a sequence of small changes of a text. Exhaustive recomlmtation is tber, not a feasible alternative. Rather, to avoid ms much recomputation as possible, each update cycle must re-use those parts of the previous solution that are still wdid. We say that an algorithm is incremental if it rises information from an old solution in computing the new solution. The problem of incremental processing can be stal.ed its follows, using a notation similar to that of All)ern et al. [1]: Assume given a problenr instance P (a represen- tation of the current input), a solution S (the current output), and a modification Ap to p.2 The modifica- tion results in a new problem instance P' = P • At,, where • is a composition operator. The task of an in- 1I would like to thank Ralph RSnnqulst as well as Gregor Erbach and other colleagues in Snarbrfieken for discussions on the material presented here, Peter Fritzson for originally alerting my attention to Ramalingam and tleps' paper, and the anony- mous referees. This research has been flmded by the Cerman Science Foundation (DFG) through the Sonderforschnngsl)erelch 314, project N3 (BiLD). ~A terminological note: we use "input change" and "modifi- cation" as well as "output cllange" and "update" synonymously. z~ p ~ P'=P(DAp As S. ~- S' -- S (I) A s l;'igure 1: Batch-mode versus incremental cornlmtation. cremental algorithm is then to produce an upd~te As in the old solution such that .5' • As is a solution to P(DAp (see figure 1). At this point, nothing is stipula- ted about tim amount, of information it, S tlmt should be re-used in S'. To show properties such im correctness and comple- xity of incremental algorithms, it is necessary to esta- blish a formal measure of "the set of things changed". This me,inure sllouhl capture tim minimal change re- suiting from a modification and, moreover, should be independent of any particular algorithms R)r incremen- tal update. One way of achieving this is …

Content truncated to 500 words