In the late summer of 1998, the authors, a cognitive scientist and a logician, started talking about the relevance of modern mathematical logic to the study of human reasoning, and we have been talking ever since. This book is an interim report of that conversation. It argues that results such as those on the Wason selection task, purportedly showing the irrelevance of formal logic to actual human reasoning, have been widely misinterpreted, mainly because the picture of logic current in psychology (...) and cognitive science is completely mistaken. We aim to give the reader a more accurate picture of mathematical logic and, in doing so, hope to show that logic, properly conceived, is still a very helpful tool in cognitive science. The main thrust of the book is therefore constructive. We give a number of examples in which logical theorizing helps in understanding and modeling observed behavior in reasoning tasks, deviations of that behavior in a psychiatric disorder (autism), and even the roots of that behavior in the evolution of the brain. (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)

We use a new model of metarepresentational development to predict a cognitive deficit which could explain a crucial component of the social impairment in childhood autism. One of the manifestations of a basic metarepresentational capacity is a ‘ theory of mind ’. We have reason to believe that autistic children lack such a ‘ theory ’. If this were so, then they would be unable to impute beliefs to others and to predict their behaviour. This hypothesis was tested using Wimmer (...) and Perner’s puppet play paradigm. Normal children and those with Down’s syndrome were used as controls for a group of autistic children. Even though the mental age of the autistic children was higher than that of the controls, they alone failed to impute beliefs to others. Thus the dysfunction we have postulated and demonstrated is independent of mental retardation and specific to autism. (shrink)

This article takes off from Johan van Benthem’s ruminations on the interface between logic and cognitive science in his position paper “Logic and reasoning: Do the facts matter?”. When trying to answer Van Benthem’s question whether logic can be fruitfully combined with psychological experiments, this article focuses on a specific domain of reasoning, namely higher-order social cognition, including attributions such as “Bob knows that Alice knows that he wrote a novel under pseudonym”. For intelligent interaction, it is important that the (...) participants recursively model the mental states of other agents. Otherwise, an international negotiation may fail, even when it has potential for a win-win solution, and in a time-critical rescue mission, a software agent may depend on a teammate’s action that never materializes. First a survey is presented of past and current research on higher-order social cognition, from the various viewpoints of logic, artificial intelligence, and psychology. Do people actually reason about each other’s knowledge in the way proscribed by epistemic logic? And if not, how can logic and cognitive science productively work together to construct more realistic models of human reasoning about other minds? The paper ends with a delineation of possible avenues for future research, aiming to provide a better understanding of higher-order social reasoning. The methodology is based on a combination of experimental research, logic, computational cognitive models, and agent-based evolutionary models. Keywords Epistemic logic - Cognitive science - Intelligent interaction - Cognitive modeling. (shrink)

This revised edition includes a new Preface outlining developments in Relevance Theory since 1986, discussing the more serious criticisms of the theory, and ...

A fixed-parameter is an algorithm that provides an optimal solution to a combinatorial problem. This research-level text is an application-oriented introduction to the growing and highly topical area of the development and analysis of efficient fixed-parameter algorithms for hard problems. The book is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the (...) essential from parameterized hardness theory with a focus on W [1]-hardness, which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology. Aimed at graduate and research mathematicians, programmers, algorithm designers and computer scientists, the book introduces the basic techniques and results and provides a fresh view on this highly innovative field of algorithmic research. (shrink)

Many social situations require a mental model of the knowledge, beliefs, goals, and intentions of others: a Theory of Mind (ToM). If a person can reason about other people’s beliefs about his own beliefs or intentions, he is demonstrating second-order ToM reasoning. A standard task to test second-order ToM reasoning is the second-order false belief task. A different approach to investigating ToM reasoning is through its application in a strategic game. Another task that is believed to involve the application of (...) second-order ToM is the comprehension of sentences that the hearer can only understand by considering the speaker’s alternatives. In this study we tested 40 children between 8 and 10 years old and 27 adult controls on (adaptations of) the three tasks mentioned above: the false belief task, a strategic game, and a sentence comprehension task. The results show interesting differences between adults and children, between the three tasks, and between this study and previous research. (shrink)

