In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred interpretation, provides (...) evidence for these predictions. Experiment 2 was a picture verification task. The results show that the strong interpretation was in fact possible for tractable all but one-reciprocals, but not for exactly n. The last experiment manipulated monotonicity of the quantifier antecedents. (shrink)

In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred interpretation, provides (...) evidence for these predictions. Experiment 2 was a picture verification task. The results show that the strong interpretation was in fact possible for tractable all but one-reciprocals, but not for exactly n. The last experiment manipulated monotonicity of the quantifier antecedents. (shrink)

Moral considerations and our normative expectations influence not only our judgments about intentional action or causation but also our judgments about exact probabilities and quantities. Whereas those cases support the competence theory proposed by Knobe in his paper, they remain compatible with a modular conception of the interaction between moral and nonmoral cognitive faculties in each of those domains.

It is widely believed that existential quantifiers can bring about the semantic effects of a scope which is wider than their actual syntactic scope (See Fodor & Sag (1982), Cresti (1995), Kratzer (1995), Reinhart (1995) and Winter (1995), among many others.) On the other hand, it is assumed that the syntactic scope of universal quantifiers can be determined unequivocally by the semantics. This paper shows that this second assumption is wrong; universal quantifiers can also bring about scope illusions, though in (...) a very specific environment. In particular, we argue that in the environment of generic tense, universal quantifiers can show the semantic effects of a scope which is wider than the one that is actually realized at LF. Our argument has four steps. First, we show that in generic contexts, universal quantifiers escape standard “scope-islands” (Section 1). Second, we show how the effects of wide scope in generic contexts can be achieved without syntactic wide scope (Section 2.1). Third, we show that this result is actually forced on us, once we take seriously certain independent issues concerning the interpretation of generic tense (Sections 2.2 - 2.4). Finally, the semantics of generic tense and, in particular, its interaction with focus, will yield some intricate new predictions, which, as we show, are borne out (Sections 3 - 5). (shrink)

We discuss the thesis formulated by Hintikka (1973) that certain natural language sentences require non-linear quantification to express their meaning. We investigate sentences with combinations of quantifiers similar to Hintikka's examples and propose a novel alternative reading expressible by linear formulae. This interpretation is based on linguistic and logical observations. We report on our experiments showing that people tend to interpret sentences similar to Hintikka sentence in a way consistent with our interpretation.

A formal, computational, semantically clean representation of natural language is presented. This representation captures the fact that logical inferences in natural language crucially depend on the semantic relation of entailment between sentential constituents such as determiner, noun, adjective, adverb, preposition, and verb phrases.The representation parallels natural language in that it accounts for human intuition about entailment of sentences, it preserves its structure, it reflects the semantics of different syntactic categories, it simulates conjunction, disjunction, and negation in natural language by computable (...) operations with provable mathematical properties, and it allows one to represent coordination on different syntactic levels. (shrink)

When we assess an action as right or wrong we often want to know whether it was forced upon the agent, whether it had certain causal effects, and whether its consequences were known. It seems natural to think that these questions are prior to and independent of all normative evaluation of the action. Recent experimental results have shown that in fact this is not so: when people consider such questions their answers often depend on whether the action has violated a (...) salient norm. (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)

What is the relation between models, as used in model-theoretic semantics, and the “world” which models represent? More specifically, let us consider the question of whether a single individual, event, time or other element in a model might be used to represent more than one individual, event, time or other object in the real world.

This paper gives a novel analysis of identificational sentences such as 'this is Mary','this is a beautiful woman' or 'this looks like Mary' based on the notion of a trope.

We consider the notion of everyday language. We claim that everyday language is semantically bounded by the properties expressible in the existential fragment of second–order logic. Two arguments for this thesis are formulated. Firstly, we show that so–called Barwise's test of negation normality works properly only when assuming our main thesis. Secondly, we discuss the argument from practical computability for finite universes. Everyday language sentences are directly or indirectly verifiable. We show that in both cases they are bounded by second–order (...) existential properties. Moreover, there are known examples of everyday language sentences which are the most difficult in this class (NPTIME–complete). (shrink)

