We introduce Arbitrary Public Announcement Logic with Memory (APALM), obtained by adding to the models a ‘memory’ of the initial states, representing the information before any communication took place (“the prior”), and adding to the syntax operators that can access this memory. We show that APALM is recursively axiomatizable (in contrast to the original Arbitrary Public Announcement Logic, for which the corresponding question is still open). We present a complete recursive axiomatization, that includes a natural finitary rule, and study this (...) logic’s expressivity and the appropriate notion of bisimulation. We then examine Group Announcement Logic with Memory (GALM), the extension of APALM obtained by adding to its syntax group announcement operators, and provide a complete finitary axiomatization (again in contrast to the original Group Announcement Logic, for which the only known axiomatization is infinitary). We also show that, in the memory-enhanced context, there is a natural reduction of the so-called coalition announcement modality to group announcements (in contrast to the memory-free case, where this natural translation was shown to be invalid). (shrink)

We propose a multi-agent logic of knowledge, public announcements and arbitrary announcements, interpreted on topological spaces in the style of subset space semantics. The arbitrary announcement modality functions similarly to the effort modality in subset space logics, however, it comes with intuitive and semantic differences. We provide axiomatizations for three logics based on this setting, with S5 knowledge modality, and demonstrate their completeness. We moreover consider the weaker axiomatizations of three logics with S4 type of knowledge and prove soundness and (...) completeness results for these systems. (shrink)

In this work we define contingency logic with arbitrary announcement. In contingency logic, the primitive modality contingency formalises that a proposition may be true but also may be false, so that if it is non-contingent then it is necessarily true or necessarily false. To this logic one can add dynamic operators to describe change of contingency. Our logic has operators for public announcement and operators for arbitrary public announcement, as in the dynamic epistemic logic called arbitrary public announcement logic. However, (...) our language primitive is the more suitable notion of public announcement whether, instead of the public announcement that. We compare the expressive power of our logic and its various fragments to related dynamic epistemic logics. We further present an axiomatisation and show its completeness by adapting a method to demonstrate completeness of arbitrary public announcement logic. Various extensions are also shown to be complete with respect to the corresponding frame classes. (shrink)

We propose a multi-agent logic of knowledge, public announcements and arbitrary announcements, interpreted on topological spaces in the style of subset space semantics. The arbitrary announcement modality functions similarly to the effort modality in subset space logics, however, it comes with intuitive and semantic differences. We provide axiomatizations for three logics based on this setting, with S5 knowledge modality, and demonstrate their completeness. We moreover consider the weaker axiomatizations of three logics with S4 type of knowledge and prove soundness and (...) completeness results for these systems. (shrink)

A true lie is a lie that becomes true when announced. In a logic of announcements, where the announcing agent is not modelled, a true lie is a formula that becomes true when announced. We investigate true lies and other types of interaction between announced formulas, their preconditions and their postconditions, in the setting of Gerbrandy’s logic of believed announcements, wherein agents may have or obtain incorrect beliefs. Our results are on the satisfiability and validity of instantiations of these semantically (...) defined categories, on iterated announcements, including arbitrarily often iterated announcements, and on syntactic characterization. We close with results for iterated announcements in the logic of knowledge, and for lying as private announcements to different agents. Detailed examples illustrate our lying concepts. (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)

This chapter presents a new semantics for inductive empirical knowledge. The epistemic agent is represented concretely as a learner who processes new inputs through time and who forms new beliefs from those inputs by means of a concrete, computable learning program. The agent’s belief state is represented hyper-intensionally as a set of time-indexed sentences. Knowledge is interpreted as avoidance of error in the limit and as having converged to true belief from the present time onward. Familiar topics are re-examined within (...) the semantics, such as inductive skepticism, the logic of discovery, Duhem’s problem, the articulation of theories by auxiliary hypotheses, the role of serendipity in scientific knowledge, Fitch’s paradox, deductive closure of knowability, whether one can know inductively that one knows inductively, whether one can know inductively that one does not know inductively, and whether expert instruction can spread common inductive knowledge—as opposed to mere, true belief—through a community of gullible pupils. (shrink)