When seeking to coordinate in a game with imperfect information, it is often relevant for a player to know what other players know. Keeping track of the information acquired in a play of infinite duration may, however, lead to infinite hierarchies of higher-order knowledge. We present a construction that makes explicit which higher-order knowledge is relevant in a game and allows us to describe a class of games that admit coordinated winning strategies with finite memory.

A method is described for inducing a type-logical grammar from a sample of bare sentence trees which are annotated by lambda terms, called term-labelled trees . Any type logic from a permitted class of multimodal logics may be specified for use with the procedure, which induces the lexicon of the grammar including the grammatical categories. A first stage of semantic bootstrapping is performed, which induces a general form lexicon from the sample of term-labelled trees using Fulop’s (J Log Lang Inf (...) 14(1):49–86, 2005) procedure. Next we present a two-stage procedure for performing distributional learning by unifying the lexical types that are initially discovered. The first structural unification algorithm in essence unifies the initial family of sets of types so that the resulting grammar will generate all term-labelled trees that follow the usage patterns evident from the learning sample. Further altering the lexical categories to generate a recursively extended language can be accomplished by a second unification. The combined unification algorithm is shown to yield a new type-logical lexicon that extends the learning sample to a possibly infinite (and possibly context-sensitive) language in a principled fashion. Finally, the complete learning strategy is analyzed from the perspective of algorithmic learning theory; the range of the procedure is shown to be a class of term-labelled tree languages which is finitely learnable from good examples (Lange et al in Algorithmic learning theory, Vol 872 of lecture notes in artificial intelligence, Springer, Berlin, pp 423–437), and so is identifiable in the limit as a corollary. (shrink)

This paper surveys the interface between the two major logical trends that describe agents’ intelligent interaction over time: dynamic epistemic logic (DEL) and epistemic temporal logic (ETL). The initial attempt to “merge” DEL and ETL was made in van Benthem et al. (Merging frameworks for interaction: DEL and ETL, 2007) and followed up by van Benthem et al. (J Phil Logic 38(5):491–526, 2009) and Hoshi (Epistemic dynamics and protocol information. Ph.D. thesis, Stanford University Stanford, 2009a). The merged framework provides a (...) systematic comparison between these two logical systems and studies new logics of intelligent interaction. This paper presents the main results and the recent developments at the interface between DEL and ETL. (shrink)

Impossible worlds are regarded with understandable suspicion by most philosophers. Here we are concerned with a modal argument which might seem to show that acknowledging their existence, or more particularly, the existence of some hypothetical (we do not say “possible”) world in which everything was the case, would have drastic effects, forcing us to conclude that everything is indeed the case—and not just in the hypothesized world in question. The argument is inspired by a metaphysical (rather than modal-logical) argument of (...) Paul Kabay’s which would have us accept this unpalatable conclusion, though its details bear a closer resemblance to a line of thought developed by Jc Beall, in response to which Graham Priest has made some philosophical moves which are echoed in our diagnosis of what goes wrong with the present modal argument. Logical points of some interest independent of the main issue arise along the way. (shrink)

Diachronic uncertainty, uncertainty about where an agent falls in time, poses interesting conceptual difficulties. Although the agent is uncertain about where she falls in time, this uncertainty can only obtain at a particular moment in time. We resolve this conceptual tension by providing a transformation from models with diachronic uncertainty relations into “equivalent” models with only synchronic uncertainty relations. The former are interpreted as capturing the causal structure of a situation, while the latter are interpreted as capturing its epistemic structure (...) . The models are equivalent in the sense that agents pass through the same information sets in the same order, In this paper, we investigate how such a transformation may be used to define an appropriate notion of equivalence, which we call epistemic equivalence . Although our project is motivated by problems which have arisen in a variety of disciplines, especially philosophy and game theory, our formal development takes place within the general and flexible framework provided by epistemic temporal logic. (shrink)

Tarski avoids the liar paradox by relativizing truth and falsehood to particular languages and forbidding the predication to sentences in a language of truth or falsehood by any sentences belonging to the same language. The Tarski truth-schemata stratify an object-language and indefinitely ascending hierarchy of meta-languages in which the truth or falsehood of sentences in a language can only be asserted or denied in a higher-order meta-language. However, Tarski’s statement of the truth-schemata themselves involve general truth functions, and in particular (...) the biconditional, defined in terms of truth conditions involving truth values standardly displayed in a truth table. Consistently with his semantic program, all such truth values should also be relativized to particular languages for Tarski. The objection thus points toward the more interesting problem of Tarski’s concept of the exact status of truth predications in a general logic of sentential connectives. Tarski’s three-part solution to the circularity objection which he anticipates is discussed and refuted in detail. (shrink)