In the beginning, there was the DN (Deductive Nomological) model of explanation, articulated by Hempel and Oppenheim (1948). According to DN, scientific explanation is subsumption under natural law. Individual events are explained by deducing them from laws together with initial conditions (or boundary conditions), and laws are explained by deriving them from other more fundamental laws, as, for example, the simple pendulum law is derived from Newton's laws of motion.

An individual has a theory of mind if he imputes mental states to himself and others. A system of inferences of this kind is properly viewed as a theory because such states are not directly observable, and the system can be used to make predictions about the behavior of others. As to the mental states the chimpanzee may infer, consider those inferred by our own species, for example, purpose or intention, as well as knowledge, belief, thinking, doubt, guessing, pretending, liking, (...) and so forth. To determine whether or not the chimpanzee infers states of this kind, we showed an adult chimpanzee a series of videotaped scenes of a human actor struggling with a variety of problems. Some problems were simple, involving inaccessible food as in the original Kohler problems; others were more complex, involving an actor unable to extricate himself from a locked cage, shivering because of a malfunctioning heater, or unable to play a phonograph because it was unplugged. With each videotape the chimpanzee was given several photographs, one a solution to the problem, such as a stick for the inaccessible bananas, a key for the locked up actor, a lit wick for the malfunctioning heater. The chimpanzee's consistent choice of the correct photographs can be understood by assuming that the animal recognized the videotape as representing a problem, understood the actor's purpose, and chose alternatives compatible with that purpose. (shrink)

The everyday capacity to understand the mind, or 'mindreading', plays an enormous role in our ordinary lives. Shaun Nichols and Stephen Stich provide a detailed and integrated account of the intricate web of mental components underlying this fascinating and multifarious skill. The imagination, they argue, is essential to understanding others, and there are special cognitive mechanisms for understanding oneself. The account that emerges has broad implications for longstanding philosophical debates over the status of folk psychology. Mindreading is another trailblazing volume (...) in the prestigious interdisciplinary Oxford Cognitive Science series. (shrink)

We analyse the computational complexity of comparing informational structures. Intuitively, we study the complexity of deciding queries such as the following: Is Alice’s epistemic information strictly coarser than Bob’s? Do Alice and Bob have the same knowledge about each other’s knowledge? Is it possible to manipulate Alice in a way that she will have the same beliefs as Bob? The results show that these problems lie on both sides of the border between tractability (P) and intractability (NP-hard). In particular, we (...) investigate the impact of assuming information structures to be partition-based (rather than arbitrary relational structures) on the complexity of various problems. We focus on the tractability of concrete epistemic tasks and not on epistemic logics describing them. (shrink)

My goal in this paper 1 is, first, to collect together a number of themes and observations that have usually been kept apart, locked up in their respective disciplines. When these are brought together, some general and far reaching implications become really rather clear. In particular, I want to make a case for the implicit coherence of these themes in the idea that.

Abstract ?Theory of Mind? (ToM) is widely held to be ubiquitous in our navigation of the social world. Recently this standard view has been contested by phenomenologists and enactivists. Proponents of the ubiquity of ToM, however, accept and effectively neutralize the intuitions behind their arguments by arguing that ToM is mostly sub-personal. This paper proposes a similar move on behalf of the phenomenologists and enactivists: it offers a novel explanation of the intuition that ToM is ubiquitous that is compatible with (...) the rejection of this ubiquity. According to this explanation, we use ToM-talk primarily to model and thereby reconstruct non-mentalizing social-cognitive processes in order to explain our assessment of the behaviour of others. The intuition that ToM is ubiquitous is the result of mistaking the model for the real thing. This explanation is argued to be more complete than the ?ToM-ist? explanation of the intuition that ToM is not ubiquitous. (shrink)

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

This volume on the semantic complexity of natural language explores the question why some sentences are more difficult than others. While doing so, it lays the groundwork for extending semantic theory with computational and cognitive aspects by combining linguistics and logic with computations and cognition. -/- Quantifier expressions occur whenever we describe the world and communicate about it. Generalized quantifier theory is therefore one of the basic tools of linguistics today, studying the possible meanings and the inferential power of quantifier (...) expressions by logical means. The classic version was developed in the 1980s, at the interface of linguistics, mathematics and philosophy. Before this volume, advances in "classic" generalized quantifier theory mainly focused on logical questions and their applications to linguistics, this volume adds a computational component, the third pillar of language use and logical activity. This book is essential reading for researchers in linguistics, philosophy, cognitive science, logic, AI, and computer science. (shrink)

