The meaning of 'most' can be described in many ways. We offer a framework for distinguishing semantic descriptions, interpreted as psychological hypotheses that go beyond claims about sentential truth conditions, and an experiment that tells against an attractive idea: 'most' is understood in terms of one-to-one correspondence. Adults evaluated 'Most of the dots are yellow', as true or false, on many trials in which yellow dots and blue dots were displayed for 200 ms. Displays manipulated the ease of using a (...) 'one-to-one with remainder' strategy, and a strategy of using the Approximate Number System to compare of (approximations of) cardinalities. Interpreting such data requires care in thinking about how meaning is related to verification. But the results suggest that 'most' is understood in terms of cardinality comparison, even when counting is impossible. (shrink)

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)

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.

This paper proposes an Interface Transparency Thesis concerning how linguistic meanings are related to the cognitive systems that are used to evaluate sentences for truth/falsity: a declarative sentence S is semantically associated with a canonical procedure for determining whether S is true; while this procedure need not be used as a verification strategy, competent speakers are biased towards strategies that directly reflect canonical specifications of truth conditions. Evidence in favor of this hypothesis comes from a psycholinguistic experiment examining adult judgments (...) concerning ‘Most of the dots are blue’. This sentence is true if and only if the number of blue dots exceeds the number of nonblue dots. But this leaves unsettled, e.g., how the second cardinality is specified for purposes of understanding and/or verification: via the nonblue things, given a restriction to the dots, as in ‘|{x: Dot(x) & ~Blue(x)}|’; via the blue things, given the same restriction, and subtraction from the number of dots, as in ‘|{x: Dot(x)}| – |{x: Dot(x) & Blue(x)}|’; or in some other way. Psycholinguistic evidence and psychophysical modeling support the second hypothesis. (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)

By a fragment of a natural language, we understand a collection of sentences forming a naturally delineated subset of that language and equipped with a semantics commanding the general assent of its native speakers. By the semantic complexity of such a fragment, we understand the computational complexity of deciding whether any given set of sentences in that fragment represents a logically possible situation. In earlier papers by the first author, the semantic complexity of various fragments of English involving at most (...) transitive verbs was investigated. The present paper considers various fragments of English involving ditransitive verbs and determines their semantic complexity. (shrink)

The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= finite (...) satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic. (shrink)

In this paper we present a semantic analysis of the imperfective paradox based on the Event Calculus, a planning formalism characterizing a class of models which can be computed by connectionist networks. We report the results of a questionnaire that support the semantic theory and suggest that different aspectual classes of VPs in the progressive give rise to different entailment patterns. Further, a processing model is outlined, combining the semantic analysis with the psycholinguistic principle of immediacy in the framework of (...) recurrent networks. The model is used to derive predictions concerning the electrophysiological correlates of the computations described by the Event Calculus. (shrink)

Next SectionWe 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.

We discuss the thesis formulated by Hintikka 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.

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.

The recognition that human minds/brains are finite systems with limited resources for computation has led some researchers to advance the Tractable Cognition thesis: Human cognitive capacities are constrained by computational tractability. This thesis, if true, serves cognitive psychology by constraining the space of computational‐level theories of cognition. To utilize this constraint, a precise and workable definition of “computational tractability” is needed. Following computer science tradition, many cognitive scientists and psychologists define computational tractability as polynomial‐time computability, leading to the P‐Cognition thesis. (...) This article explains how and why the P‐Cognition thesis may be overly restrictive, risking the exclusion of veridical computational‐level theories from scientific investigation. An argument is made to replace the P‐Cognition thesis by the FPT‐Cognition thesis as an alternative formalization of the Tractable Cognition thesis (here, FPT stands for fixed‐parameter tractable). Possible objections to the Tractable Cognition thesis, and its proposed formalization, are discussed, and existing misconceptions are clarified. (shrink)

This paper proposes that elementary reciprocal sentences have four semantic readings: a strongly reciprocal interpretation, a weakly reciprocal interpretation, a situation-based weakly reciprocal reading, and a collective reading. Interpretational possibilities of reciprocal sentences that have been discussed in the literature are identified as one of these four. A compositional semantic analysis of all of these readings is provided in which the reciprocal expression is uniformly represented as 'the other ones among them' (recasting Heim, Lasnik and May 1991a, b). A reciprocal (...) sentence is thus a special kind of relational plural. Interpretational variability comes about by the same mechanisms of plural predication at work in relational plurals: pluralization operators, LF operations like QR, and addition of contextual information. (shrink)

In this paper we present a semantic analysis of the imperfective paradox based on the Event Calculus, a planning formalism characterizing a class of models which can be computed by connectionist networks. We report the results of a questionnaire that support the semantic theory and suggest that different aspectual classes of VPs in the progressive give rise to different entailment patterns. Further, a processing model is outlined, combining the semantic analysis with the psycholinguistic principle of immediacy in the framework of (...) recurrent networks. The model is used to derive predictions concerning the electrophysiological correlates of the computations described by the Event Calculus. (shrink)

Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain "built-in" relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence.

