Expressive Power and Decidability for Memory Logics

C. Areces, D. Figueira, S. Figueira, and S. Mera. Expressive Power and Decidability for Memory Logics. In Logic, Language, Information and Computation, Lecture Notes in Computer Science, pp. 56–68, Springer Berlin / Heidelberg, Edinburgh, Scotland, 2008. Proceedings of WoLLIC 2008

Download

[pdf] 

Abstract

Taking as inspiration the hybrid logic HL(\downarrow), we introduce a new family of logics that we call memory logics. In this article we present in detail two interesting members of this family defining their formal syntax and semantics. We then introduce a proper notion of bisimula- tion and investigate their expressive power (in comparison with modal and hybrid logics). We will prove that in terms of expressive power, the memory logics we discuss in this paper are more expressive than ortho- dox modal logic, but less expressive than HL(\downarrow). We also establish the undecidability of their satisfiability problems.

BibTeX

@InCollection{Areces2008a,
  author =       "C. Areces and D. Figueira and S. Figueira and S.
                 Mera",
  abstract =     "Taking as inspiration the hybrid logic HL(\downarrow),
                 we introduce a new family of logics that we call memory
                 logics. In this article we present in detail two
                 interesting members of this family defining their
                 formal syntax and semantics. We then introduce a proper
                 notion of bisimula- tion and investigate their
                 expressive power (in comparison with modal and hybrid
                 logics). We will prove that in terms of expressive
                 power, the memory logics we discuss in this paper are
                 more expressive than ortho- dox modal logic, but less
                 expressive than HL(\downarrow). We also establish the
                 undecidability of their satisfiability problems.",
  booktitle =    "Logic, Language, Information and Computation",
  publisher =    "Springer Berlin / Heidelberg",
  title =        "Expressive Power and Decidability for Memory Logics",
  year =         "2008",
  address =      "Edinburgh, Scotland",
  note =         "Proceedings of {W}o{LLIC} 2008",
  pages =        "56--68",
  series =       "Lecture Notes in Computer Science",
  volume =       "5110",
  editors =      "W. Hodges and R. de Queiroz",
  ISBN =         "978-3-540-69936-1",
}