On the Modal Definability of Simulability by Finite Transitive Models

Studia Logica 98 (3):347-373 (2011)
Abstract
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)
Options
 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: 9,351
External links
  • Through your library Configure
    References found in this work BETA

    View all 6 references

    Citations of this work BETA
    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.
    Analytics

    Monthly downloads

    Sorry, there are not enough data points to plot this chart.

    Added to index

    2011-08-12

    Total downloads

    0

    Recent downloads (6 months)

    0

    How can I increase my downloads?

    My notes
    Sign in to use this feature


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