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)

1) We will begin by offering a short introduction to Epistemic Logic and presenting Fitch’s paradox in an epistemic‑modal logic. (2) Then, we will proceed to presenting three Epistemic Temporal logical frameworks creat‑ ed by Hoshi (2009) : TPAL (Temporal Public Announcement Logic), TAPAL (Temporal Arbitrary Public Announcement Logic) and TPAL+P ! (Temporal Public Announcement Logic with Labeled Past Operators). We will show how Hoshi stated the Verificationist Thesis (...) in the language of TAPAL and analyze his argument on why this version of it is immune from paradox. (3) Edgington (1985) offered an interpretation of the Verificationist Thesis that blocks Fitch’s paradox and we will propose a way to formulate it in a TAPAL‑based lan‑ guage. The language we will use is a combination of TAPAL and TPAL+P ! with an Indefinite (Unlabeled) Past Operator (TAPAL+P !+P). Using indexed satisfi‑ ability relations (as introduced in (Wang 2010 ; 2011)) we will offer a prospec ‑ tive semantics for this language. We will investigate whether the tentative re‑ formulation of Edgington’s Verificationist Thesis in TAPAL+P !+P is free from paradox and adequate to Edgington’s ideas on how „all truths are knowable“ should be interpreted. (shrink)

We present an epistemic default logic, based on the metaphore of a meta-level architecture. Upward reflection is formalized by a nonmonotonic entailment relation, based on the objective facts that are either known or unknown at the object level. Then, the meta (monotonic) reasoning process generates a number of default-beliefs of object-level formulas. We extend this framework by proposing a mechanism to reflect these defaults down. Such a reflection is seen as essentially having a temporal flavour: defaults derived (...) at the meta-level are projected as facts in a next object level state. In this way, we obtain temporal models for default reasoning in meta-level formalisms which can be conceived as labeled branching trees. Thus, descending the tree corresponds to shifts in time that model downward reflection, whereas the branching of the tree corresponds to ways of combining possible defaults. All together, this yields an operational or procedural semantics of reasoning by default, which admits one to reason about it by means of branching-time temporal logic. Finally, we define sceptical and credulous entailment relations based on these temporal models and we characterize Reiter extensions in our semantics. (shrink)

We present Dynamic Epistemic Temporal Logic, a framework for reasoning about operations on multi-agent Kripke models that contain a designated temporal relation. These operations are natural extensions of the well-known “action models” from Dynamic Epistemic Logic. Our “temporal action models” may be used to define a number of informational actions that can modify the “objective” temporal structure of a model along with the agents’ basic and higher-order knowledge and beliefs about this structure, (...) including their beliefs about the time. In essence, this approach provides one way to extend the domain of action model-style operations from atemporal Kripke models to temporal Kripke models in a manner that allows actions to control the flow of time. We present a number of examples to illustrate the subtleties involved in interpreting the effects of our extended action models on temporal Kripke models. We also study preservation of important epistemic-temporal properties of temporal Kripke models under temporal action model-induced operations, provide complete axiomatizations for two theories of temporal action models, and connect our approach with previous work on time in DEL. (shrink)

van Bentham et al. (Merging frameworks for interaction: DEL and ETL, 2007) provides a framework for generating the models of Epistemic Temporal Logic ( ETL : Fagin et al., Reasoning about knowledge, 1995; Parikh and Ramanujam, Journal of Logic, Language, and Information, 2003) from the models of Dynamic Epistemic Logic ( DEL : Baltag et al., in: Gilboa (ed.) Tark 1998, 1998; Gerbrandy, Bisimulations on Planet Kripke, 1999). We consider the logic TDEL on (...) the merged semantic framework, and its extension with the labeled past-operator “ P ϵ ” (“The event ϵ has happened before which. . .”). To axiomatize the extension, we introduce a method for transforming a given model into a normal form in a suitable sense. These logics suggest further applications of DEL in the theory of agency, the theory of learning, etc. (shrink)

