{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:42:35Z","timestamp":1775839355507,"version":"3.50.1"},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2020,7,21]],"date-time":"2020-07-21T00:00:00Z","timestamp":1595289600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["The Review of Symbolic Logic"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the modal logic of stepwise removal of objects, both for its intrinsic interest as a logic of quantification without replacement, and as a pilot study to better understand the complexity jumps between dynamic epistemic logics of model transformations and logics of freely chosen graph changes that get registered in a growing memory. After introducing this logic (<jats:sans-serif>MLSR<\/jats:sans-serif>) and its corresponding removal modality, we analyze its expressive power and prove a bisimulation characterization theorem. We then provide a complete Hilbert-style axiomatization for the logic of stepwise removal in a hybrid language enriched with nominals and public announcement operators. Next, we show that model-checking for <jats:sans-serif>MLSR<\/jats:sans-serif> is PSPACE-complete, while its satisfiability problem is undecidable. Lastly, we consider an issue of fine-structure: the expressive power gained by adding the stepwise removal modality to fragments of first-order logic.<\/jats:p>","DOI":"10.1017\/s1755020320000258","type":"journal-article","created":{"date-parts":[[2020,7,21]],"date-time":"2020-07-21T03:57:19Z","timestamp":1595303839000},"page":"36-63","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":17,"title":["THE MODAL LOGIC OF STEPWISE REMOVAL"],"prefix":"10.1017","volume":"15","author":[{"given":"JOHAN","family":"VAN BENTHEM","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KRZYSZTOF","family":"MIERZEWSKI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FRANCESCA","family":"ZAFFORA BLANDO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,7,21]]},"reference":[{"key":"S1755020320000258_r10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41389-6_2"},{"key":"S1755020320000258_r2","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/jzv020"},{"key":"S1755020320000258_r7","volume-title":"Modal Logic","author":"Blackburn","year":"2011"},{"key":"S1755020320000258_r5","first-page":"821","volume-title":"Handbook of Modal Logic","author":"Areces","year":"2006"},{"key":"S1755020320000258_r14","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806724"},{"key":"S1755020320000258_r21","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L. J. , & Meyer, A. R. (1973). Word problems requiring exponential time. Proceedings of the 5th ACM Symposium on Theory of Computing, STOC \u201973, pp. 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"S1755020320000258_r26","doi-asserted-by":"publisher","DOI":"10.1007\/s10992-008-9099-x"},{"key":"S1755020320000258_r11","first-page":"33","volume-title":"International Workshop on Hybrid Logic and Applications 2010","author":"Hansen","year":"2011"},{"key":"S1755020320000258_r17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45138-9_47"},{"key":"S1755020320000258_r13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"S1755020320000258_r20","unstructured":"Rohde, P. (2005). On games and logics over dynamically changing structures. Ph.D. Dissertation, RWTH Aachen University (Germany), pp. 1\u2013216."},{"key":"S1755020320000258_r24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974533"},{"key":"S1755020320000258_r1","first-page":"307","volume-title":"The Life and Work of Leon Henkin","author":"Andr\u00e9ka","year":"2016"},{"key":"S1755020320000258_r3","first-page":"56","volume-title":"Logic, Language, Information and Computation, WoLLIC 2008","author":"Areces","year":"2008"},{"key":"S1755020320000258_r9","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-15-2221-5_1"},{"key":"S1755020320000258_r25","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-15-2221-5_7"},{"key":"S1755020320000258_r22","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-15-2221-5_5"},{"key":"S1755020320000258_r23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32254-2_16"},{"key":"S1755020320000258_r15","doi-asserted-by":"publisher","DOI":"10.2307\/2586754"},{"key":"S1755020320000258_r6","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exx034"},{"key":"S1755020320000258_r19","first-page":"197","volume-title":"Logical Perspectives on Language and Information","author":"de Lavalette","year":"2001"},{"key":"S1755020320000258_r12","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044481714-3\/50009-6"},{"key":"S1755020320000258_r18","first-page":"139","volume-title":"Handbook of Modal Logic","author":"Marx","year":"2006"},{"key":"S1755020320000258_r16","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exz036"}],"container-title":["The Review of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1755020320000258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T13:00:34Z","timestamp":1648558834000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1755020320000258\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,21]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["S1755020320000258"],"URL":"https:\/\/doi.org\/10.1017\/s1755020320000258","relation":{},"ISSN":["1755-0203","1755-0211"],"issn-type":[{"value":"1755-0203","type":"print"},{"value":"1755-0211","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,21]]},"assertion":[{"value":"\u00a9 2020, Association for Symbolic Logic","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}