Skip to main content
SpringerLink
Log in

Computational complexity of polyadic lifts of generalized quantifiers in natural language

  • Research Article
  • Published:
Linguistics and Philosophy Aims and scope Submit manuscript

Abstract

We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results to investigate semantic distinctions between quantified reciprocal sentences. We show a computational dichotomy between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility of revising the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of formal semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bach K. (1982) Semantic nonspecificity and mixed quantifiers. Linguistics and Philosophy 4(4): 593–605

    Article  Google Scholar 

  • Barwise J., Cooper R. (1981) Generalized quantifiers and natural language. Linguistics and Philosophy 4: 159–219

    Article  Google Scholar 

  • Beck S. (2000) The semantics of different: Comparison operator and relational adjective. Linguistics and Philosophy 23(2): 101–139

    Article  Google Scholar 

  • Ben-Avi G., Winter Y. (2003) Monotonicity and collective quantification. Journal of Logic, Language and Information 12(2): 127–151

    Article  Google Scholar 

  • Blass A., Gurevich Y. (1986) Henkin quantifiers and complete problems. Annals of Pure and Applied Logic 32: 1–16

    Article  Google Scholar 

  • Bott, O., & Radó , J. (2009). How to provide exactly one interpretation for every sentence, or what eye movements reveal about quantifier scope. In S. Winkler, & S. Featherson, (Eds.), The fruits of empirical linguistics, Vol. 1. Berlin: Walther de Gruyter.

  • Cherniak C. (1981) Minimal rationality. Mind 90(358): 161–183

    Article  Google Scholar 

  • Cook, S.A. (1971). The complexity of theorem-proving procedures. In STOC ’71: Proceedings of the third annual ACM symposium on theory of computing (pp. 151–158). ACM Press: New York, NY.

  • Dalrymple M., Kanazawa M., Kim Y., Mchombo S., Peters S. (1998) Reciprocal expressions and the concept of reciprocity. Linguistics and Philosophy 21: 159–210

    Article  Google Scholar 

  • Frege, G. (1879). Begriffsschrift: eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle.

  • Frege G. (1892) Über Sinn und Bedeutung. Zeitschrift für Philosophie und philosophische Kritik 100: 25–50

    Google Scholar 

  • Frixione M. (2001) Tractable competence. Minds and Machines 11(3): 379–397

    Article  Google Scholar 

  • Garey M.R., Johnson D.S. (1979) Computers and intractability. San Francisco, W. H. Freeman and Co.

    Google Scholar 

  • Gierasimczuk N., Szymanik J. (2009) Branching quantification vs. two-way quantification. The Journal of Semantics 26(4): 329–366

    Article  Google Scholar 

  • Grädel E., Gurevich Y. (1998) Metafinite model theory. Information and Computation 140(1): 26–81

    Article  Google Scholar 

  • Hackl M. (2009) On the grammar and processing of proportional quantifiers: Most versus more than half. Natural Language Semantics 17(1): 63–98

    Article  Google Scholar 

  • Hella L., Väänänen J., Westerståhl D. (1997) Definability of polyadic lifts of generalized quantifiers. Journal of Logic, Language and Information 6(3): 305–335

    Article  Google Scholar 

  • Henkin, L. (1961). Some remarks on infinitely long formulas. In Infinistic methods (pp. 167–183). Oxford: Pergamon Press.

  • Hintikka J. (1973) Quantifiers vs. quantification theory. Dialectica 27: 329–358

    Article  Google Scholar 

  • Hintikka J. (1996) Principles of mathematics revisited. Cambridge University Press, Cambridge

    Book  Google Scholar 

  • Hintikka J., Sandu G. (1997) Game-theoretical semantics. In: Benthem J., Meulen A. (eds) Handbook of logic and language. Elsevier, Amsterdam, pp 361–410

    Chapter  Google Scholar 

  • Immerman N. (1998) Descriptive complexity. Texts in Computer Science. Springer, Newyork

    Google Scholar 

  • Jaszczolt K. (2002) Semantics and pragmatics: Meaning in language and discourse. Longman Linguistics, Library Longman, London

    Google Scholar 

  • Karp R.M. (1972) Reducibility among combinatorial problems. In: Miller R.E., Thatcher J.W. (eds) Complexity of computer computations. Plenum Press, New York, pp 85–103

    Google Scholar 

  • Keenan E. (1992) Beyond the Frege boundary. Linguistics and Philosophy 15(2): 199–221

    Article  Google Scholar 

  • Keenan E. (1996) Further beyond the Frege boundary. In: Does J., Eijck J. (eds) Quantifiers, logic, and language. CSLI Lecture Notes. Stanford University, California, pp 179–201

    Google Scholar 

  • Keenan E., Westerståhl D. (1997) Generalized quantifiers in linguistics and logic. In: Benthem J., Meulen A. (eds) Handbook of logic and language. Elsevier, Amsterdam, pp 837–895

    Chapter  Google Scholar 

  • Kempson R.M., Cormack A. (1981a) Ambiguity and quantification. Linguistics and Philosophy 4(2): 259–309

    Article  Google Scholar 

  • Kempson R.M., Cormack A. (1981) On ‘formal games and forms for games’. Linguistics and Philosophy 4(3): 431–435

    Article  Google Scholar 

  • Kempson R.M., Cormack A. (1982) Quantification and pragmatics. Linguistics and Philosophy 4(4): 607–618

    Article  Google Scholar 

  • Krynicki M., Mostowski M. (1995) Henkin quantifiers. In: Krynicki M., Mostowski M., Szczerba L. (eds) Quantifiers: logics, models and computation. Dordercht, Kluwer Academic Publishers, pp 193–263

    Google Scholar 

  • Landman, F. (2000). Against binary quantifiers. In Events and plurality. Studies in Linguistic and Philosophy (pp. 310–349). Dordercht: Kluwer Academic Publisher

  • Levesque H.J. (1988) Logic and the complexity of reasoning. Journal of Philosophical Logic 17(4): 355–389

    Article  Google Scholar 

  • Lindström P. (1966) First order predicate logic with generalized quantifiers. Theoria 32: 186–195

    Google Scholar 

  • May R. (1985) Logical form: Its structure and derivation. The MIT Press, Linguistic Inquiry Monographs Cambridge, MA

    Google Scholar 

  • McMillan C.T., Clark R., Moore P., Devita C., Grossman M. (2005) Neural basis for generalized quantifier comprehension. Neuropsychologia 43: 1729–1737

    Article  Google Scholar 

  • Montague R. (1970) Pragmatics and intensional logic. Dialectica 24(4): 277–302

    Article  Google Scholar 

  • Moschovakis Y. (2006) A logical calculus of meaning and synonymy. Linguistics and Philosophy 29(1): 27–89

    Article  Google Scholar 

  • Mostowski A. (1957) On a generalization of quantifiers. Fundamenta Mathematicae 44: 12–36

    Google Scholar 

  • Mostowski M. (1998) Computational semantics for monadic quantifiers. Journal of Applied Non-Classical Logics 8: 107–121

    Google Scholar 

  • Mostowski M., Szymanik J. (2007) Computational complexity of some Ramsey quantifiers in finite models. The Bulletin of Symbolic Logic 13: 281–282

    Google Scholar 

  • Mostowski M., Wojtyniak D. (2004) Computational complexity of the semantics of some natural language constructions. Annals of Pure and Applied Logic 127(13): 219–227

    Article  Google Scholar 

  • Otto, M. (1997). Bounded variable logics and counting. A study in finite models. Volume 9 of Lecture Notes in Logic. Berlin: Springer-Verlag.

  • Papadimitriou C.H. (1993) Computational complexity. Redwood City, CA, Addison Wesley

    Google Scholar 

  • Peters S., Westerståhl D. (2006) Quantifiers in language and logic. Clarendon Press, Oxford

    Google Scholar 

  • Pietroski P., Lidz J., Hunter T., Halberda J. (2009) The meaning of 'most': Semantics, numerosity, and psychology. Mind and Language 24: 54–85

    Article  Google Scholar 

  • Ristad E.S. (1993) The language complexity game. Artificial Intelligence. The MIT Press, Cambridge, MA

    Google Scholar 

  • Robaldo L. (2009) Independent set readings and generalized quantifiers. Journal of Philosophical Logic 39(1): 23–58

    Article  Google Scholar 

  • Sabato, S., & Winter, Y. (2005). From semantic restrictions to reciprocal meanings. In Proceedings of FG-MOL 2005. CSLI Publications.

  • Sevenster, M. (2006). Branches of imperfect information: Logic, games, and computation. PhD thesis, Universiteit van Amsterdam. http://www.illc.uva.nl/Publications/Dissertations/DS-2006-06.text.pdf.

  • Sher G. (1990) Ways of branching quantifiers. Linguistics and Philosophy 13: 393–442

    Article  Google Scholar 

  • Szymanik, J. (2009). Quantifiers in TIME and SPACE. Computational complexity of generalized quantifiers in natural language. PhD thesis, Universiteit van Amsterdam. http://www.illc.uva.nl/Publications/ResearchReports/DS-2009-01.text.pdf.

  • Szymanik J., Zajenkowski M. (2010a) Comprehension of simple quantifiers. Empirical evaluation of a computational model. Cognitive Science: A Multidisciplinary Journal 34(3): 521–532

    Article  Google Scholar 

  • Szymanik, J., Zajenkowski, M. (2010b). Quantifiers and working memory. In M. Aloni, & K. Schulz, (Eds.), Amsterdam Colloquium 2009. Lecture Notes in Artificial Intelligence 6042 (pp. 456–464). Berlin: Springer.

  • Tennant N. (1981) Formal games and forms for games. Linguistics and Philosophy 4(2): 311–320

    Article  Google Scholar 

  • Turing A. (1936) On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 42(2): 230–265

    Google Scholar 

  • Väänänen J. (1997) Unary quantifiers on finite models. Journal of Logic, Language and Information 6(3): 275–304

    Article  Google Scholar 

  • Väänänen J. (2007). Dependence logic—a new approach to independence friendly logic. London Mathematical Society Student Texts. Cambridge: Cambridge University Press.

  • van Benthem J. (1986) Essays in logical semantics. Reidel, Dordercht

    Google Scholar 

  • van Benthem J. (1989) Polyadic quantifiers. Linguistics and Philosophy 12(4): 437–464

    Article  Google Scholar 

  • van Rooij I. (2008) The tractable cognition thesis. Cognitive Science: A Multidisciplinary Journal 32(6): 939–984

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Philosophy, Stockholm University, Stockholm, Sweden

    Jakub Szymanik

Authors
  1. Jakub Szymanik
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jakub Szymanik.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Szymanik, J. Computational complexity of polyadic lifts of generalized quantifiers in natural language. Linguist and Philos 33, 215–250 (2010). https://doi.org/10.1007/s10988-010-9076-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10988-010-9076-z

Keywords

Search

Navigation