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 | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,875 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesDavid Gabelaia, Agi Kurucz, Frank Wolter & Michael Zakharyaschev (2005). Products of 'Transitive' Modal Logics. Journal of Symbolic Logic 70 (3):993 - 1021.
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.
Marco Hollenberg (1998). Characterizations of Negative Definability in Modal Logic. Studia Logica 60 (3):357-386.
Wiesław Dziobiak (1981). Strong Completeness with Respect to Finite Kripke Models. Studia Logica 40 (3):249 - 252.
A. V. Chagrov & L. A. Chagrova (1995). Algorithmic Problems Concerning First-Order Definability of Modal Formulas on the Class of All Finite Frames. Studia Logica 55 (3):421 - 448.
M. Krynicki & K. Zdanowski (2005). Theories of Arithmetics in Finite Models. Journal of Symbolic Logic 70 (1):1-28.
Sergei Artemov & Giorgie Dzhaparidze (1990). Finite Kripke Models and Predicate Logics of Provability. Journal of Symbolic Logic 55 (3):1090-1098.
Holger Sturm & Frank Wolter (2001). First-Order Expressivity for S5-Models: Modal Vs. Two-Sorted Languages. Journal of Philosophical Logic 30 (6):571-591.
Gerard Allwein, Hilmi Demir & Lee Pike (2004). Logics for Classes of Boolean Monoids. Journal of Logic, Language and Information 13 (3):241-266.
Maciej Farulewski (2005). On Finite Models of the Lambek Calculus. Studia Logica 80 (1):63 - 74.
Vedran Čačić & Domagoj Vrgoč (2013). A Note on Bisimulation and Modal Equivalence in Provability Logic and Interpretability Logic. Studia Logica 101 (1):31-44.
Ian Hodkinson (1994). Finite H-Dimension Does Not Imply Expressive Completeness. Journal of Philosophical Logic 23 (5):535 - 573.
Hiroakira Ono & Akira Nakamura (1980). On the Size of Refutation Kripke Models for Some Linear Modal and Tense Logics. Studia Logica 39 (4):325 - 333.
Robert Goldblatt (2001). Quasi-Modal Equivalence of Canonical Structures. Journal of Symbolic Logic 66 (2):497-508.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2011-08-12Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
