An Algorithm for Generating Non-Redundant Quantifier Scopings

AN ALGORITHM FOR GENERATING NON-REDUNDANT QUANTIFIER SCOPINGS Espen J. Vestre Department of Mathematics University of Oslo P.O. Box 1053 Blindern N-0316 OSLO 3, Norway Internet: espen@math.uio.no ABSTRACT This paper describes an algorithm for generat- ing quantifier scopings. The algorithm is designed to generate only logically non-redundant scopings and to partially order the scopings with a given :default scoping first. Removing logical redundancy is not only interesting per se, but also drastically reduces the processing time. The input and output formats are described through a few access and construc- tion functions. Thus, the algorithm is interesting for a modular linguistic theory, which is flexible with re- spect to syntactic and semantic framework. INTRODUCTION Natural language sentences like the notorious (1) Every man loves a woman, are usually regarded to be scope ambiguous. There have been two ways to attack this problem: To generate the most probable scoping and ignore the rest, or to generate all theoretically possible scopings. Choosing the first alternative is actually not a bad solution, since any sample piece of tex t usually contains few possibilities for (real) scope ambiguity, and since reasonable heuristics in most cases pick out the intended reading. However, there are cases which seem to be genuinely ambiguous, or where the selection of the intended reading requires exten- sive world knowledge. If the second alternative is chosen, there are basically two possible approaches: To integrate the generation of scopings into the grammar (like e.g. in Johnson and Kay (90) or Halvorsen and? Kaplan (88)), or to devise a procedure that generates the scopings from the parse output (like in Hobbs and Shieber (87)). In both cases, only structurally im- possible scopings are ruled out, like the reading of (2) Every representative of a company saw most samples in which "most samples" is outscoped by "every representative" but outscopes "a company" (Hobbs and Shieber (87)). Logically equivalent readings are not ruled out on either of these proposals. Hobbs and Shieber argue that "When we move beyond the two first- order quantifiers to deal with the so-called generalized quantifiers, such as "most", these logical redundancies become quite rare". Theoretically, they become rare. But it may very well be that sentences with several occur- rences of non-first-order generalized quantifiers are not very commonly used. On the other hand, sen- tences with several occurrences of existential or universal quantifiers may be quite common. What kinds of expressions that really resemble first-order quantifiers is of course a controversial question. But working natural language systems, with inference mechanisms that are based on f'trst-order logic, often have to simplify the interpretation process by inter- preting broad classes of expressions as plain univer- sal or existential quantifiers. Thus, the gain of gen- erating only non-equivalent scopings may be quite significant in practical systems. Ordering of the scopings according to preference is also not treated on approaches like that of Hobbs & Shieber (87) or Johnson & Kay (90). Hobbs & Shieber (87) are quite aware of this, and give some suggestions on …

Content truncated to 500 words