On the Modal Definability of Simulability by Finite Transitive Models

Studia Logica 98 (3):347-373 (2011)
We show that given a finite, transitive and reflexive Kripke model 〈 W , ≼, ⟦ ⋅ ⟧ 〉 and $${w \in W}$$ , the property of being simulated by w (i.e., lying on the image of a literalpreserving relation satisfying the ‘forth’ condition of bisimulation) is modally undefinable within the class of S4 Kripke models. Note the contrast to the fact that lying in the image of w under a bi simulation is definable in the standard modal language even over the class of K4 models, a fairly standard result for which we also provide a proof. We then propose a minor extension of the language adding a sequent operator $${\natural}$$ (‘tangle’) which can be interpreted over Kripke models as well as over topological spaces. Over finite Kripke models it indicates the existence of clusters satisfying a specified set of formulas, very similar to an operator introduced by Dawar and Otto. In the extended language $${{\sf L}^+ = {\sf L}^{\square\natural}}$$ , being simulated by a point on a finite transitive Kripke model becomes definable, both over the class of (arbitrary) Kripke models and over the class of topological S4 models. As a consequence of this we obtain the result that any class of finite, transitive models over finitely many propositional variables which is closed under simulability is also definable in L + , as well as Boolean combinations of these classes. From this it follows that the μ -calculus interpreted over any such class of models is decidable
Keywords Simulation  bisimulation  modal logic  spatial logic  definability
Categories (categorize this paper)
DOI 10.1007/s11225-011-9339-x
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 23,674
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

View all 6 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles
Eric Rosen (1997). Modal Logic Over Finite Structures. Journal of Logic, Language and Information 6 (4):427-439.
Kai F. Wehmeier (1996). Classical and Intuitionistic Models of Arithmetic. Notre Dame Journal of Formal Logic 37 (3):452-461.
Gerard Allwein, Hilmi Demir & Lee Pike (2004). Logics for Classes of Boolean Monoids. Journal of Logic, Language and Information 13 (3):241-266.

Monthly downloads

Added to index


Total downloads

8 ( #467,114 of 1,903,042 )

Recent downloads (6 months)

2 ( #324,600 of 1,903,042 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.