We combine linear temporal logic (with both past and future modalities) with a deontic version of justification logic to provide a framework for reasoning about time and epistemic and normative reasons. In addition to temporal modalities, the resulting logic contains two kinds of justification assertions: epistemic justification assertions and deontic justification assertions. The former presents justification for the agent’s knowledge and the latter gives reasons for why a proposition is obligatory. We present two (...) kinds of semantics for the logic: one based on Fitting models and the other based on neighborhood models. The use of neighborhood semantics enables us to define the dual of deontic justification assertions properly, which corresponds to a notion of permission in deontic logic. We then establish the soundness and completeness of an axiom system of the logic with respect to these semantics. Further, we formalize the Protagoras versus Euathlus paradox in this logic and present a precise analysis of the paradox, and also briefly discuss Leibniz’s solution. (shrink)

In the study of nonmonotonic reasoning the main emphasis has been on static (declarative) aspects. Only recently has there been interest in the dynamic aspects of reasoning processes, particularly in artificial intelligence. We study the dynamics of reasoning processes by using a temporal logic to specify them and to reason about their properties, just as is common in theoretical computer science. This logic is composed of a base temporal epistemic logic with a preference relation (...) on models, and an associated nonmonotonic inference relation, in the style of Shoham, to account for the nonmonotonicity. We present an axiomatic proof system for the base logic and study decidability and complexity for both the base logic and the nonmonotonic inference relation based on it. Then we look at an interesting class of formulas, prove a representation result for it, and provide a link with the rule of monotonicity. (shrink)

This chapter contains sections titled: Modal Concepts The Semantics of Modalities and Systems of Modal Logic Modality and Quantification Deontic, Epistemic, and Temporal Modalities Epistemic Logic Deontic Logic Temporal Frames Conditional Obligations and Rules of Detachment.

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. (shrink)

This paper adds temporal logic to public announcement logic (PAL) and dynamic epistemic logic (DEL). By adding a previous-time operator to PAL, we express in the language statements concerning the muddy children puzzle and sum and product. We also express a true statement that an agent’s beliefs about another agent’s knowledge flipped twice, and use a sound proof system to prove this statement. Adding a next-time operator to PAL, we provide formulas that express that belief (...) revision does not take place in PAL. We also discuss relationships between announcements and the new knowledge agents thus acquire; such relationships are related to learning and to Fitch’s paradox. We also show how inverse programs and hybrid logic each can be used to help determine whether or not an arbitrary structure represents the play of a game. We then add a past-time operator to DEL, and discuss the importance of adding yet another component to the language in order to prove completeness. (shrink)

When reasoning about complex domains, where information available is usually only partial, nonmonotonic reasoning can be an important tool. One of the formalisms introduced in this area is Reiter's Default Logic (1980). A characteristic of this formalism is that the applicability of default (inference) rules can only be verified in the future of the reasoning process. We describe an interpretation of default logic in temporal epistemic logic which makes this characteristic explicit. It is shown that (...) this interpretation yields a semantics for default logic based on temporal epistemic models. A comparison between the various semantics for default logic will show the differences and similarities of these approaches and ours. (shrink)

The paper offers a formalization of reasoning about distributed multi-agent systems. The presented propositional probabilistic temporal epistemic logic |$\textbf {PTEL}$| is developed in full detail: syntax, semantics, soundness and strong completeness theorems. As an example, we prove consistency of the blockchain protocol with respect to the given set of axioms expressed in the formal language of the logic. We explain how to extend |$\textbf {PTEL}$| to axiomatize the corresponding first-order logic.

We study a propositional probabilistic temporal epistemic logic |$\textbf {PTEL}$| with both future and past temporal operators, with non-rigid set of agents and the operators for agents’ knowledge and for common knowledge and with probabilities defined on the sets of runs and on the sets of possible worlds. A semantics is given by a class |${\scriptsize{\rm Mod}}$| of Kripke-like models with possible worlds. We prove decidability of |$\textbf {PTEL}$| by showing that checking satisfiability of a formula (...) in |${\scriptsize{\rm Mod}}$| is equivalent to checking its satisfiability in a finite set of finitely representable structures. The same procedure can be applied to the class of all synchronous |${\scriptsize{\rm Mod}}$|-models. We give an upper complexity bound for the satisfiability problem for |${\scriptsize{\rm Mod}}$|⁠. (shrink)

