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 argue that a comprehensive theory of reciprocals must rely on a general taxonomy of restrictions on the interpretation of relational expressions. Developing such a taxonomy, we propose a new principle for interpreting reciprocals that relies on the interpretation of the relation in their scope. This principle, the Maximal Interpretation Hypothesis (MIH), analyzes reciprocals as partial polyadic quantifiers. According to the MIH, the partial quantifier denoted by a reciprocal requires the relational expression REL in its scope to denote a maximal (...) relation in REL’s interpretation domain. In this way the MIH avoids a priori assumptions on the available readings of reciprocal expressions, which are necessary in previous accounts. Relying extensively on the work of Dalrymple et al. (Ling Philos 21:159–210, 1998), we show that the MIH also exhibits some observational improvements over Dalrymple et al.’s Strongest Meaning Hypothesis (SMH). In addition to deriving some attested reciprocal interpretations that are not expected by the SMH, the MIH offers a more restrictive account of the way context affects the interpretation of reciprocals through its influence on relational domains. Further, the MIH generates a reciprocal interpretation at the predicate level, which is argued to be advantageous to Dalrymple et al.’s propositional selection of reciprocal meanings. More generally, we argue that by focusing on restrictions on relational domains, the MIH opens the way for a more systematic study of the ways in which lexical meaning, world knowledge and contextual information interact with the interpretation of quantificational expressions. (shrink)

This article proposes a new logical framework for NL quantification. The framework is based on Generalized Quantifiers, Skolem-like functional dependencies, and Maximality of the involved sets of entities. Among the readings available for NL sentences, those where two or more sets of entities are independent of one another are particularly challenging. In the literature, examples of those readings are known as Collective and Cumulative readings. This article briefly analyzes previous approaches to Cumulativity and Collectivity, and indicates (Schwarzschild in Pluralities. Kluwer, (...) Dordrecht, 1996) as the best proposal so far to deal with these readings. Then, it incorporates its insights in the logical framework defined in Robaldo (J Philos Log 39(1):23–58, 2009a), leading to a scalable logical account for NL quantification. (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 article, we describe and attempt to solve a puzzle arising from the interpretation of modified numerals like less than five and between two and five. The puzzle is this: such modified numerals seem to mean different things depending on whether they combine with distributive or non-distributive predicates. When they combine with distributive predicates, they intuitively impose a kind of upper bound, whereas when they combine with non-distributive predicates, they do not. We propose and explore in detail four solutions (...) to this puzzle, each involving some notion of maximality, but differing in the type of maximality involved and in the source of maximality. While the full range of data we consider do not conclusively favor one theory over the other three, we do argue that overall the evidence goes against the view that modified numerals lexically encode a ‘standard’ maximality operator, and suggests the need for a pragmatic blocking mechanism that filters out readings of sentences that are generated by the grammar but intuitively unavailable. (shrink)

Among the readings available for NL sentences, those where two or more sets of entities are independent of one another are particularly challenging from both a theoretical and an empirical point of view. Those readings are termed here as ‘Independent Set (IS) readings'. Standard examples of such readings are the well-known Collective and Cumulative Readings. (Robaldo, 2011) proposes a logical framework that can properly represent the meaning of IS readings in terms of a set-Skolemization of the witness sets. One of (...) the main assumptions of Robaldo's logical framework, drawn from (Schwarzschild, 1996), is that pragmatics plays a crucial role in the identification of such witness sets. Those are firstly identified on pragmatic grounds, then logical clauses are asserted on them in order to trigger the appropriate inferences. In this paper, we present the results of an experimental analysis that appears to confirm Robaldo's hypotheses concerning the pragmatic identification of the witness sets. (shrink)