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)

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.

'Working Memory, Thought, and Action' is the magnum opus of one of the most influential cognitive psychologists of the past 50 years. This new volume on the model he created discusses the developments that have occurred within the model in the past twenty years, and places it within a broader context.

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)

In Minimal Rationality, Christopher Cherniak boldly challenges the myth of Man the the Rational Animal and the central role that the "perfectly rational...

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 paper gives a survey of known results related to computational devices (finite and push–down automata) recognizing monadic generalized quantifiers in finite models. Some of these results are simple reinterpretations of descriptive—feasible correspondence theorems from finite–model theory. Additionally a new result characterizing monadic quantifiers recognized by push down automata is proven.

We consider connections between number sense—the ability to judge number—and the interpretation of natural language quantifiers. In particular, we present empirical evidence concerning the neuroanatomical underpinnings of number sense and quantifier interpretation. We show, further, that impairment of number sense in patients can result in the impairment of the ability to interpret sentences containing quantifiers. This result demonstrates that number sense supports some aspects of the language faculty.

ABSTRACT This paper gives a survey of known results related to computational devices recognising monadic generalised quantifiers infinite models. Some of these results are simple reinterpretations of descriptive-feasible correspondence theorems from finite-model theory. Additionally a new result characterizing monadic quantifiers recognized by push down automata is proven.

The general problem of visual search can be shown to be computationally intractable in a formal, complexity-theoretic sense, yet visual search is extensively involved in everyday perception, and biological systems manage to perform it remarkably well. Complexity level analysis may resolve this contradiction. Visual search can be reshaped into tractability through approximations and by optimizing the resources devoted to visual processing. Architectural constraints can be derived using the minimum cost principle to rule out a large class of potential solutions. The (...) evidence speaks strongly against bottom-up approaches to vision. In particular, the constraints suggest an attentional mechanism that exploits knowledge of the specific problem being solved. This analysis of visual search performance in terms of attentional influences on visual information processing and complexity satisfaction allows a large body of neurophysiological and psychological evidence to be tied together. (shrink)

This paper examines the role that linguistic and cognitive prominence play in the resolution of anaphor–antecedent relationships. In two experiments, we found that pronouns are immediately sensitive to the cognitive prominence of potential antecedents when other antecedent selection cues are uninformative. In experiment 1, results suggest that despite their theoretical dissimilarities, topic and contrastive focus both serve to enhance cognitive prominence. Results from experiment 2 suggest that the contrastive prosody appropriate for focus constructions may also play an important role in (...) enhancing cognitive prominence. Thus different types of linguistic prominence (topic, contrastive focus) appear to have the common effect of increasing the cognitive prominence of the discourse referent. For pronouns with two possible antecedents, the cognitive prominence of an antecedent aids in anaphor resolution, immediately biasing selection towards the more prominent (and ultimately preferred) antecedent. (shrink)

The general problem of visual search can be shown to be computationally intractable in a formal, complexity-theoretic sense, yet visual search is extensively involved in everyday perception, and biological systems manage to perform it remarkably well. Complexity level analysis may resolve this contradiction. Visual search can be reshaped into tractability through approximations and by optimizing the resources devoted to visual processing. Architectural constraints can be derived using the minimum cost principle to rule out a large class of potential solutions. The (...) evidence speaks strongly against bottom-up approaches to vision. In particular, the constraints suggest an attentional mechanism that exploits knowledge of the specific problem being solved. This analysis of visual search performance in terms of attentional influences on visual information processing and complexity satisfaction allows a large body of neurophysiological and psychological evidence to be tied together. (shrink)

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.

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 present study examined the neural substrate of two classes of quantifiers: numerical quantifiers like ” at least three” which require magnitude processing, and logical quantifiers like ” some” which can be understood using a simple form of perceptual logic. We assessed these distinct classes of quantifiers with converging observations from two sources: functional imaging data from healthy adults, and behavioral and structural data from patients with corticobasal degeneration who have acalculia. Our findings are consistent with the claim that numerical (...) quantifier comprehension depends on a lateral parietal-dorsolateral prefrontal network, but logical quantifier comprehension depends instead on a rostral medial prefrontal-posterior cingulate network. These observations emphasize the important contribution of abstract number knowledge to the meaning of numerical quantifiers in semantic memory and the potential role of a logic-based evaluation in the service of non-numerical quantifiers. (shrink)