Review of Symbolic Logic:1-28 (forthcoming)

Johan Van Benthem
University of Amsterdam
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 (MLSR) and its corresponding removal modality, we analyze its expressive power and prove a bisimulation characterization theorem. We then provide a complete Hillbert-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 MLSR 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.
Keywords dynamic logic  logics for graph games  complexity and decidability
Categories (categorize this paper)
DOI 10.1017/s1755020320000258
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 65,740
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Modal Logic.Johan van Benthem - 2015 - Internet Encyclopedia of Philosophy.
What One May Come to Know.van Benthem Johan - 2004 - Analysis 64 (2):95–105.
Modal Logic for Open Minds.Johan F. A. K. van Benthem - 2010 - Stanford, CA, USA: Center for the Study of Language and Information.
Modal Logic for Open Minds -.Johan F. A. K. van Benthem - 2010 - Stanford, CA, USA: Center for the Study of Language and Inf.
Modal Logic in Two Gestalts.Johan van Benthem - 2000 - In Michael Zakharyaschev, Krister Segerberg, Maarten de Rijke & Heinrich Wansing (eds.), Advances in Modal Logic, Volume 2. CSLI Publications. pp. 91-118.
Modal Logic in Two Gestalts.Johan van Benthem - 2000 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 91-118.
Suhrawardi's Modal Syllogisms.Zia Movahed - 2012 - Sophia Perennis 21:5-17.
A New Modal Lindström Theorem.Johan van Benthem - 2007 - Logica Universalis 1 (1):125-138.


Added to PP index

Total views
9 ( #933,746 of 2,462,895 )

Recent downloads (6 months)
2 ( #299,108 of 2,462,895 )

How can I increase my downloads?


My notes