It is widely agreed that sentences containing a non-denoting description embedded in the scope of a propositional attitude verb have true de dicto interpretations, and Russell’s (1905) analysis of definite descriptions is often praised for its simple analysis of such cases, cf. e.g. Neale (1990). However, several people, incl. Elbourne (2005, 2009), Heim (1991), and Kripke (2005), have contested this by arguing that Russell’s analysis yields incorrect predictions in non-doxastic attitude contexts. Heim and Elbourne have subsequently argued that once certain (...) facts about presupposition projection are fully appreciated, the Frege/Strawson analysis of definite descriptions has an explanatory advantage. In this paper, I argue that both Russell’s analysis and the Frege/Strawson analysis face a serious problem when it comes to the interaction of attitude verbs and definite descriptions. I argue that the problem observed by Elbourne, Heim, and Kripke is much more general than standardly assumed and that a solution requires a revision of the semantics of definite and indefinite descriptions. I outline the conditions that are required to solve the problem and present an analysis couched in dynamic semantics which can provide a solution. I conclude by discussing some further issues related to propositional attitude verbs that complicate a fully general solution to the problem. (shrink)

Syntactic and semantic theories of quantificational phenomena traditionally treat all noun phrases alike, thus predicting that noun phrases exhibit a uniform behavior. It is well-known that this is an idealization: in any given case, some noun phrases will support a desired reading more readily than others. Anyone who has lectured on quantifier scope ambiguities to a class of unbrainwashed undergraduates will recall the amount of preparation time that goes into coming up with two or three examples that the class will (...) judge to be ambiguous in exactly the ways the theory under discussion predicts. The same experience with ``good citizens'' and ``bad citizens'' repeats itself in connection with branching, anaphora, distributive versus collective readings, extraction, event quantification, pair-list questions, and so on. (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)

The paper presents a study examining the role of working
memory in quantifier verification. We created situations similar to the
span task to compare numerical quantifiers of low and high rank, parity
quantifiers and proportional quantifiers. The results enrich and support
the data obtained previously in and predictions drawn from a computational
model.

We prove that PTIME generalized quantifiers are closed under Boolean operations, iteration, cumulation and resumption. -/- .

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 study the computational complexity of reciprocal sentences with quantified antecedents. We observe a computational dichotomy between different interpretations of reciprocity, and shed some light on the status of the so-called Strong Meaning Hypothesis.

We discuss McMillan et al. (2005) paper devoted to study brain activity during comprehension of sentences with generalized quantifiers. According to the authors their results verify a particular computational model of natural language quantifier comprehension posited by several linguists and logicians (e. g. see van Benthem, 1986). We challenge this statement by invoking the computational difference between first-order quantifiers and divisibility quantifiers (e. g. see Mostowski, 1998). Moreover, we suggest other studies on quantifier comprehension, which can throw more light on (...) the role of working memory in processing quantifiers. (shrink)

The paper presents an experimental evidence on differences in the sentence-picture verification under additional memory load between parity and proportional quantifiers. We asked subjects to memorize strings of 4 or 6 digits, then to decide whether a quantifier sentence is true at a given picture, and finally to recall the initially given string of numbers. The results show that: (a) proportional quantifiers are more difficult than parity quantifiers with respect to reaction time and accuracy; (b) maintaining either 4 or 6 (...) elements in the working memory has the same effect on the processing of parity quantifiers; (c) however, in the case of proportional quantifiers subjects performed better in the verification tasks under the 6-digit load condition, and (d) even though the strings of 4 numbers were better recalled by subjects after judging parity there is no difference between quantifiers in the case of the 6-element condition. We briefly outline two alternative explanations for the observed phenomena rooted in the computational model of quantifier verification and the different theories of working memory. (shrink)

Szymanik (2007) suggested that the distinction between first-order and higher-order quantifiers does not coincide with the computational resources required to compute the meaning of quantifiers. Cognitive difficulty of quantifier processing might be better assessed on the basis of complexity of the minimal corresponding automata. For example, both logical and numerical quantifiers are first-order. However, computational devices recognizing logical quantifiers have a fixed number of states while the number of states in automata corresponding to numerical quantifiers grows with the rank of (...) the quantifier. This observation partially explains the differences in processing between those two types of quantifiers (Troiani et al. 2009) and links them to the computational model. Taking this perspective, below, we suggest the experimental setting extending the one by McMillan et al. (2005) and Troiani et al. (2009). (shrink)

We compared the processing of natural language quantifiers in a group of patients with schizophrenia and a healthy control group. In both groups, the difficulty of the quantifiers was consistent with computational predictions, and patients with schizophrenia took more time to solve the problems. However, they were significantly less accurate only with proportional quantifiers, like more than half. This can be explained by noting that, according to the complexity perspective, only proportional quantifiers require working memory engagement.