Elamur Research⌕
☰
home / papers / 1987 / An Algorithm for Generating Quantifier Scopings

An Algorithm for Generating Quantifier Scopings

Paper · 1987 · Jerry R. Hobbs and Stuart M. Shieber

Summary

Syntax usually makes predicate-argument structure clear, but it does not show how quantifiers and modals scope over one another. Earlier systems either ignored scope or used vague or over-generous mechanisms. The common one simply permutes the quantifiers, giving n! readings, many of them structurally impossible. Hobbs and Shieber present an explicit algorithm, with nondeterministic and deterministic versions, that turns an unscoped predicate-argument encoding into fully scoped logical forms.

The input uses "complex terms", which are triples of quantifier, variable and restriction. The output uses three-part quantified formulas (variable, restriction, body), following Woods and Moore. Terms are pulled out from the inside outward. A term may be applied only if every variable free in it is also free in the surrounding formula. The authors prove this rule never yields unbound variables.

The algorithm produces exactly the structurally legitimate scopings and also handles scope relative to opaque operators such as negation. It is meant as a sound, complete benchmark and as a base for heuristic, efficiency-oriented scoping.

Key points

  • For the example sentence in which each company's representatives are said to have seen the majority of samples, permuting the quantifiers yields 6 readings, of which just 5 are valid. For a five-quantifier example sentence, 42 readings are valid versus the 120 that permutation produces.
  • The excluded readings follow from separating restriction and body. A quantifier from elsewhere in the sentence cannot fall between a head noun's quantifier and the quantifier of a noun phrase inside that noun's complement.
  • Cooper storage is criticised because, for such readings, it produces expressions with an unbound variable and a vacuous quantifier.
  • Opaque operators are covered: "Everyone isn't here" receives two readings.
  • Ordering heuristics, such as keeping left-to-right order or giving wide scope to PP complements, can be added by steering the nondeterministic choices, though only to a limited extent. Donkey sentences fall outside the algorithm because their input structures are ill-formed.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States434 works · 314,419 citations🔬SRI InternationalMenlo Park · United States23 works · 7,208 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

Cite

Cite as Jerry R. Hobbs and Stuart M. Shieber. 1987. An Algorithm for Generating Quantifier Scopings. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@article{hobbs1987algorithm,
  title = {{An Algorithm for Generating Quantifier Scopings}},
  author = {Jerry R. Hobbs and Stuart M. Shieber},
  journal = {Computational Linguistics},
  year = {1987},
  url = {https://aclanthology.org/J87-1005/}
}

References

10 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Barwisc, Jon and Coopcr, Robin 1981 Generalized Quantificrs and Natural Language. Linguistics attd Philosophy 4(2): 159-219. find
  2. Cooper, Robin 1 9 8 3 Quant~[Tcation and Syntactic Theory. Rcidcl, Dordrecht. find
  3. Cushing, Stevcn 1976 Thc Formal Semantics of Quantification. Ph.D. dissertation. Univcrsity of California, Los Angclcs. find
  4. Grosz, Barbara J.; Appclt, Douglas E.; Martin, Paul; Pcreira, Fcrnando C.N.; and Shinkle, Lorna 1 9 8 5 The TEAM Natural-Language Interface System. Final Report, Project 4865. Artificial Intclligcnce Center, SRI International, Menlo Park, California. find
  5. Hobbs, Jcrry R. 1983 An Improper Treatment of Quantification in Ordinary English. In Proceedings 9[" the 21st Annual Meeting ¢~/" the Association for Computational Linguistics. Cambridge, Massachusetts: 57-63.
  6. Keller, William 1986 Nested Cooper Storage. Paper presented at thc Workshop on Word Order and Parsing in Unification Grammars, Friedcnweiler, West Germany (7- I I April). find
  7. Montaguc, Richard 1973 The Propcr Trcatmcnt of Quantification in Ordinary English. In Thomason, R., Ed., Formal Philosopl¢y. Selected Papers of Richard Montague. Yale University Press, Ncw Haven, Connecticut. find
  8. Moore, Robert C. 1981 Problems in Logical Fornl. In Proceedings ¢~/" the 19th Annual Meet\#lg of the Association .[br Computational Linguistics. Stanford, California: 117-124. find
  9. Pcreira, Fernando C.N. 1983 Logic for Natural Language Analysis. Technical Note 275. Artificial Intelligence Center, SRI International, Menlo Park, California. find
  10. Woods, William 1 9 7 7 Semantics and Quantification in Natural Language Question Answering. Adwmces in Computers. Vohtme 17. Academic Press, New York: 1-87. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/hobbs-1987-algorithm-generating-quantifier-scopings/