Branching-time temporal logics have proved to be an extraordinarily successful tool in the formal specification and verification of distributed systems. Much of their success stems from the tractability of the model checking problem for the branching time logic CTL, which has made it possible to implement tools that allow designers to automatically verify that systems satisfy requirements expressed in CTL. Recently, CTL was generalised by Alur, Henzinger, and Kupferman in a logic known as Alternating-time Temporal (...) class='Hi'>Logic (ATL). The key insight in ATL is that the path quantifiers of CTL could be replaced by cooperation modalities, of the form , where is a set of agents. The intended interpretation of an ATL formula is that the agents can cooperate to ensure that holds (equivalently, that have a winning strategy for ). In this paper, we extend ATL with knowledge modalities, of the kind made popular in the work of Fagin, Halpern, Moses, Vardi and colleagues. Combining these knowledge modalities with ATL, it becomes possible to express such properties as group can cooperate to bring about iff it is common knowledge in that . The resulting logic — Alternating-time Temporal Epistemic Logic (ATEL) — shares the tractability of model checking with its ATL parent, and is a succinct and expressive language for reasoning about game-like multiagent systems. (shrink)

This paper contributes to an increasing literature strengthening the connection between epistemic logic and epistemology (Van Benthem, Hendricks). I give a survey of the most important applications of epistemic logic in epistemology. I show how it is used in the history of philosophy (Steiner's reconstruction of Descartes' sceptical argument), in solutions to Moore's paradox (Hintikka), in discussions about the relation between knowledge and belief (Lenzen) and in an alleged refutation of verificationism (Fitch) and I examine an (...) early argument about the (im)possibility of epistemic logic (Hocutt). Subsequently, I deal with interpretive questions about epistemic logic that, although implicitly, already appeared in the first section. I contend that a conception of epistemic logic as a theory of knowledge assertions is incoherent, and I argue that it does not make sense to adopt a normative interpretation of epistemic logic. Finally, I show ways to extend epistemic logic with other branches of philosophical logic so as to make it useful for some epistemological questions. Conditional logics and logics of public announcement are used to understand causal theories of knowledge and versions of reliabilism. Temporal logic helps understand some dynamic aspects of knowledge as well as the verificationist thesis. (shrink)

Compositional verification aims at managing the complexity of theverification process by exploiting compositionality of the systemarchitecture. In this paper we explore the use of a temporal epistemiclogic to formalize the process of verification of compositionalmulti-agent systems. The specification of a system, its properties andtheir proofs are of a compositional nature, and are formalized within acompositional temporal logic: Temporal Multi-Epistemic Logic. It isshown that compositional proofs are valid under certain conditions.Moreover, the possibility of incorporating default (...) persistence ofinformation in a system, is explored. A completion operation on aspecific type of temporal theories, temporal completion, is introducedto be able to use classical proof techniques in verification withrespect to non-classical semantics covering default persistence. (shrink)

Temporal epistemic logics are known, from results of Halpern and Vardi, to have a wide range of complexities of the satisfiability problem: from PSPACE, through non-elementary, to highly undecidable. These complexities depend on the choice of some key parameters specifying, inter alia, possible interactions between time and knowledge, such as synchrony and agents' abilities for learning and recall. In this work we develop practically implementable tableau-based decision procedures for deciding satisfiability in single-agent synchronous temporal-epistemic logics with (...) interactions between time and knowledge. We discuss some complications that occur, even in the single-agent case, when interactions between time and knowledge are assumed and show how the method of incremental tableaux can be adapted to work in EXPSPACE, respectively 2EXPTIME, for these logics, thereby also matching the upper bounds obtained for them by Halpern and Vardi. (shrink)

Branching-time temporal logics have proved to be an extraordinarily successful tool in the formal specification and verification of distributed systems. Much of their success stems from the tractability of the model checking problem for the branching time logic CTL, which has made it possible to implement tools that allow designers to automatically verify that systems satisfy requirements expressed in CTL. Recently, CTL was generalised by Alur, Henzinger, and Kupferman in a logic known as "Alternating-time Temporal (...) class='Hi'>Logic". The key insight in ATL is that the path quantifiers of CTL could be replaced by "cooperation modalities", of the form $\langle \langle \Gamma \rangle \rangle $, where Γ is a set of agents. The intended interpretation of an ATL formula $\langle \langle \Gamma \rangle \rangle \varphi $ is that the agents Γ can cooperate to ensure that φ holds. In this paper, we extend ATL with knowledge modalities, of the kind made popular in the work of Fagin, Halpern, Moses, Vardi and colleagues. Combining these knowledge modalities with ATL, it becomes possible to express such properties as "group Γ can cooperate to bring about φ iff it is common knowledge in Γ that ψ". The resulting logic -- Alternating-time Temporal Epistemic Logic -- shares the tractability of model checking with its ATL parent, and is a succinct and expressive language for reasoning about game-like multiagent systems. (shrink)

