Quantification is a topic which brings together linguistics, logic, and philosophy. Quantifiers are the essential tools with which, in language or logic, we refer to quantity of things or amount of stuff. In English they include such expressions as no, some, all, both, many. Peters and Westerstahl present the definitive interdisciplinary exploration of how they work - their syntax, semantics, and inferential role.

Quantification is a topic which brings together linguistics, logic, and philosophy. Quantifiers are the essential tools with which, in language or logic, we refer to quantity of things or amount of stuff. In English they include such expressions as no, some, all, both, many. Peters and Westerstahl present the definitive interdisciplinary exploration of how they work - their syntax, semantics, and inferential role.

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. (...) Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

As Quine observed, the following sentence has a reading which, if true, would be of special interest to the authorities: Ralph believes that someone is a spy. This is the reading where the quantifier is naturally understood as taking wide scope relative to the attitude verb and as binding a variable within the scope of the attitude verb. This essay is interested in addressing the question what the semantic analysis of this kind of reading should look like from a Fregean (...) perspective—a perspective according to which attitude states are generally relations to structured Fregean thoughts composed of senses. The Fregean view faces a challenge of compositionality here. This essay describes the challenge and offers a response on the Fregean's behalf. (shrink)

We introduce generalized quantifiers, as defined in Tarskian semantics by Mostowski and Lindström, in logics whose semantics is based on teams instead of assignments, e.g., IF-logic and Dependence logic. Both the monotone and the non-monotone case is considered. It is argued that to handle quantifier scope dependencies of generalized quantifiers in a satisfying way the dependence atom in Dependence logic is not well suited and that the multivalued dependence atom is a better choice. This atom is in fact definably equivalent (...) to the independence atom recently introduced by Väänänen and Grädel. (shrink)

REFERENCES Barwise, J. & R. Cooper (1981) — 'Generalized Quantifiers and Natural Language', Linguistics and Philosophy 4:2159-219. Van Benthem, J. (1983a) — ' Five Easy Pieces', in Ter Meulen (ed.), 1-17. Van Benthem, J. (1983b) ...

This talk is based on Krifka (2001). Its topic is the interpretation of quantifiers in questions. I will use English data for illustration, but the phenomena to be discussed appear to be general enough to be relevant for other languages as well, at least those languages that have nominal quantifiers.

In this paper I shall present some of the results I have obtained on modal theories which contain quantifiers for propositions. The paper is in two parts: in the first part I consider theories whose non-quantificational part is S5; in the second part I consider theories whose non-quantificational part is weaker than or not contained in S5. Unless otherwise stated, each theory has the same language L. This consists of a countable set V of propositional variables pl, pa, ... , (...) the operators v (or), ~ (not) and □ (necessarily), the universal quantifier (p), p a propositional variable, and brackets ( and ). The formulas of L are then defined in the usual way. (shrink)

Section 1 provides a brief summary of the pair-list literature singling out some points that are particularly relevant for the coming discussion. -/- Section 2 shows that the dilemma of quantifi cation versus domain restriction arises only in extensional complement interrogatives. In matrix questions and in intensional complements only universals support pairlist readings, whence the simplest domain restriction treatment suffices. Related data including conjunction, disjunction, and cumulative readings are discussed -/- Section 3 argues that in the case of extensional complements (...) the domain restriction treatment is inadequate for at least two independent reasons. One has to do with the fact that not only upward monotonic quantifi ers support pairlist readings, and the other with the derivation of apparent scope out readings. The reasoning is supplemented with some discussion of the semantic properties of layered quantifi ers.  The above will establish the need for quantifi cation, so the question arises how the objections explicitly enlisted in the literature against quantifi cation can be answered. Section 4 considers the de dicto reading of the quantifi er s restriction, quanti cational variability, and the absence of pairlist readings with whether questions, and argues that they need not militate against the quanti ficational analysis. -/- Section 5 summarizes the emergent proposal -/- Finally, section 6 discusses the signifi cance of the above findings for the behavior of weak islands. (shrink)

We compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and pushdown automata is psychologically relevant. Our research improves upon hypothesis and explanatory power of recent neuroimaging studies as well as provides evidence for the claim that human linguistic abilities are constrained by computational complexity.

This paper is a reaction to G. Küng's and J. T. Canty's Substitutional Quantification and Leniewskian quantifiers'Theoria 36 (1970), 165–182. I reject their arguments that quantifiers in Ontology cannot be referentially interpreted but I grant that there is what can be called objectual — referential interpretation of quantifiers and that because of the unrestricted quantification in Ontology the quantifiers in Ontology should not be given a so-called objectual-referential interpretation. I explain why I am in agreement with Küng and Canty's recommendation (...) that Ontology's quantifiers not be substitutionally interpreted even if Leniewski intended them to be so interpreted. A notion of an interpretation which is referential but yet which does not interpret as an assertor of existence of objects in a domain is developed. It is then shown that a first order version of Ontology is satisfied by those special kind of referential interpretations which read as Something as epposed to Something existing. (shrink)

Philosophia (Israel), 16(3-4), 333 - 344. YEAR: 1986 Extensive corrigenda Vol. 17, no. 3. -/- SUBJECT(S): Quine's second thoughts on quantifying in, appearing in the second, revised edition of _From a Logical Point of View_ of 1961, are shown to be incorrect. His original thoughts were correct. ABSTRACT: Additional tumult is supplied to pp. 152-154 of _From A Logical Point of View_, showing that being dated is no guarantee of being right. Among other things, it is shown that Quine's (...) argument to the conclusion that limiting the universe of discourse to intensional entities does not "relieve the original difficulty over quantifying into modal contexts" is incorrect; that the contradictory of that conclusion is in fact true; and that an even stronger conclusion is true, with 'abstract' replacing 'intensional'. (shrink)