This book develops a view of logic as a theory of information-driven agency and intelligent interaction between many agents - with conversation, argumentation and games as guiding examples. It provides one uniform account of dynamic logics for acts of inference, observation, questions and communication, that can handle both update of knowledge and revision of beliefs. It then extends the dynamic style of analysis to include changing preferences and goals, temporal processes, group action and strategic interaction in games. Throughout, the book (...) develops a mathematical theory unifying all these systems, and positioning them at the interface of logic, philosophy, computer science and game theory. A series of further chapters explores repercussions of the 'dynamic stance' for these areas, as well as cognitive science. (shrink)

This book is a comprehensive development and defense of one of the guiding assumptions of evolutionary psychology: that the human mind is composed of a large number of semi-independent modules. The Architecture of the Mind has three main goals. One is to argue for massive mental modularity. Another is to answer a 'How possibly?' challenge to any such approach. The first part of the book lays out the positive case supporting massive modularity. It also outlines how the thesis should best (...) be developed, and articulates the notion of 'module' that is in question. Then the second part of the book takes up the challenge of explaining how the sorts of flexibility and creativity that are distinctive of the human mind could possibly be grounded in the operations of a massive number of modules.Peter Carruthers's third aim is to show how the various components of the mind are likely to be linked and interact with one another - indeed, this is crucial to demonstrating how the human mind, together with its familiar capacities, can be underpinned by a massively modular set of mechanisms. He outlines and defends the basic framework of a perception / belief / desire / planning / motor-control architecture, as well as detailing the likely components and their modes of connectivity. Many specific claims about the place within this architecture of natural language, of a mind-reading system, and others are explained and motivated. A number of novel proposals are made in the course of these discussions, one of which is that creative human thought depends upon a prior kind of creativity of action.Written with unusual clarity and directness, and surveying an extensive range of research in cognitive science, this book will be essential reading for anyone with an interest in the nature and organization of the mind. (shrink)

`Folk Psychology' - our everyday talk of beliefs, desires and mental events - has long been compared with the technical language of `Cognitive Science'. Does folk psychology provide a correct account of the mental causes of our behaviour, or must our everyday terms ultimately be replaced by a language developed from computational models and neurobiology? This broad-ranging book addresses these questions, which lie at the heart of psychology and philosophy. Providing a critical overview of the key literature in the field, (...) including the seminal work of Fodor and Churchland, the author explores the classic `Frame Problem' and assesses the future prospects of cognitive science. The scope of the frame problem, touching on connec. (shrink)

Representing an epistemic situation involving several agents obviously depends on the modeling point of view one takes. We start by identifying the types of modeling points of view which are logically possible. We call the one traditionally followed by epistemic logic the perfect external approach, because there the modeler is assumed to be an omniscient and external observer of the epistemic situation. In the rest of the paper we focus on what we call the internal approach, where the modeler is (...) one of the agents involved in the situation. For this approach we propose and axiomatize a logical formalism based on epistemic logic. This leads us to formalize some intuitions about the internal approach and about its connections with the external ones. Finally, we show that our internal logic is decidable and PSPACE-complete. (shrink)

Introduction -- Evidence from children -- Evidence form infants and non-human animals -- Evidence from neuroimaging and neuropsychology -- Evidence from adults -- The cognitive basis of mindreading -- Elaborating and applying the theory.

The recognition that human minds/brains are finite systems with limited resources for computation has led some researchers to advance theTractable 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 theP‐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 theFPT‐Cognition thesisas 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 article takes off from Johan van Benthem’s ruminations on the interface between logic and cognitive science in his position paper “Logic and reasoning: Do the facts matter?”. When trying to answer Van Benthem’s question whether logic can be fruitfully combined with psychological experiments, this article focuses on a specific domain of reasoning, namely higher-order social cognition, including attributions such as “Bob knows that Alice knows that he wrote a novel under pseudonym”. For intelligent interaction, it is important that the (...) participants recursively model the mental states of other agents. Otherwise, an international negotiation may fail, even when it has potential for a win-win solution, and in a time-critical rescue mission, a software agent may depend on a teammate’s action that never materializes. First a survey is presented of past and current research on higher-order social cognition, from the various viewpoints of logic, artificial intelligence, and psychology. Do people actually reason about each other’s knowledge in the way proscribed by epistemic logic? And if not, how can logic and cognitive science productively work together to construct more realistic models of human reasoning about other minds? The paper ends with a delineation of possible avenues for future research, aiming to provide a better understanding of higher-order social reasoning. The methodology is based on a combination of experimental research, logic, computational cognitive models, and agent-based evolutionary models. (shrink)