'Epistemic' theories of vagueness notoriously claim that (despite the appearances to the contrary) all of our vague terms have sharp boundaries, it's just that we can't know what they are. Epistemic theories are typically criticized for failing to explain (1) the source of the ignorance postulated, and (2) how our terms could come to have such precise boundaries. Both of these objections will, however, be shown to rest on certain 'presentist' assumptions about the relation between use and meaning, (...) and if allows that the meaning constitutive elements of our linguistic practices can extend into the future, the possibility of a new sort of 'normative epistemicism' emerges. (shrink)

Temporal justification logic is a new family of temporal logics of knowledge in which the knowledge of agents is modelled using a justification logic. In this paper, we present various temporal justification logics involving both past and future time modalities. We combine Artemov’s logic of proofs with linear temporal logic with past, and we also investigate several principles describing the interaction of justification and time. We present two kinds of semantics for our (...) temporal justification logics, one based on interpreted systems and Fitting models and the other based on Mkrtychev models, and further, we establish soundness and completeness. We show that the internalization property holds in some of the temporal justification logics. We further investigate the two well-known epistemic-temporal notions of no forgetting and no learning in the framework of justification logics. Finally, we present temporal justification logics that avoid the logical omniscience problem. (shrink)

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.

It has recently been argued that a person’s moral judgments (about both their own and others’ actions) are constrained by the nature and extent of their relevant ignorance and, thus, that such judgments are determined in the first instance by the person’s epistemic circumstances. It has been argued, in other words, that the epistemic is logically prior to other normative (e.g., ethical, prudential, pecuniary) considerations in human decision-making, that these other normative considerations figure in decision-making only after (logically (...) and temporally) relevant ignorance has constrained the decision-maker’s menu of options. If this is right, then a person’s moral judgments in some set of circumstances should vary with their knowledge and ignorance of these circumstances. In this study, we test the hypothesis of the logical priority of the epistemic. We describe two experiments in which subjects’ knowledge and ignorance of relevant consequences were manipulated. In the second experiment, we also compared the effect of ignorance on moral judgments with that of personal force, a factor previously shown to influence moral judgments. We found broad empirical support for the armchair arguments that epistemic considerations are logically prior to normative considerations. (shrink)

In dynamical multi-agent systems, agents are controlled by protocols. In choosing a class of formal protocols, an implicit choice is made concerning the types of agents, actions and dynamics representable. This paper investigates one such choice: An intensional protocol class for agent control in dynamic epistemic logic (DEL), called ‘DEL dynamical systems’. After illustrating how such protocols may be used in formalizing and analyzing information dynamics, the types of epistemic temporal models that they may generate are (...) characterized. This facilitates a formal comparison with the only other formal protocol framework in dynamic epistemic logic, namely the extensional ‘DEL protocols’. The paper concludes with a conceptual comparison, highlighting modeling tasks where DEL dynamical systems are natural. (shrink)

In dynamical multi-agent systems, agents are controlled by protocols. In choosing a class of formal protocols, an implicit choice is made concerning the types of agents, actions and dynamics representable. This paper investigates one such choice: An intensional protocol class for agent control in dynamic epistemic logic, called ‘DEL dynamical systems’. After illustrating how such protocols may be used in formalizing and analyzing information dynamics, the types of epistemic temporal models that they may generate are characterized. (...) This facilitates a formal comparison with the only other formal protocol framework in dynamic epistemic logic, namely the extensional ‘DEL protocols’. The paper concludes with a conceptual comparison, highlighting modeling tasks where DEL dynamical systems are natural. (shrink)