This paper has two parts. In part I, I review two older accounts of the logical forms of modifiers, and suggest that they may be combined with each other so as to yield a theory that is better than either of its parts taken singly. Part of this theory involves the idea that certain sentences refer to events, states, or processes; Part II of this paper shows how to use this idea to account for tenses and temporal adverbials, and offers (...) a new account of ordinary language quantification. (shrink)

The sentence Irving was closer to me than he was to most of the others contains a quantifier, most of the other, in the scope a comparative. The first part of this paper explains the challenges presented by such cases to existing approaches to the semantics of the comparative. The second part presents a new analysis of comparatives based on intervals rather than points on a scale. This innovation is analogized to the move from moments to intervals in tense semantics. (...) The remainder of the paper is concerned with an interval-based semantics of degree in relation to issues other than the comparative proper. The paper begins with a discussion of the role negative polarity has played in studies on the semantics of comparatives. (shrink)

The first aim of the paper is to show that under certain conditions generative syntax can be made suitable for Montague semantics, based on his type logic. One of the conditions is to make branching in the so-called X-bar syntax strictly binary, This makes it possible to provide an adequate semantics for Noun Phrases by taking them as referring to sets of collections of sets of entities ( type <ett,t>) rather than to sets of sets of entities (ett).

The cofinality quantifiers were introduced by Shelah as an example of a compact logic stronger than first-order logic. We show that the classes of models axiomatized by these quantifiers can be turned into an Abstract Elementary Class by restricting to positive and deliberate uses. Rather than using an ad hoc proof, we give a general framework of abstract Skolemizations. This method gives a uniform proof that a wide rang of classes are Abstract Elementary Classes.

This article concerns the treatment of propositional quantification in a framework of labelled natural deduction for modal logic developed by Basin, Matthews and Viganò. We provide a detailed analysis of a basic calculus that can be used for a proof-theoretic rendering of minimal normal multimodal systems with quantification over stable domains of propositions. Furthermore, we consider variations of the basic calculus obtained via relational theories and domain theories allowing for quantification over possibly unstable domains of propositions. The main result of (...) the article is that fragments of the labelled calculi not exploiting reductio ad absurdum enjoy the Church–Rosser property and the strong normalization property; such result is obtained by combining Girard’s method of reducibility candidates and labelled languages of lambda calculus codifying the structure of modal proofs. (shrink)

In this paper we present a logical system able to compute the semantics of both declarative and interrogative sentences. Our proposed analysis takes place at both the sentential and at the discourse level. We use syntactic inference on the sentential level for declarative sentences, while the discourse level comes into play for our treatment of questions. Our formalization uses a type logic sensitive to both the syntactic and semantic properties of natural language. We will show how an account of the (...) linguistic data follows naturally from the logical relations inherent in the type logic. (shrink)

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)

Analysis of quantifiers in Wittgenstein's Tractatus. A critical survey In the Tractatus Logico-Philosophicus, Wittgenstein distinguishes between what can and cannot be said in any language by the general form of propositions. I explain Wittgenstein's method and discuss Robert J. Fogelin's criticism of what he takes to be the incompleteness of Wittgenstein's general form of propositions in his exposition of the 'Naive Constructivism of the Tractatus.' I argue that Fogelin's objection is mistaken, and that, contrary to Fogelin's claim, Wittgenstein's method when (...) properly applied produces all of the well-formed formulas with mixed multiple quantification that Fogelin maintains it cannot provide. I conclude by offering a critical comparison of similar solutions proposed, among others, by P.T. Geach, Scott Soames, and Matthias Varga von Kibéd. (shrink)

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].We introduce an operation existsn on properties S that says "there are n components having S". We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if (...) the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.We introduce another operation alt on properties which has the same relationship with the Circuit Value Problem as reach has with the Directed Reachability Problem. We use alt to show that Πn⊈ FO, Σn⊈ FO, and Δn+1⊈ FOB, solving some open problems raised in [Mat98]. (shrink)

We investigate uniform interpolants in propositional modal logics from the proof-theoretical point of view. Our approach is adopted from Pitts’ proof of uniform interpolationin intuitionistic propositional logic [15]. The method is based on a simulation of certain quantifiers ranging over propositional variables and uses a terminating sequent calculus for which structural rules are admissible.

We generalize Shelah's analysis of cardinality quantifiers for a superstable theory from Chapter V of Classification Theory and the Number of Nonisomorphic Models. We start with a set of bounds for the cardinality of each formula in some general invariant family of formulas in a superstable theory (in Classification Theory, a uniform family of formulas is considered) and find a set of derived bounds for all formulas. The set of derived bounds is sharp: up to a technical restriction, every model (...) that satisfies the original bounds has a sufficiently saturated elementary extension that satisfies the original bounds and such that for each formula the set of its realizations in the extension has arbitrarily large cardinality below the corresponding derived bound of the formula. (shrink)

In this paper an alternative Skolemization method is introduced that, for a large class of formulas, is sound and complete with respect to intuitionistic logic. This class extends the class of formulas for which standard Skolemization is sound and complete and includes all formulas in which all strong quantifiers are existential. The method makes use of an existence predicate first introduced by Dana Scott.

We provide tools for a concise axiomatization of a broad class of quantifiers in many-valued logic, so-called distribution quantifiers. Although sound and complete axiomatizations for such quantifiers exist, their size renders them virtually useless for practical purposes. We show that for quantifiers based on finite distributive lattices compact axiomatizations can be obtained schematically. This is achieved by providing a link between skolemized signed formulas and filters/ideals in Boolean set lattices. Then lattice theoretic tools such as Birkhoff's representation theorem for finite (...) distributive lattices are used to derive tableau-style axiomatizations of distribution quantifiers. (shrink)