We consider an example of a sentence which according to Hintikka's claim essentially requires for its logical form a Henkin quantifier. We show that if Hintikka is right then recognizing the truth value of the sentence in finite models is an NP-complete problem. We discuss also possible conclusions from this observation.

A study of the contribution semantics makes to the syntactic patterns of English: an intepretive theory of grammar.

Branching quantifiers were first introduced by L. Henkin in his 1959 paper ‘Some Remarks on Infmitely Long Formulas’. By ‘branching quantifiers’ Henkin meant a new, non-linearly structured quantiiier-prefix whose discovery was triggered by the problem of interpreting infinitistic formulas of a certain form} The branching (or partially-ordered) quantifier-prefix is, however, not essentially infinitistic, and the issues it raises have largely been discussed in the literature in the context of finitistic logic, as they will be here. Our discussion transcends, however, the (...) resources of standard lst-order languages and we will consider the new form in the context of 1st-order logic with 1- and 2-place ‘Mostowskian` generalized quantifiers.2.. (shrink)

Several authors proposed to devise logical structures for Natural Language (NL) semantics in which noun phrases yield referential terms rather than standard Generalized Quantifiers. In this view, two main problems arise: the need to refer to the maximal sets of entities involved in the predications and the need to cope with Independent Set (IS) readings, where two or more sets of entities are introduced in parallel. The article illustrates these problems and their consequences, then presents an extension of the proposal (...) made in Sher (J Philos Logic 26:1–43, 1997 ) in order to properly represent the meaning of IS readings involving NL quantifiers. The solution proposed here allows to uniformly deal with both standard linear and IS readings, regardless of their actual existence in NL or quantifiers’ monotonicity. Sentences featuring nested quantifications are particularly problematic. By avoiding parallel nested quantification in the formulae, the proper true values are achieved. (shrink)

In the opening sections of this paper, we defined ambiguity in terms of distinct sentences (for a single sentence-string) with, in particular, distinct sets of truth conditions for the corresponding negative sentence-string. Lexical vagueness was defined as equivalent to disjunction, for under conditions of the negation of a sentence-string containing such an expression, all the relevant more specific interpretations of the string had also to be negated. Yet in the case of mixed quantification sentences, the strengthened, more specific, interpretations of (...) some such positive string are not all of them necessarily implied to be false if the corresponding negative sentence-string is asserted. On the contrary, as we saw in section 6, a negative sentence-string can be used to deny one of the more specific interpretations of the corresponding positive string without also denying other weaker interpretations of that same string. One might therefore argue that the only empirical evidence availble for assessing quantified sentences suggests clearly that these sentence-strings are ambiguous. Indeed logicians, many of whom restrict their attention to propositions, MUST recognise logical ambiguity at this point. For the contextualisation of the negative sentences in section 6 showed that it was possible to assert the falsity of some proposition P expressed by the sentence S while asserting a further proposition which was compatible with the truth of S. However the corresponding conclusion that such sentence-strings are sententially ambiguous is not a necessary conclusion for the linguist: for the alternative account of postulating a single semantic representation plus a set of semantic procedures is also compatible with the negation evidence. Moreover we have seen independent reasons for thinking that if sentential ambiguity is assumed to be in one-to-one correspondence with what we should now call logical ambiguity, a considerable body of generalisations is lost. For the maximal ambiguity account, it should be recalled, is committed to assigning at least thirteen distinct propositions and hence thirteen distinct sentence outputs for every sentence-string containing no more than two quantifiers, for three out of the four interpretations originally outlined in this paper can be understood with each numeral taken either in an ’exactly’ sense or in an ’at least’ sense. Moreover there is no explanation of why just these interpretations are available-they are merely an arbitrary list, no more connected than are the two interpretations of John saw her duck, with no reason to predict that the ambiguity would carry over from language to language. If then it is granted that an ambiguity account fails to capture appropriate generalisations, only two alternative accounts of mixed quantification sentence-strings remain viable-an analysis proposing an initial co-ordinate logical form like the logical form III, which is the strongest form compatible with each of the propositional interpretations of sentence-string Two examiners marked six scripts, and the radically weak form in which only existential quantification (both over sets and over members of those sets) is invoked. Since there are strong arguments to suggest that the procedures which both analyses require are semantic, there seems no reason not to adopt the radical vagueness account, with its considerably greater simplicity. (shrink)

This book is a relatively self-contained introduction to the subject, which includes the necessary background material, as well as numerous examples and exercises.

In the study of cognitive processes, limitations on computational resources (computing time and memory space) are usually considered to be beyond the scope of a theory of competence, and to be exclusively relevant to the study of performance. Starting from considerations derived from the theory of computational complexity, in this paper I argue that there are good reasons for claiming that some aspects of resource limitations pertain to the domain of a theory of competence.

Chapter. 1. Logical. Form. as. a. Level. of. Linguistic. Representation. What is the relation of a sentence's syntactic form to its logical form? This issue has been of central concern in modern inquiry into the semantic properties of natural ...

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)

We show in rather informal terms how witness sets can be useful in both explicating some basic intuitions about scope and understanding how particular denotational semantic differences between noun phrases affect their abilities to bear out certain scopal patterns. More generally we suggest that the usual notion of scope needs to be factored into variation distributivity and maximality. This part lays some groundwork for several of the subsequent chapters and is thus of interest to all readers. The second part shows (...) that already in this initial raw form the above insights can be applied to make a novel claim concerning the availability of so-called branching readings. In logical terms a branching reading can be defined for any sentence with a subject and a direct object. However speakers of English accept only a fraction of these readings, so the question arises how the data can be predicted from the meanings of the participating quantifiers and the syntactic structure of the sentence. We propose that thinking about the behavior of quantifiers along the lines introduced in the first part leads to a simple answer to this question. (shrink)

We discuss Hintikka’s Thesis [Hintikka 1973] that there exist natural language sentences which require non–linear quantification to express their logical form.