The situation calculus is one of the most established formalisms for reasoning about action and change. In this paper we will review the basics of Reiter’s version of the situation calculus, show how knowledge and time have been addressed in this framework, and point to some of the weaknesses of the situation calculus with respect to time. We then present a modal version of the situation calculus where these problems can be overcome with relative ease and without sacrificing the advantages (...) of the original. (shrink)

We continue the work initiated in Herzig and Lorini (J Logic Lang Inform, in press) whose aim is to provide a minimalistic logical framework combining the expressiveness of dynamic logic in which actions are first-class citizens in the object language, with the expressiveness of logics of agency such as STIT and logics of group capabilities such as CL and ATL. We present a logic called ( Deterministic Dynamic logic of Agency ) which supports reasoning about actions and joint actions of (...) agents and coalitions, and agentive and coalitional capabilities. In it is supposed that, once all agents have selected a joint action, the effect of this joint action is deterministic. In order to assess we prove that it embeds Coalition Logic. We then extend with modal operators for agents’ preferences, and show that the resulting logic is sufficiently expressive to capture the game-theoretic concepts of best response and Nash equilibrium. (shrink)

We suggest that developing automata theoretic foundations is relevant for knowledge theory, so that we study not only what is known by agents, but also the mechanisms by which such knowledge is arrived at. We define a class of epistemic automata , in which agents’ local states are annotated with abstract knowledge assertions about others. These are finite state agents who communicate synchronously with each other and information exchange is ‘perfect’. We show that the class of recognizable languages has good (...) closure properties, leading to a Kleene-type theorem using what we call regular knowledge expressions . These automata model distributed causal knowledge in the following way: each agent in the system has a partial knowledge of the temporal evolution of the system, and every time agents synchronize, they update each other’s knowledge, resulting in a more up-to-date view of the system state. Hence we show that these automata can be used to solve the satisfiability problem for a natural epistemic temporal logic for local properties. Finally, we characterize the class of languages recognized by epistemic automata as the regular consistent languages studied in concurrency theory. (shrink)

We conducted a computer-based psychological experiment in which a random mix of 40 tautologies and 40 non-tautologies were presented to the participants, who were asked to determine which ones of the formulas were tautologies. The participants were eight university students in computer science who had received tuition in propositional logic. The formulas appeared one by one, a time-limit of 45 s applied to each formula and no aids were allowed. For each formula we recorded the proportion of the participants who (...) classified the formula correctly before timeout (accuracy) and the mean response time among those participants (latency). We propose a new proof formalism for modeling propositional reasoning with bounded cognitive resources. It models declarative memory, visual memory, working memory, and procedural memory according to the memory model of Atkinson and Shiffrin and reasoning processes according to the model of Newell and Simon. We also define two particular proof systems, T and NT , for showing propositional formulas to be tautologies and non-tautologies, respectively. The accuracy was found to be higher for non-tautologies than for tautologies ( p T was .89 and for non-tautologies the correlation between latency and minimum proof length in NT was .87. (shrink)

We present a simple theory of actions against the background of branching time, based on which we propose two versions of an extended stit theory, one equipped with particular actions and the other with sets of such actions. After reporting some basic results of a formal development of such a theory, we briefly explore its connection to a version of branching ETL.

Probability logics have been an active topic of investigation of beliefs in type spaces in game theoretical economics. Beliefs are expressed as subjective probability measures. Savage’s postulates in decision theory imply that subjective probability measures are not necessarily countably additive but finitely additive. In this paper, we formulate a probability logic Σ + that is strongly complete with respect to this class of type spaces with finitely additive probability measures, i.e. a set of formulas is consistent in Σ + iff (...) it is satisfied in a finitely additive type space. Although we can characterize Σ + -theories satisfiable in the class as maximally consistent sets of formulas, we prove that any canonical model of maximally consistent sets is not universal in the class of type spaces with finitely additive measures, and, moreover, it is not a type space. At the end of this paper, we show that even a minimal use of probability indices causes the failure of compactness in probability logics. (shrink)