Expressive power and decidability for memory logics

Taking as inspiration the hybrid logic , 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 bisimulation and investigate their exp...

Descripción completa

Detalles Bibliográficos
Autores principales: Areces, C., Figueira, D., Figueira, S., Mera, S.
Formato: SER
Materias:
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v5110LNAI_n_p56_Areces
Aporte de:
Descripción
Sumario:Taking as inspiration the hybrid logic , 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 bisimulation 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 orthodox modal logic, but less expressive than . We also establish the undecidability of their satisfiability problems. © 2008 Springer-Verlag Berlin Heidelberg.