We present a technique for automatically verifying cryptographic protocols specified in the mainstream specification language CAPSL. We define a translation from CAPSL models into interpreted systems, a popular semantics for temporal-epistemic logic, and rewrite CAPSL goals as temporal-epistemic specifications. We present a compiler that implements this translation. The compiler links to the symbolic model checker MCMAS. We evaluate the technique on protocols in the Clark-Jacobs library and in the SPORE repository against custom secrecy and authentication (...) requirements. (shrink)

In an earlier paper by the author, Åqvist , I presented an approach to the logic of historical necessity, or inevitability, in the sense of a “two-dimensional” combination of tense and modal logic for worlds, or histories, with the same time order, known as T × W logic. Distinctive features of that approach were, apart from its two-dimensionality, its being based on discrete and finite time, and its use of so-called systematic frame constants in order to enable (...) us to indicate longitudes and latitudes of any points in the co-ordinate systems under consideration. This led us to study and axiomatize an infinite hierarchy HTWxy of two-dimensional modal tense logics with the characteristic operators for historical necessity and possibility added to the original basic vocabulary. The main purpose of the present paper is then twofold: to extend the logics HTWxy to the interesting branch of philosophical logic constituted by deontic logic as combined with tense logic; and to deal with a curious puzzle known as the so-called epistemic obligation paradox – a well known stumbling-block in this area of research in philosophical logic. We argue for a solution to both these problems, which appeals to a new infinite hierarchy DHTWxym of extensions of the HTWxy in the sense of logics combining dyadic deontic modalities with temporal ones such as those for historical necessity and other two-dimensional modalities. (shrink)

Epistemic logic in the tradition of Hintikka provides, as one of its many applications, a toolkit for the precise analysis of certain epistemological problems. In recent years, dynamic epistemic logic has expanded this toolkit. Dynamic epistemic logic has been used in analyses of well-known epistemic “paradoxes”, such as the Paradox of the Surprise Examination and Fitch’s Paradox of Knowability, and related epistemic phenomena, such as what Hintikka called the “anti-performatory effect” of Moorean (...) announcements. In this paper, we explore a variation on basic dynamic epistemic logic—what we call sequential epistemic logic—and argue that it allows more faithful and fine-grained analyses of those epistemological topics. (shrink)

Epistemic logic in the tradition of Hintikka provides, as one of its many applications, a toolkit for the precise analysis of certain epistemological problems. In recent years, dynamic epistemic logic has expanded this toolkit. Dynamic epistemic logic has been used in analyses of well-known epistemic “paradoxes”, such as the Paradox of the Surprise Examination and Fitch’s Paradox of Knowability, and related epistemic phenomena, such as what Hintikka called the “anti-performatory effect” of Moorean (...) announcements. In this paper, we explore a variation on basic dynamic epistemic logic—what we call sequential epistemic logic—and argue that it allows more faithful and fine-grained analyses of those epistemological topics. (shrink)

It has recently been argued that a person’s moral judgments (about both their own and others’ actions) are constrained by the nature and extent of their relevant ignorance and, thus, that such judgments are determined in the first instance by the person’s epistemic circumstances. It has been argued, in other words, that the epistemic is logically prior to other normative (e.g., ethical, prudential, pecuniary) considerations in human decision-making, that these other normative considerations figure in decision-making only after (logically (...) and temporally) relevant ignorance has constrained the decision-maker’s menu of options. If this is right, then a person’s moral judgments in some set of circumstances should vary with their knowledge and ignorance of these circumstances. In this study, we test the hypothesis of the logical priority of the epistemic. We describe two experiments in which subjects’ knowledge and ignorance of relevant consequences were manipulated. In the second experiment, we also compared the effect of ignorance on moral judgments with that of personal force, a factor previously shown to influence moral judgments. We found broad empirical support for the armchair arguments that epistemic considerations are logically prior to normative considerations. (shrink)

Formal learning theory constitutes an attempt to describe and explain the phenomenon of learning, in particular of language acquisition. The considerations in this domain are also applicable in philosophy of science, where it can be interpreted as a description of the process of scientific inquiry. The theory focuses on various properties of the process of hypothesis change over time. Treating conjectures as informational states, we link the process of conjecture-change to epistemic update. We reconstruct and analyze the temporal (...) aspect of learning in the context of dynamic and temporal logics of epistemic change. We first introduce the basic formal notions of learning theory and basic epistemic logic. We provide a translation of the components of learning scenarios into the domain of epistemic logic. Then, we propose a characterization of finite identifiability in an epistemic temporal language. In the end we discuss consequences and possible extensions of our work. (shrink)