Argues that the key distinction between human and nonhuman social cognition consists in our complex, diverse and flexible capacities to shape each other's minds in ways that make them easier to interpret.

In this paper we show how to formalise false-belief tasks like the Sally-Anne task and the second-order chocolate task in Dynamic Epistemic Logic. False-belief tasks are used to test the strength of the Theory of Mind of humans, that is, a human’s ability to attribute mental states to other agents. Having a ToM is known to be essential to human social intelligence, and hence likely to be essential to social intelligence of artificial agents as well. It is therefore important to (...) find ways of implementing a ToM in artificial agents, and to show that such agents can then solve false-belief tasks. In this paper, the approach is to use DEL as a formal framework for representing ToM, and use reasoning in DEL to solve false-belief tasks. In addition to formalising several false-belief tasks in DEL, the paper introduces some extensions of DEL itself: edge-conditioned event models and observability propositions. These extensions are introduced to provide better formalisations of the false-belief tasks, but expected to have independent future interest. (shrink)

The main aim of the present paper is to use a proof system for hybrid modal logic to formalize what are called false-belief tasks in cognitive psychology, thereby investigating the interplay between cognition and logical reasoning about belief. We consider two different versions of the Smarties task, involving respectively a shift of perspective to another person and to another time. Our formalizations disclose that despite this difference, the two versions of the Smarties task have exactly the same underlying logical structure. (...) We also consider the Sally-Anne task, having a more complicated logical structure, presupposing a “principle of inertia” saying that a belief is preserved over time, unless there is belief to the contrary. (shrink)

In this paper, we investigate the use of event models for automated planning. Event models are the action defining structures used to define a semantics for dynamic epistemic logic. Using event models, two issues in planning can be addressed: Partial observability of the environment and knowledge. In planning, partial observability gives rise to an uncertainty about the world. For single-agent domains, this uncertainty can come from incomplete knowledge of the starting situation and from the nondeterminism of actions. In multi-agent domains, (...) an additional uncertainty arises from the fact that other agents can act in the world, causing changes that are not instigated by the agent itself. For an agent to successfully construct and execute plans in an uncertain environment, the most widely used formalism in the literature on automated planning is “belief states”: sets of different alternatives for the current state of the world. Epistemic logic is a significantly more expressive and theoretically better founded method for representing knowledge and ignorance about the world. Further, epistemic logic allows for planning according to the knowledge (and iterated knowledge) of other agents, allowing the specification of a more complex class of planning domains, than those simply concerned with simple facts about the world. We show how to model multi-agent planning problems using Kripke-models for representing world states, and event models for representing actions. Our mechanism makes use of slight modifications to these concepts, in order to model the internal view of agents, rather than that of an external observer. We define a type of planning domain called epistemic planning domains, a generalisation of classical planning domains, and show how epistemic planning can successfully deal with partial observability, nondeterminism, knowledge and multiple agents. Finally, we show epistemic planning to be decidable in the single-agent case, but only semi-decidable in the multi-agent case. (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.

Dynamic Epistemic Logic This article tells the story of the rise of dynamic epistemic logic, which began with epistemic logic, the logic of knowledge, in the 1960s. Then, in the late 1980s, came dynamic epistemic logic, the logic of change of knowledge. Much of it was motivated by puzzles and paradoxes. The number … Continue reading Dynamic Epistemic Logic →.

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)

Hans van Ditmarsch and Barteld Kooi (2008). Semantic results for ontic and epistemic change. In: G. Bonanno, W. van der Hoek and M. Wooldridge (editors). Logic and the Foundations of Game and Decision Theory (LOFT 7). Texts in Logic and Games 3, pp. 87-117, Amsterdam University Press, Amsterdam.