Action and Knowledge in Alternating-Time Temporal Logic

Alternating-time temporal logic (ATL) is a branching time temporal logic in which statements about what coalitions of agents can achieve by strategic cooperation can be expressed. Alternating-time temporal epistemic logic (ATEL) extends ATL by adding knowledge modalities, with the usual possible worlds interpretation. This paper investigates how properties of agents’ actions can be expressed in ATL in general, and how properties of the interaction between action and knowledge can be expressed in ATEL in particular. One commonly discussed property is that an agent should know about all available actions, i.e., that the same actions should be available in indiscernible states. Van der Hoek and Wooldridge suggest a syntactic expression of this semantic property. This paper shows that this correspondence in fact does not hold. Furthermore, it is shown that the semantic property is not expressible in ATEL at all. In order to be able to express common and interesting properties of action in general and of the interaction between action and knowledge in particular, a generalization of the coalition modalities of ATL is proposed. The resulting logics, ATL-A and ATEL-A, have increased expressiveness without loosing ATL’s and ATEL’s tractability of model checking.     

一个用于表达因果关系的ATL的扩展

CTL模型检测技术已被广泛应用于形式验证领域。交互时态逻辑（ATL）是对CTL的一个扩展,用于表达多主体博弈结构上的性质。ATL使用合作算子来表达多个主体能够通过合作保证系统的设计目标。在实际应用中,我们需要知道主体的行动与系统的输出状态之间具有因果关系。在本文中,我们通过引入新的模态算子扩展ATL,使得这种因果关系得到表达。我们使用两种方式的扩展。其中之一是从主体的能力出发,直观上,如果一些主体可以通过合作的行动来保证系统进入某个状态,同时,这些主体也可以通过合作的行动保证系统不进入这个状态,则这些主体的行动与该系统状态间具有更强的因果关系。我们使用的另一种方式是从系统状态出发。我们考虑要想使系统进入某状态,哪些主体的行动的必不可少的,哪些主体的行动是充分的但非必要的条件。在本文中,我们扩展后的逻辑CATL和SATL表达力强于ATL,但计算复杂性与ATL相同。     

The Undecidability of Quantified Announcements

This paper demonstrates the undecidability of a number of logics with quantification over public announcements: arbitrary public announcement logic (APAL), group announcement logic (GAL), and coalition announcement logic (CAL). In APAL we consider the informative consequences of any announcement, in GAL we consider the informative consequences of a group of agents (this group may be a proper subset of the set of all agents) all of which are simultaneously (and publicly) making known announcements. So this is more restrictive than APAL. Finally, CAL is as GAL except that we now quantify over anything the agents not in that group may announce simultaneously as well. The logic CAL therefore has some features of game logic and of ATL. We show that when there are multiple agents in the language, the satisfiability problem is undecidable for APAL, GAL, and CAL. In the single agent case, the satisfiability problem is decidable for all three logics.     

Synchronization of Logics

Motivated by applications in software engineering, we propose two forms of combination of logics: synchronization on formulae and synchronization on models. We start by reviewing satisfaction systems, consequence systems, one-step derivation systems and theory spaces, as well as their functorial relationships. We define the synchronization on formulae of two consequence systems and provide a categorial characterization of the construction. For illustration we consider the synchronization of linear temporal logic and equational logic. We define the synchronization on models of two satisfaction systems and provide a categorial characterization of the construction. We illustrate the technique in two cases: linear temporal logic versus equational logic; and linear temporal logic versus branching temporal logic. Finally, we lift the synchronization on formulae to the category of logics over consequences systems.     

Logics for Epistemic Programs

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. The basic operation used in the semantics is called the update product. A version of this was introduced in Baltag et al. (1998), and the presentation here improves on the earlier one. The update product is used to obtain from any program model the corresponding epistemic update, thus allowing us to compute changes of information or belief. This point is of interest independently of our logical languages. We illustrate the update product and our logical languages with many examples throughout the paper.     

博弈论中重复可允许算法的认知分析

博弈论中重复可允许(Iterated Admissibilty)算法对于快速约简博弈模型、寻找合理置信的纳什均衡具有重要意义,但该算法的认知基础存在悖论。本文构建一个完备的博弈认知逻辑系统EL_G,利用该系统语言描述博弈相关概念和性质,使得我们可以基于EL_G逻辑刻画重复可允许算法,从而达到为该算法提供合理的认知基础,解决算法背后的认知悖论的目的。     

Rough Sets and 3-Valued Logics