This paper discusses the possibility of modelling inductive inference (Gold 1967) in dynamic epistemic logic (see e.g. van Ditmarsch et al. 2007). The general purpose is to propose a semantic basis for designing a modal logic for learning in the limit. First, we analyze a variety of epistemological notions involved in identification in the limit and match it with traditional epistemic and doxastic logic approaches. Then, we provide a comparison of learning by erasing (Lange et (...) al. 1996) and iterated epistemic update (Baltag and Moss 2004) as analyzed in dynamic epistemic logic. We show that finite identification can be modelled in dynamic epistemic logic, and that the elimination process of learning by erasing can be seen as iterated belief-revision modelled in dynamic doxastic logic. Finally, we propose viewing hypothesis spaces as temporal frames and discuss possible advantages of that perspective. (shrink)

Security properties naturally combine temporal aspects of protocols with aspects of knowledge of the agents. Since BAN-logic, there have been several initiatives and attempts to incorpórate epistemics into the analysis of security protocols. In this paper, we give an overview of work in the field and present it in a unified perspective, with comparisons on technical subtleties that have been employed in different approaches. Also, we study to which degree the use of epistemics is essential for the analysis (...) of security protocols. We look for formal conditions under which knowledge modalities can bring extra expressive power to pure temporal languages. On the other hand, we discuss the cost of the epistemic operators in terms of model checking complexity. (shrink)

A recurring issue in any formal model representing agents' (changing) informational attitudes is how to account for the fact that the agents are limited in their access to the available inference steps, possible observations and available messages. This may be because the agents are not logically omniscient and so do not have unlimited reasoning ability. But it can also be because the agents are following a predefined protocol that explicitly limits statements available for observation and/or communication. Within the broad literature (...) on epistemic logic, there are a variety of accounts that make precise a notion of an agent's "limited access" (for example, Awareness Logics, Justification Logics, and Inference Logics). This paper interprets the agents' access set of formulas as a constraint on the agents' information gathering process limiting which formulas can be observed. (shrink)

In the literature, different axiomatizations of Public Announcement Logic (PAL) have been proposed. Most of these axiomatizations share a “core set” of the so-called “reduction axioms”. In this paper, by designing non-standard Kripke semantics for the language of PAL, we show that the proof system based on this core set of axioms does not completely axiomatize PAL without additional axioms and rules. In fact, many of the intuitive axioms and rules we took for granted could not be derived from (...) the core set. Moreover, we also propose and advocate an alternative yet meaningful axiomatization of PAL without the reduction axioms. The completeness is proved directly by a detour method using the canonical model where announcements are treated as merely labels for modalities as in normal modal logics. This new axiomatization and its completeness proof may sharpen our understanding of PAL and can be adapted to other dynamic epistemic logics. (shrink)

