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)

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)

This modern, advanced textbook reviews modal logic, a field which caught the attention of computer scientists in the late 1970's.

We study a generalization of the Muddy Children puzzle by allowing public announcements with arbitrary generalized quantifiers. We propose a new concise logical modeling of the puzzle based on the number triangle representation of quantifi ers. Our general aim is to discuss the possibility of epistemic modeling that is cut for specifi c informational dynamics. Moreover, we show that the puzzle is solvable for any number of agents if and only if the quanti fier in the announcement is positively active (...) (satis es a form of variety). (shrink)

Public announcement logic is an extension of multiagent epistemic logic with dynamic operators to model the informational consequences of announcements to the entire group of agents. We propose an extension of public announcement logic with a dynamic modal operator that expresses what is true after any announcement: after which , does it hold that Kφ? We give various semantic results and show completeness for a Hilbert-style axiomatization of this logic. There is a natural generalization to a logic for arbitrary events.

Reasoning About Knowledge is the first book to provide a general discussion of approaches to reasoning about knowledge and its applications to distributed ...

We construct logical languages which allow one to represent a variety of possible types of changes affecting the information states of agents in a multi-agent setting. We formalize these changes by defining a notion of epistemic program. The languages are two-sorted sets that contain not only sentences but also actions or programs. This is as in dynamic logic, and indeed our languages are not significantly more complicated than dynamic logics. But the semantics is more complicated. In general, the semantics of (...) an epistemic program is what we call aprogram model. This is a Kripke model of ‘actions’,representing the agents' uncertainty about the current action in a similar way that Kripke models of ‘states’ are commonly used in epistemic logic to represent the agents' uncertainty about the current state of the system. Program models induce changes affecting agents' information, which we represent as changes of the state model, called epistemic updates. Formally, an update consists of two operations: the first is called the update map, and it takes every state model to another state model, called the updated model; the second gives, for each input state model, a transition relation between the states of that model and the states of the updated model. Each variety of epistemic actions, such as public announcements or completely private announcements to groups, gives what we call an action signature, and then each family of action signatures gives a logical language. The construction of these languages is the main topic of this paper. We also mention the systems that capture the valid sentences of our logics. But we defer to a separate paper the completeness proof. (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)

The Aristotelian syllogistic cannot account for the validity of certain inferences involving relational facts. In this paper, we investigate the prospects for providing a relational syllogistic. We identify several fragments based on (a) whether negation is permitted on all nouns, including those in the subject of a sentence; and (b) whether the subject noun phrase may contain a relative clause. The logics we present are extensions of the classical syllogistic, and we pay special attention to the question of whether reductio (...) ad absurdum is needed. Thus our main goal is to derive results on the existence (or nonexistence) of syllogistic proof systems for relational fragments. We also determine the computational complexity of all our fragments. (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 two case studies of multi-agent information exchange involving generalized quantifiers. We focus on scenarios in which agents successfully converge to knowledge on the basis of the information about the knowledge of others, so-called Muddy Children puzzle and Top Hat puzzle. We investigate the relationship between certain invariance properties of quantifiers and the successful convergence to knowledge in such situations. We generalize the scenarios to account for public announcements with arbitrary quantifiers. We show that the Muddy Children puzzle (...) is solvable for any number of agents if and only if the quantifier in the announcement is positively active (satisfies a version of the variety condition). In order to get the characterization result, we propose a new concise logical modeling of the puzzle based on the number triangle representation of generalized quantifiers. In a similar vein, we also study the Top Hat puzzle. We observe that in this case an announcement needs to satisfy stronger conditions in order to guarantee solvability. Hence, we introduce a new property, called bounded thickness, and show that the solvability of the Top Hat puzzle for arbitrary number of agents is equivalent to the announcement being 1-thick. (shrink)