In the paper we explore the idea of describing Pawlak’s rough sets using three-valued logic, whereby the value t corresponds to the positive region of a set, the value f — to the negative region, and the undefined value u — to the border of the set. Due to the properties of the above regions in rough set theory, the semantics of the logic is described using a non-deterministic matrix (Nmatrix). With the strong semantics, where only the value t is treated as designated, the above logic is a “common denominator” for Kleene and Łukasiewicz 3-valued logics, which represent its two different “determinizations”. In turn, the weak semantics—where both t and u are treated as designated—represents such a “common denominator” for two major 3-valued paraconsistent logics. We give sound and complete, cut-free sequent calculi for both versions of the logic generated by the rough set Nmatrix. Then we derive from these calculi sequent calculi with the same properties for the various “determinizations” of those two versions of the logic (including Łukasiewicz 3-valued logic). Finally, we show how to embed the four above-mentioned determinizations in extensions of the basic rough set logics obtained by adding to those logics a special two-valued “definedness” or “crispness” operator.     

Logics of public communications

Multi-modal versions of propositional logics S5 or S4—commonly accepted as logics of knowledge—are capable of describing static states of knowledge but they do not reflect how the knowledge changes after communications among agents. In the present paper (part of broader research on logics of knowledge and communications) we define extensions of the logic S5 which can deal with public communications. The logics have natural semantics. We prove some completeness, decidability and interpretability results and formulate a general method that solves certain kind of problems involving public communications—among them well known puzzles of Muddy Children and Mr. Sum & Mr. Product. As the paper gives a formal logical treatment of the operation of restriction of the universe of a Kripke model, it contributes also to investigations of semantics for modal logics. This paper was originally published as Plaza, J. A. (1989). Logics of public communications. In M. L. Emrich, M. S. Pfeifer, M. Hadzikadic, & Z.W. Ras (Eds.), Proceedings of the fourth international symposium on methodologies for intelligent systems: Poster session program (pp. 201–216). Publisher: Oak Ridge National Laboratory, ORNL/DSRD-24. Research partly supported by NSF Grant CCR-8702307 and PSC-CUNY Grant 668283.     

Well-founded semantics for defeasible logic

Fixpoint semantics are provided for ambiguity blocking and propagating variants of Nute’s defeasible logic. The semantics are based upon the well-founded semantics for logic programs. It is shown that the logics are sound with respect to their counterpart semantics and complete for locally finite theories. Unlike some other nonmonotonic reasoning formalisms such as Reiter’s default logic, the two defeasible logics are directly skeptical and so reject floating conclusions. For defeasible theories with transitive priorities on defeasible rules, the logics are shown to satisfy versions of Cut and Cautious Monotony. For theories with either conflict sets closed under strict rules or strict rules closed under transposition, a form of Consistency Preservation is shown to hold. The differences between the two logics and other variants of defeasible logic—specifically those presented by Billington, Antoniou, Governatori, and Maher—are discussed.     

Using temporal logics of knowledge for specification and verification—a case study

Temporal logics of knowledge are useful for reasoning about situations where the knowledge of an agent or component is important, and where change in this knowledge may occur over time. Here we use temporal logics of knowledge to reason about the game Cluedo. We show how to specify Cluedo using temporal logics of knowledge and prove statements about the knowledge of the players using a clausal resolution calculus for this logic. We discuss the advantages and disadvantages of using this logic to specify and verify the game Cluedo and describe related implementations.     

Keep ‘hoping’ for rationality: a solution to the backward induction paradox

We formalise a notion of dynamic rationality in terms of a logic of conditional beliefs on (doxastic) plausibility models. Similarly to other epistemic statements (e.g. negations of Moore sentences and of Muddy Children announcements), dynamic rationality changes its meaning after every act of learning, and it may become true after players learn it is false. Applying this to extensive games, we “simulate” the play of a game as a succession of dynamic updates of the original plausibility model: the epistemic situation when a given node is reached can be thought of as the result of a joint act of learning (via public announcements) that the node is reached. We then use the notion of “stable belief”, i.e. belief that is preserved during the play of the game, in order to give an epistemic condition for backward induction: rationality and common knowledge of stable belief in rationality. This condition is weaker than Aumann’s and compatible with the implicit assumptions (the “epistemic openness of the future”) underlying Stalnaker’s criticism of Aumann’s proof. The “dynamic” nature of our concept of rationality explains why our condition avoids the apparent circularity of the “backward induction paradox”: it is consistent to (continue to) believe in a player’s rationality after updating with his irrationality.     

Epistemic action: A measure for cognitive support in tangible user interfaces?

The quality of user interfaces is often measured in terms of efficiency, effectiveness, and satisfaction. In the area of tangible user interfaces, epistemic—or exploratory—action has been suggested as a fourth measure of quality. In computer game studies (Kirsh & Maglio, 1992, 1994), players used epistemic actions to modify the environment, which helped them determine the correct position of blocks with less mental effort. There, the researchers found that it might be easier to physically modify the external world and then interpret it than to compute and interpret a new state mentally. Specifically, epistemic action may be a relevant concept when researching tangible user interfaces incorporating physical handles. This article examines the potential relations between the three traditional measures of usability and epistemic actions using three spatial planning tools with different degrees of physicality. The results indicate that epistemic action is a measure that is independent of the three traditional usability measures: efficiency, effectiveness, and satisfaction. However, epistemic action does not increase linearly with the physicality of a user interface, and it probably is a more complex measure that is also related to the reusability of the interface. Further research is needed to fully understand the potential of this measure.     

