Completeness results for memory logics

Abstract. Memory logics are a family of modal logics in which standard relational structures are augmented with data structures and additional operations to modify and query these structures. In this paper we present sound and complete axiomatizations for some members of this family. We analyze the use of nominals to achieve completeness, and present one example in which they can be avoided. 1 Modal Logics with Memory Many attempts have been made in recent years to increase modal logic expres-sivity by adding some notion of state to standard relational structures. This is a natural need, since modal logics are used in many different scenarios as tools for modeling behavior. One example of how this can be achieved comes from epistemic logic with dy-namic operators, which allow to express the evolution of knowledge by knowledge-changing actions. Such logics are often called Dynamic Epistemic Logics (DEL) [16], and a large number of DELs has been proposed [9, 13–15]. Thes