{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T12:07:34Z","timestamp":1775736454982,"version":"3.50.1"},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2011,6,8]],"date-time":"2011-06-08T00:00:00Z","timestamp":1307491200000},"content-version":"unspecified","delay-in-days":7,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Review of Symbolic Logic"],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:p>We investigate the expressive power of <jats:italic>memory logics<\/jats:italic>. These are modal logics extended with the possibility to store (or remove) the current node of evaluation in (or from) a <jats:italic>memory<\/jats:italic>, and to perform membership tests on the current memory. From this perspective, the hybrid logic <jats:italic>\u210b\u2112<\/jats:italic> (\u2193), 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.<\/jats:p><jats:p>This work focuses in the case where the memory is a <jats:italic>set<\/jats:italic>, 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 <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S1755020310000389_inline1\"><jats:alt-text>${\\cal K}$<\/jats:alt-text><\/jats:inline-graphic> and <jats:italic>\u210b\u2112<\/jats:italic> (\u2193). 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.<\/jats:p>","DOI":"10.1017\/s1755020310000389","type":"journal-article","created":{"date-parts":[[2011,6,8]],"date-time":"2011-06-08T10:42:52Z","timestamp":1307529772000},"page":"290-318","source":"Crossref","is-referenced-by-count":21,"title":["THE EXPRESSIVE POWER OF MEMORY LOGICS"],"prefix":"10.1017","volume":"4","author":[{"given":"CARLOS","family":"ARECES","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DIEGO","family":"FIGUEIRA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SANTIAGO","family":"FIGUEIRA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SERGIO","family":"MERA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,6,8]]},"reference":[{"key":"S1755020310000389_ref9","first-page":"16","volume-title":"Proceedings of LFCS 2009, Vol. 5407 of LNCS","author":"Areces","year":"2009"},{"key":"S1755020310000389_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/227595.227602"},{"key":"S1755020310000389_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1024"},{"key":"S1755020310000389_ref5","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/8.5.653"},{"key":"S1755020310000389_ref10","first-page":"821","volume-title":"Handbook of Modal Logics","author":"Areces","year":"2006"},{"key":"S1755020310000389_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90102-X"},{"key":"S1755020310000389_ref6","doi-asserted-by":"publisher","DOI":"10.2307\/2695090"},{"key":"S1755020310000389_ref30","unstructured":"Schneider T. (2007). The complexity of hybrid logics over restricted classes of frames. PhD thesis, University of Jena."},{"key":"S1755020310000389_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02716-1_5"},{"key":"S1755020310000389_ref7","first-page":"56","volume-title":"Logic, Language, Information and Computation, Vol. 5110 of Lecture Notes in Computer Science","author":"Areces","year":"2008"},{"key":"S1755020310000389_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF00628304"},{"key":"S1755020310000389_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32254-2_16"},{"key":"S1755020310000389_ref3","first-page":"164","volume-title":"Journal of the ACM","author":"Alur","year":"1989"},{"key":"S1755020310000389_ref4","first-page":"15","volume-title":"Proceedings of LogKCA-07, San Sebastian, Spain","author":"Areces","year":"2007"},{"key":"S1755020310000389_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107050884"},{"key":"S1755020310000389_ref17","first-page":"19","volume-title":"Proceedings of the American Mathematical Society Symposia on Applied Mathematics","volume":"19","author":"Floyd","year":"1967"},{"key":"S1755020310000389_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59207-2"},{"key":"S1755020310000389_ref26","first-page":"587","volume-title":"Proceedings 34th International Symposium on Mathematical Foundations of Computer Science (MFCS), Vol. 5734 of LNCS","author":"Meier","year":"2009"},{"key":"S1755020310000389_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01049415"},{"key":"S1755020310000389_ref16","volume-title":"Mathematical Logic","author":"Ebbinghaus","year":"1984"},{"key":"S1755020310000389_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0018433"},{"key":"S1755020310000389_ref18","unstructured":"Gerbrandy J. (1999). Bisimulations on Planet Kripke. PhD Thesis, University of Amsterdam. ILLC Dissertation series DS-1999-01."},{"key":"S1755020310000389_ref22","first-page":"402","volume-title":"Proceedings of LICS\u201990","author":"Harel","year":"1990"},{"key":"S1755020310000389_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93429"},{"key":"S1755020310000389_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/363235.363259"},{"key":"S1755020310000389_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01995674"},{"key":"S1755020310000389_ref28","first-page":"188","volume-title":"Proceedings of the 20th IEEE Symposium of Logic in Computer Science (LICS 2005)","author":"Ouaknine","year":"2005"},{"key":"S1755020310000389_ref29","first-page":"201","volume-title":"4th International Symposium on Methodologies for Intelligent Systems","author":"Plaza","year":"1989"},{"key":"S1755020310000389_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.04.006"},{"key":"S1755020310000389_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-5839-4"},{"key":"S1755020310000389_ref27","unstructured":"Mera S. (2009). Modal memory logics. PhD thesis, Universidad de Buenos Aires and Universit\u00e9 Henri Poincar\u00e9."},{"key":"S1755020310000389_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-6259-0_10"},{"key":"S1755020310000389_ref14","volume-title":"Handbook of Modal Logics","author":"Blackburn","year":"2006"},{"key":"S1755020310000389_ref31","first-page":"51","volume-title":"TARK\u201901: Proceedings of the 8th Conference on Theoretical Aspects of Rationality and Knowledge","author":"van Benthem","year":"2001"}],"container-title":["The Review of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1755020310000389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T08:30:54Z","timestamp":1556353854000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1755020310000389\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["S1755020310000389"],"URL":"https:\/\/doi.org\/10.1017\/s1755020310000389","relation":{},"ISSN":["1755-0203","1755-0211"],"issn-type":[{"value":"1755-0203","type":"print"},{"value":"1755-0211","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6]]}}}