Recent developments in the semantics of natural language seem to lead to a genuine synthesis of ideas from linguistics and logic, producing novel concepts and questions of interest to both parent disciplines. This book is a collection of essays on such new topics, which have arisen over the past few years. Taking a broad view, developments in formal semantics over the past decade can be seen as follows. At the beginning stands Montague's pioneering work, showing how a rigorous semantics can (...) be given for complete fragments of natural language by creating a suitable fit between syntactic categories and semantic types. This very enterprise already dispelled entrenched prejudices concerning the separation of linguistics and logic. Having seen the light, however, there is no reason at all to stick to the letter of Montague's proposals, which are often debatable. Subsequently, then, many improvements have been made upon virtually every aspect of the enterprise. More sophisticated grammars have been inserted (lately, lexical-functional grammar and generalized phrase structure grammar), more sensitive model structures have been developed (lately, 'partial' rather than 'total' in their com position), and even the mechanism of interpretation itself may be fine-tuned more delicately, using various forms of 'representations' mediating between linguistic items and semantic reality. In addition to all these refinements of the semantic format, descriptive coverage has extended considerably. (shrink)

The verification of a sentence against a visual display in experimental conditions reveals a procedure that is driven solely by the properties of the linguistic input and not by the properties of the context (the set-up of the visual display) or extra-linguistic cognition (operations executed to obtain the truth value). This procedure, according to the Interface Transparency Thesis (ITT) (Lidz et al. in Nat Lang Semant 19(3):227–256, 2011), represents the meaning of an expression at the interface with the ‘conceptual-intentional’ system (...) (Chomsky in The minimalist program. MIT Press, Cambridge, 1995). My experiments provide support for the ITT by replicating in Polish and in Bulgarian the findings of Lidz et al. (Nat Lang Semant 19(3):227–256, 2011) for the English quantifier most. We also obtain new evidence that participants are prompted to switch between verification procedures by a change in the linguistic input (a different superlative quantifier entailed by most), but not by a change in the visual input. Thus, the motivation for the subconscious switch in procedures is not to maximize efficiency. Participants use the procedure associated with each quantifier, and in effect, the same display is verified differently depending on which information the visual system is instructed to use by the semantic representation of the sentence. (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)

We examine the verification of simple quantifiers in natural language from a computational model perspective. We refer to previous neuropsychological investigations of the same problem and suggest extending their experimental setting. Moreover, we give some direct empirical evidence linking computational complexity predictions with cognitive reality.<br>In the empirical study we compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and push-down automata is psychologically relevant. Our research improves upon hypothesis and (...) explanatory power of recent neuroimaging studies as well as provides<br>evidence. (shrink)

This paper investigates different readings of plural and reciprocal sentences and how they can be derived from syntactic surface structures in a systematic way. The main thesis is that these readings result from different ways of inserting logical operators at the level of Logical Form. The basic operator considered here is a cumulative mapping from predicates that apply to singularities onto the corresponding predicates that apply to pluralities. Given a theory which allows for free insertion of such operators, it can (...) then be shown that the lexical semantics of the reciprocal expressions each other/one another consists of exactly two components, namely an anaphoric variable and a non-identity statement. This receives further support from the observation that it is exactly these two components that can be focused by only; all that remains to be done is to correctly manipulate these components at the level of LF. (shrink)

The semantic automata framework, developed originally in the 1980s, provides computational interpretations of generalized quantifiers. While recent experimental results have associated structural features of these automata with neuroanatomical demands in processing sentences with quantifiers, the theoretical framework has remained largely unexplored. In this paper, after presenting some classic results on semantic automata in a modern style, we present the first application of semantic automata to polyadic quantification, exhibiting automata for iterated quantifiers. We also discuss the role of semantic automata in (...) linguistic theory and offer new empirical predictions for sentence processing with embedded quantifiers. (shrink)

The semantic automata framework, developed originally in the 1980s, provides computational interpretations of generalized quantifiers. While recent experimental results have associated structural features of these automata with neuroanatomical demands in processing sentences with quantifiers, the theoretical framework has remained largely unexplored. In this paper, after presenting some classic results on semantic automata in a modern style, we present the first application of semantic automata to polyadic quantification, exhibiting automata for iterated quantifiers. We also discuss the role of semantic automata in (...) linguistic theory and offer new empirical predictions for sentence processing with embedded quantifiers. (shrink)

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.

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.

The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to the problem of computational (...) complexity of the Ramsey quantifier for which the phrase “A is big relatively to the universe” is interpreted as containing at least one representative of each equivalence class, for some given equvalence relation. In this work we consider quantifiers Rf, for which “A is big relatively to the universe” means “card(A) > f (n), where n is the size of the universe”. Following [Blass, Gurevich 1986] we call R mighty if Rx, yH(x, y) defines N P – complete class of finite models. Similarly we say that Rf is N P –hard if the corresponding class is N P –hard. We prove the following theorems. (shrink)

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)

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)

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)