Modal logics, originally conceived in philosophy, have recently found many applications in computer science, artificial intelligence, the foundations of mathematics, linguistics and other disciplines. Celebrated for their good computational behaviour, modal logics are used as effective formalisms for talking about time, space, knowledge, beliefs, actions, obligations, provability, etc. However, the nice computational properties can drastically change if we combine some of these formalisms into a many-dimensional system, say, to reason about knowledge bases developing in time or moving objects. To study (...) the computational behaviour of many-dimensional modal logics is the main aim of this book. On the one hand, it is concerned with providing a solid mathematical foundation for this discipline, while on the other hand, it shows that many seemingly different applied many-dimensional systems (e.g., multi-agent systems, description logics with epistemic, temporal and dynamic operators, spatio-temporal logics, etc.) fit in perfectly with this theoretical framework, and so their computational behaviour can be analyzed using the developed machinery. We start with concrete examples of applied one- and many-dimensional modal logics such as temporal, epistemic, dynamic, description, spatial logics, and various combinations of these. Then we develop a mathematical theory for handling a spectrum of 'abstract' combinations of modal logics - fusions and products of modal logics, fragments of first-order modal and temporal logics - focusing on three major problems: decidability, axiomatizability, and computational complexity. Besides the standard methods of modal logic, the technical toolkit includes the method of quasimodels, mosaics, tilings, reductions to monadic second-order logic, algebraic logic techniques. Finally, we apply the developed machinery and obtained results to three case studies from the field of knowledge representation and reasoning: temporal epistemic logics for reasoning about multi-agent systems, modalized description logics for dynamic ontologies, and spatio-temporal logics. The genre of the book can be defined as a research monograph. It brings the reader to the front line of current research in the field by showing both recent achievements and directions of future investigations (in particular, multiple open problems). On the other hand, well-known results from modal and first-order logic are formulated without proofs and supplied with references to accessible sources. The intended audience of this book is logicians as well as those researchers who use logic in computer science and artificial intelligence. More specific application areas are, e.g., knowledge representation and reasoning, in particular, terminological, temporal and spatial reasoning, or reasoning about agents. And we also believe that researchers from certain other disciplines, say, temporal and spatial databases or geographical information systems, will benefit from this book as well. Key Features: Integrated approach to modern modal and temporal logics and their applications in artificial intelligence and computer science Written by internationally leading researchers in the field of pure and applied logic Combines mathematical theory of modal logic and applications in artificial intelligence and computer science Numerous open problems for further research Well illustrated with pictures and tables. (shrink)

In the “Second Analogy,” Kant argues that, unless mental contents involve the concept of causation, they cannot represent an objective temporal sequence. According to Kant, deploying the concept of causation renders a certain temporal ordering of representations necessary, thus enabling objective representational purport. One exegetical question that remains controversial is this: how, and in what sense, does deploying the concept of cause render a certain ordering of representations necessary? I argue that this necessitation is a matter of (...) class='Hi'>epistemic normativity: with certain causal presuppositions in place, the individual is obliged to make a judgment with certain temporal contents, on pain of irrationality. To make this normatively obligatory judgment, the subject must place her perceptual representations in a certain order. This interpretation fits Kant's text, his argumentative aims, and his broader views about causal inference, better than rival interpretations can. This result has important consequences for the ongoing debate over the role of normativity in Kant's philosophy of mind. (shrink)

Logics of joint strategic ability have recently received attention, with arguably the most influential being those in a family that includes Coalition Logic (CL) and Alternating-time Temporal Logic (ATL). Notably, both CL and ATL bypass the epistemic issues that underpin Schelling-type coordination problems, by apparently relying on the meta-level assumption of (perfectly reliable) communication between cooperating rational agents. Yet such epistemic issues arise naturally in settings relevant to ATL and CL: these logics are standardly interpreted (...) on structures where agents move simultaneously, opening the possibility that an agent cannot foresee the concurrent choices of other agents. In this paper we introduce a variant of CL we call Two-Player Strategic Coordination Logic (SCL2). The key novelty of this framework is an operator for capturing coalitional ability when the cooperating agents cannot share strategic information. We identify significant differences in the expressive power and validities of SCL2 and CL2, and present a sound and complete axiomatization for SCL2. We briefly address conceptual challenges when shifting attention to games with more than two players and stronger notions of rationality. (shrink)

In section 1 we argue that the adoption of a tenseless notion of truth entails a realistic view of propositions and provability. This view, in turn, opens the way to the intelligibility of theclassical meaning of the logical constants, and consequently is incompatible with the antirealism of orthodox intuitionism. In section 2 we show how what we call the potential intuitionistic meaning of the logical constants can be defined, on the one hand, by means of the notion of atemporal provability (...) and, on the other, by means of the operator K of epistemic logic. Intuitionistic logic, as reconstructed within this perspective, turns out to be a part of epistemic logic, so that it loses its traditional foundational role, antithetic to that of classical logic. In section 3 we uphold the view that certain consequences of the adoption of atemporal notion of truth, despite their apparent oddity, are quite acceptable from an antirealist point of view. (shrink)