Extending probabilistic dynamic epistemic logic

This paper aims to extend in two directions the probabilistic dynamic epistemic logic provided in Kooi’s paper (J Logic Lang Inform 12(4):381–408, 2003) and to relate these extensions to ones made in van Benthem et al. (Proceedings of LOFT’06. Liverpool, 2006). Kooi’s probabilistic dynamic epistemic logic adds to probabilistic epistemic logic sentences that express consequences of public announcements. The paper (van Benthem et al., Proceedings of LOFT’06. Liverpool, 2006) extends (Kooi, J Logic Lang Inform 12(4):381–408, 2003) to using action models, but in both papers, the probabilities are discrete, and are defined on trivial σ-algebras over finite sample spaces. The first extension offered in this paper is to add a previous-time operator to a probabilistic dynamic epistemic logic similar to Kooi’s in (J Logic Lang Inform 12(4):381–408, 2003). The other is to involve non-trivial σ-algebras and continuous probabilities in probabilistic dynamic epistemic logic.     

A Sat-Based Approach to Unbounded Model Checking for Alternating-Time Temporal Epistemic Logic

This paper deals with the problem of verification of game-like structures by means of symbolic model checking. Alternating-time Temporal Epistemic Logic (ATEL) is used for expressing properties of multi-agent systems represented by alternating epistemic temporal systems as well as concurrent epistemic game structures. Unbounded model checking (a SAT based technique) is applied for the first time to verification of ATEL. An example is given to show an application of the technique.     

On logic of complex algorithms

An algebraic approach to programs called recursive coroutines — due to Janicki [3] — is based on the idea to consider certain complex algorithms as algebraics models of those programs. Complex algorithms are generalizations of pushdown algorithms being algebraic models of recursive procedures (see Mazurkiewicz [4]). LCA — logic of complex algorithms — was formulated in [11]. It formalizes algorithmic properties of a class of deterministic programs called here complex recursive ones or interacting stacks-programs, for which complex algorithms constitute mathematical models. LCA is in a sense an extension of algorithmic logic as initiated by Salwicki [14] and of extended algorithmic logic EAL as formulated and examined by the present author in [8], [9], [10]. In LCA — similarly as in EAL-ω ⁺ -valued logic is applied as a tool to construct control systems (stacks) occurring in corresponding algorithms. The aim of this paper is to give a complete axiomatization. of LCA and to prove a completeness theorem. Logic of complex algorithms was presented at FCT'79 (International Symposium on Fundamentals of Computation Theory, Berlin 1979)     

Awareness Dynamics

In recent years, much work has been dedicated by logicians, computer scientists and economists to understanding awareness, as its importance for human behaviour becomes evident. Although several logics of awareness have been proposed, little attention has been explicitly dedicated to change in awareness. However, one of the most crucial aspects of awareness is the changes it undergoes, which have countless important consequences for knowledge and action. The aim of this paper is to propose a formal model of awareness change, and to derive from it logics of awareness change. In the first part of the paper, the model of epistemic states of bounded agents proposed in Hill (Stud Log 89(1):81–109, 2008a) is extended with operations modelling awareness change. In the second part of the paper, it is shown how this model naturally extends the “standard” logic of awareness to yield a logic of awareness change.     

A Few More Useful 8-valued Logics for Reasoning with Tetralattice <Emphasis Type="Italic">EIGHT</Emphasis><Subscript>4</Subscript>

In their useful logic for a computer network Shramko and Wansing generalize initial values of Belnap’s 4-valued logic to the set 16 to be the power-set of Belnap’s 4. This generalization results in a very specific algebraic structure — the trilattice SIXTEEN ₃ with three orderings: information, truth and falsity. In this paper, a slightly different way of generalization is presented. As a base for further generalization a set 3 is chosen, where initial values are a — incoming data is asserted, d — incoming data is denied, and u — incoming data is neither asserted nor denied, that corresponds to the answer “don’t know”. In so doing, the power-set of 3, that is the set 8 is considered. It turns out that there are not three but four orderings naturally defined on the set 8 that form the tetralattice EIGHT ₄. Besides three ordering relations mentioned above it is an extra uncertainty ordering. Quite predictably, the logics generated by a–order (truth order) and d–order (falsity order) coincide with first-degree entailment. Finally logic with two kinds of operations (a–connectives and d–connectives) and consequence relation defined via a–ordering is considered. An adequate axiomatization for this logic is proposed.