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<br>between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility to<br>revise 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 the formal<br>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. (shrink)

We consider collective quantification in natural language. For many years the common strategy in formalizing collective quantification has been to define the meanings of collective determiners, quantifying over collections, using certain type-shifting operations. These type-shifting operations, i.e., lifts, define the collective interpretations of determiners systematically from the standard meanings of quantifiers. All the lifts considered in the literature turn out to be definable in second-order logic. We argue that second-order definable quantifiers are probably not expressive enough to formalize all collective (...) quantification in natural language. (shrink)

In this paper, we study natural language constructions which were first examined by Barwise: The richer the country, the more powerful some of its officials. Guided by Barwise’s observations, we suggest that conceivable interpretations of such constructions express the existence of various similarities between partial orders such as homomorphism or embedding. Semantically, we interpret the constructions as polyadic generalized quantifiers restricted to finite models. We extend the results obtained by Barwise by showing that similarity quantifiers are not expressible in elementary (...) logic over finite models. We also investigate whether the proposed readings are sound from the cognitive perspective. We prove that almost all similarity quantifiers are intractable. This leads us to first-order variants, which only approximate the strong readings, but are cognitively more plausible. Driven by the question of ambiguity, we recall Barwise’s argumentation in favour of strong readings, enriching it with some arguments of our own. Given that Barwise-like sentences are indeed ambiguous, we use a generalized Strong Meaning Hypothesis to derive predictions for their verification. Finally, we propose a hypothesis according to which conflicting pressures of communication and cognition might give rise to an ambiguous construction, provided that different semantic variants of the construction withstand different pressures involved in its usage. (shrink)

This paper revisits a challenge for contextualist approaches to paradoxes such as the Liar paradox and Russell’s paradox. Contextualists argue that these paradoxes are to be resolved by appeal to context dependence. This can offer some nice and effective ways to avoid paradox. But there is a problem. Context dependence is, at least to begin with, a phenomenon in natural language. Is there really such context dependence as the solutions to paradoxes require, and is it really just a familiar linguistic (...) phenomenon at work? Not so clearly. In earlier work, I argued that the required form of context dependence does not look like our most familiar instances of context dependence in natural language. I called this extraordinary context dependence. In this paper, I shall explore, somewhat tentatively, a way that we can see the context dependence needed to address paradoxes as not so extraordinary. Doing so will also allow us to connect thinking about the context dependence of quantifier domains with some interesting ideas about the distinctive semantic properties of certain quantifiers. (shrink)

This paper revisits a challenge for contextualist approaches to paradoxes such as the Liar paradox and Russell’s paradox. Contextualists argue that these paradoxes are to be resolved by appeal to context dependence. This can offer some nice and effective ways to avoid paradox. But there is a problem. Context dependence is, at least to begin with, a phenomenon in natural language. Is there really such context dependence as the solutions to paradoxes require, and is it really just a familiar linguistic (...) phenomenon at work? Not so clearly. In earlier work, I argued that the required form of context dependence does not look like our most familiar instances of context dependence in natural language. I called this extraordinary context dependence. In this paper, I shall explore, somewhat tentatively, a way that we can see the context dependence needed to address paradoxes as not so extraordinary. Doing so will also allow us to connect thinking about the context dependence of quantifier domains with some interesting ideas about the distinctive semantic properties of certain quantifiers. (shrink)