@ARTICLE{arec:expr11,
author = {Areces, C. and Figueira, D. and Figueira, S. and Mera, S.},
title = {The Expressive Power of Memory Logics},
journal = {Review of Symbolic Logic},
year = {2011},
volume = {4},
pages = {290-318},
number = {2},
abstract = {We investigate the expressive power of memory logics. These are modal
logics extended with the possibility to store (or remove) the current
node of evaluation in (or from) a memory, and to perform membership
tests on the current memory. From this perspective, the hybrid logic
HL(\downarrow), for example, can be thought of as a particular case
of a memory logic where the memory is an indexed list of elements
of the domain.
This work focuses in the case where the memory is a set, and we can
test whether the current node belongs to the set or not. We prove
that, in terms of expressive power, the memory logics we discuss
here lie between the basic modal logic and HL(\downarrow). We show
that the satisfiability problem of most of the logics we cover is
undecidable. The only logic with a decidable satisfiability problem
is obtained by imposing strong constraints on which elements can
be memorized.},
doi = {10.1017/S1755020310000389},
eprint = {http://journals.cambridge.org/article_S1755020310000389},
publisher = {Cambridge University Press },
timestamp = {2010.09.23},
url = {http://dx.doi.org/10.1017/S1755020310000389}
}