Magic for Filter Optimization in Dynamic Bottom-Up Processing

Magic for Filter Optimization in Dynamic Bottom-up Processing Guido Minnen* SFB 340, University of Tfibingen Kleine Wilhelmstrafle. 113 D-72074 Tiibingen, Germany e-mail : minnen~sf s. nphil, uni-tuebingen, de Abstract Off-line compilation of logic grammars us- ing Magic allows an incorporation of fil- tering into the logic underlying the gram- mar. The explicit definite clause charac- terization of filtering resulting from Magic compilation allows processor independent and logically clean optimizations of dy- namic bottom-up processing with respect to goal-directedness. Two filter optimizations based on the program transformation tech- nique of Unfolding are discussed which are of practical and theoretical interest. 1 Introduction In natural language processing filtering is used to weed out those search paths that are redundant, i.e., are not going to be used in the proof tree corre- sponding to the natural language expression to be generated or parsed. Filter optimization often com- prises an extension of a specific processing strategy such that it exploits specific knowledge about gram- mars and/or the computational task(s) that one is using them for. At the same time it often remains unclear how these optimizations relate to each other and what they actually mean. In this paper I show how starting from a definite clause characterization of filtering derived automatically from a logic gram- mar using Magic compilation, filter optimizations can be performed in a processor independent and logically clean fashion. Magic (templates) is a general compilation tech- nique for efficient bottom-up evaluation of logic pro- grams developed in the deductive database commu- nity (Ramakrishnan et al., 1992). Given a logic pro- gram, Magic produces a new program in which the filtering as normally resulting from top-down eval- uation is explicitly characterized through, so-called, *url: http://www.sfs.nphil.uni-tuebingen/'minnen magic predicates, which produce variable bindings for filtering when evaluated bottom-up. The origi- nal rules of the program are extended such that these bindings can be made effective. As a result of the definite clause characterization of filtering, Magic brings filtering into the logic un- derlying the grammar. I discuss two filter optimiza- tions. These optimizations are direction indepen- dent in the sense that they are useful for both gen- eration and parsing. For expository reasons, though, they are presented merely on the basis of examples of generation. Magic compilation does not limit the informa- tion that can be used for filtering. This can lead to nontermination as the tree fragments enumer- ated in bottom-up evaluation of magic compiled grammars are connected (Johnson, forthcoming). More specifically, 'magic generation' falls prey to non-termination in the face of head recursion, i.e., the generation analog of left recursion in parsing. This necessitates a dynamic processing strategy, i.e., memoization, extended with an abstraction function like, e.g., restriction (Shieber, 1985), to weaken fil- tering and a subsumption check to discard redun- dant results. It is shown that for a large class of grammars the subsumption check which often influ- ences processing efficiency rather dramatically can be eliminated through fine-tuning of the magic pred- icates derived for a particular grammar after apply- ing …

Content truncated to 500 words