On the Modal Definability of Simulability by Finite Transitive Models

Studia Logica 98 (3):347-373 (2011)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 92,873

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Modal logic over finite structures.Eric Rosen - 1997 - Journal of Logic, Language and Information 6 (4):427-439.
Classical and Intuitionistic Models of Arithmetic.Kai F. Wehmeier - 1996 - Notre Dame Journal of Formal Logic 37 (3):452-461.
Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
Logics for classes of Boolean monoids.Gerard Allwein, Hilmi Demir & Lee Pike - 2004 - Journal of Logic, Language and Information 13 (3):241-266.
Finite h-dimension does not imply expressive completeness.Ian Hodkinson - 1994 - Journal of Philosophical Logic 23 (5):535 - 573.
Quasi-modal equivalence of canonical structures.Robert Goldblatt - 2001 - Journal of Symbolic Logic 66 (2):497-508.


Added to PP

21 (#758,365)

6 months
5 (#703,368)

Historical graph of downloads
How can I increase my downloads?