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.
Similar content being viewed by others
References
Bach K. (1982) Semantic nonspecificity and mixed quantifiers. Linguistics and Philosophy 4(4): 593–605
Barwise J., Cooper R. (1981) Generalized quantifiers and natural language. Linguistics and Philosophy 4: 159–219
Beck S. (2000) The semantics of different: Comparison operator and relational adjective. Linguistics and Philosophy 23(2): 101–139
Ben-Avi G., Winter Y. (2003) Monotonicity and collective quantification. Journal of Logic, Language and Information 12(2): 127–151
Blass A., Gurevich Y. (1986) Henkin quantifiers and complete problems. Annals of Pure and Applied Logic 32: 1–16
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
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
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
Frixione M. (2001) Tractable competence. Minds and Machines 11(3): 379–397
Garey M.R., Johnson D.S. (1979) Computers and intractability. San Francisco, W. H. Freeman and Co.
Gierasimczuk N., Szymanik J. (2009) Branching quantification vs. two-way quantification. The Journal of Semantics 26(4): 329–366
Grädel E., Gurevich Y. (1998) Metafinite model theory. Information and Computation 140(1): 26–81
Hackl M. (2009) On the grammar and processing of proportional quantifiers: Most versus more than half. Natural Language Semantics 17(1): 63–98
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
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
Hintikka J. (1996) Principles of mathematics revisited. Cambridge University Press, Cambridge
Hintikka J., Sandu G. (1997) Game-theoretical semantics. In: Benthem J., Meulen A. (eds) Handbook of logic and language. Elsevier, Amsterdam, pp 361–410
Immerman N. (1998) Descriptive complexity. Texts in Computer Science. Springer, Newyork
Jaszczolt K. (2002) Semantics and pragmatics: Meaning in language and discourse. Longman Linguistics, Library Longman, London
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
Keenan E. (1992) Beyond the Frege boundary. Linguistics and Philosophy 15(2): 199–221
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
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
Kempson R.M., Cormack A. (1981a) Ambiguity and quantification. Linguistics and Philosophy 4(2): 259–309
Kempson R.M., Cormack A. (1981) On ‘formal games and forms for games’. Linguistics and Philosophy 4(3): 431–435
Kempson R.M., Cormack A. (1982) Quantification and pragmatics. Linguistics and Philosophy 4(4): 607–618
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
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
Lindström P. (1966) First order predicate logic with generalized quantifiers. Theoria 32: 186–195
May R. (1985) Logical form: Its structure and derivation. The MIT Press, Linguistic Inquiry Monographs Cambridge, MA
McMillan C.T., Clark R., Moore P., Devita C., Grossman M. (2005) Neural basis for generalized quantifier comprehension. Neuropsychologia 43: 1729–1737
Montague R. (1970) Pragmatics and intensional logic. Dialectica 24(4): 277–302
Moschovakis Y. (2006) A logical calculus of meaning and synonymy. Linguistics and Philosophy 29(1): 27–89
Mostowski A. (1957) On a generalization of quantifiers. Fundamenta Mathematicae 44: 12–36
Mostowski M. (1998) Computational semantics for monadic quantifiers. Journal of Applied Non-Classical Logics 8: 107–121
Mostowski M., Szymanik J. (2007) Computational complexity of some Ramsey quantifiers in finite models. The Bulletin of Symbolic Logic 13: 281–282
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
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
Peters S., Westerståhl D. (2006) Quantifiers in language and logic. Clarendon Press, Oxford
Pietroski P., Lidz J., Hunter T., Halberda J. (2009) The meaning of 'most': Semantics, numerosity, and psychology. Mind and Language 24: 54–85
Ristad E.S. (1993) The language complexity game. Artificial Intelligence. The MIT Press, Cambridge, MA
Robaldo L. (2009) Independent set readings and generalized quantifiers. Journal of Philosophical Logic 39(1): 23–58
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
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
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
Turing A. (1936) On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 42(2): 230–265
Väänänen J. (1997) Unary quantifiers on finite models. Journal of Logic, Language and Information 6(3): 275–304
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
van Benthem J. (1989) Polyadic quantifiers. Linguistics and Philosophy 12(4): 437–464
van Rooij I. (2008) The tractable cognition thesis. Cognitive Science: A Multidisciplinary Journal 32(6): 939–984
Author information
Authors and Affiliations
Corresponding author
Rights 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
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10988-010-9076-z