Modal logic is the logic of necessity and possibility, of ‘must be’ and ‘may be’. These may be interpreted in various ways. If necessity is necessary truth, there is alethic modal logic; if it is moral or normative necessity, there is deontic logic [see chapter 8]. It may refer to what is known or believed to be true, in which case, there is an epistemic logic [chapter 9], or to what always has been or (...) to what henceforth always will be true, which gives an aspect of temporal logic [chapter 10]. Another interpretation is to read ‘Necessarily p′ as ‘it is provable that p′ This chapter will present the general framework of modal logic applicable to all of these, though with emphasis on alethic modal logics. (shrink)

A variety of logical frameworks have been developed to study rational agents interacting over time. This paper takes a closer look at one particular interface, between two systems that both address the dynamics of knowledge and information flow. The first is Epistemic Temporal Logic (ETL) which uses linear or branching time models with added epistemic structure induced by agents’ different capabilities for observing events. The second framework is Dynamic Epistemic Logic (DEL) that describes interactive (...) processes in terms of epistemic event models which may occur inside modalities of the language. This paper systematically and rigorously relates the DEL framework with the ETL framework. The precise relationship between DEL and ETL is explored via a new representation theorem characterizing the largest class of ETL models corresponding to DEL protocols in terms of notions of Perfect Recall , No Miracles , and Bisimulation Invariance . We then focus on new issues of completeness . One contribution is an axiomatization for the dynamic logic of public announcements constrained by protocols, which has been an open problem for some years, as it does not fit the usual ‘reduction axiom’ format of DEL. Finally, we provide a number of examples that show how DEL suggests an interesting fine-structure inside ETL. (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)

In this paper, we continued the preparatory works of Jingde Cheng in conjunction with spatio-temporal relevant logics, and proposed several epistemic spatio-temporal relevant logics as basic logics for Mobile Multi-Agent Systems (MMAS). To establish an inference system, important elements are: semantics and syntax appropriate to it include a language, axioms and inference rules. By proving the meta-logical properties such as soundness and consistency, completeness and decidability and etc., we have a method to test the reliability of the (...) systems. Finally, we will have models and algorithms for the application of these logics in the MMAS. (shrink)

We present the logic $${\mathsf {LCB}}$$ LCB which is expressed in a propositional language constantly enriched by new atomic expressions. Our formal framework is the propositional doxastic logic $${\mathsf {KD45}}$$ KD 45 with the belief operator $${\mathcal {B}}$$ B, extended by the $${\mathcal {C}}$$ C operator, to be read it changes that.... We describe the changing beliefs of an agent who uses progressively expanding language. The approach presented here allows us to weaken pragmatic objections to the so-called principle (...) of negative retrospection accepted in $${\mathsf {KD45}}$$ KD 45 and the problem of logical omniscience. In what follows, we present the expanding propositional language used in our formalism, interpreted using an epistemic version of Kripke semantics. Next, we give a syntactic characterization of logic $${\mathsf {LCB}}$$ LCB and prove the soundness and completeness of $${\mathsf {LCB}}$$ LCB in respect to our semantics. Finally, we compare the idea of expanding language with the notion of agent awareness and we relate our formalism to two epistemic temporal logics. (shrink)

We present the propositional logic LEC for the two epistemic modalities of current and stable knowledge used by an agent who system-atically enriches his language. A change in the linguistic resources of an agent as a result of certain cognitive processes is something that commonly happens. Our system is based on the logic LC intended to formalize the idea that the occurrence of changes induces the passage of time. Here, the primitive operator C read as: it changes (...) that, defines the temporal succession of states of the world. The notion of current knowledge concerns variable components of the world and it may change over time. We represent it by the primitive operator k read as: the agent currently knows that, and assume that it has S5 properties. The second type of knowledge, symbolized by the primitive operator K read as: the agent stably knows that, relates to constant components of the world and it does not change. As a result of the axiomatic entanglement of C, K and k we show that stable knowledge satisfies axioms of S4.3. K and k modalities are not mutually definable, stable knowledge implies the current one and if the latter never changes, then it comes to be stable. The combination of K and k with the idea of an expanding language allows questioning of the so-called perfect recall principle. It cannot be maintained for both types of knowledge just because of changes in the vocabulary of the agent and possibly the growing spectrum of possible states of the world. We interpret LEC in the semantics of histories of epistemic changes and show that it is complete. Finally, we compare our logic with selected epistemic logics based on the concept of linear discrete time. (shrink)