Modal characterisation theorems over special classes of frames

Annals of Pure and Applied Logic 161 (1):1-42 (2010)
  Copy   BIBTEX

Abstract

We investigate model theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance. The paradigmatic result of this kind is van Benthem’s theorem, which says that a first-order formula is invariant under bisimulation if, and only if, it is equivalent to a formula of basic modal logic. The present investigation primarily concerns ramifications for specific classes of structures. We study in particular model classes defined through conditions on the underlying frames, with a focus on frame classes that play a major role in modal correspondence theory and often correspond to typical application domains of modal logics. Classical model theoretic arguments do not apply to many of the most interesting classes–for instance, rooted frames, finite rooted frames, finite transitive frames, well-founded transitive frames, finite equivalence frames–as these are not elementary. Instead we develop and extend the game-based analysis over such classes and provide bisimulation preserving model constructions within these classes. Over most of the classes considered, we obtain finite model theory analogues of the classically expected characterisations, with new proofs also for the classical setting. The class of transitive frames is a notable exception, with a marked difference between the classical and the finite model theory of bisimulation invariant first-order properties. Over the class of all finite transitive frames in particular, we find that monadic second-order logic is no more expressive than first-order as far as bisimulation invariant properties are concerned — though both are more expressive here than basic modal logic. We obtain ramifications of the de Jongh–Sambin theorem and a new and specific analogue of the Janin–Walukiewicz characterisation of bisimulation invariant monadic second-order for finite transitive frames

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,569

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 Sequents and Definability.Bruce M. Kapron - 1987 - Journal of Symbolic Logic 52 (3):756-762.
Models for Relevant Modal Logics.André Fuhrmann - 1990 - Studia Logica 49 (4):501 - 514.
Modal and Guarded Characterisation Theorems Over Finite Transition Systems.Martin Otto - 2004 - Annals of Pure and Applied Logic 130 (1-3):173-205.
Completeness and Definability in the Logic of Noncontingency.Evgeni E. Zolin - 1999 - Notre Dame Journal of Formal Logic 40 (4):533-547.
Derivation Rules as Anti-Axioms in Modal Logic.Yde Venema - 1993 - Journal of Symbolic Logic 58 (3):1003-1034.
General Frames for Relevant Modal Logics.Takahiro Seki - 2003 - Notre Dame Journal of Formal Logic 44 (2):93-109.
Elementary Classes in Basic Modal Logic.Holger Sturm - 2000 - Studia Logica 64 (2):193-213.
Hybrid Formulas and Elementarily Generated Modal Logics.Ian Hodkinson - 2006 - Notre Dame Journal of Formal Logic 47 (4):443-478.
Elementary Definability and Completeness in General and Positive Modal Logic.Ernst Zimmermann - 2003 - Journal of Logic, Language and Information 12 (1):99-117.
Speaking About Transitive Frames in Propositional Languages.Yasuhito Suzuki, Frank Wolter & Michael Zakharyaschev - 1998 - Journal of Logic, Language and Information 7 (3):317-339.

Analytics

Added to PP
2013-12-22

Downloads
15 (#692,992)

6 months
1 (#418,511)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Modal Logic Over Finite Structures.Eric Rosen - 1997 - Journal of Logic, Language and Information 6 (4):427-439.
Modal and Guarded Characterisation Theorems Over Finite Transition Systems.Martin Otto - 2004 - Annals of Pure and Applied Logic 130 (1-3):173-205.

Add more references