Modal characterisation theorems over special classes of frames
The paper investigates model-theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance on specific classes of structures, analogous to van Benthem's theorem saying that a first-order formula is invariant under bisimulation if, and only if, it is equivalent to a formula of basic modal logic. In particular, the authors study 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, the authors develop and extend the game-based analysis (first-order Ehrenfeucht-Fraïssé versus bisimulation games) over such classes and provide bisimulation-preserving model constructions within these classes. Over most of the classes considered, they 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, it turns out that monadic second-order logic is no more expressive than first-order logic as far as bisimulation-invariant properties are concerned. The authors 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 logic for finite transitive frames.
- Bisimulation invariance and finite models
- Modal and guarded characterisation theorems over finite transition systems
- Bisimulation invariant monadic-second order logic in the finite
- Bisimulation Invariant Monadic-Second Order Logic in the Finite
- A Note on Bisimulation Quantifiers and Fixed Points over Transitive Frames
- scientific article; zbMATH DE number 3819693 (Why is no real title available?)
- scientific article; zbMATH DE number 3708351 (Why is no real title available?)
- scientific article; zbMATH DE number 1324669 (Why is no real title available?)
- scientific article; zbMATH DE number 612169 (Why is no real title available?)
- Modal and guarded characterisation theorems over finite transition systems
- Modal characterisation theorems over special classes of frames
- Modal languages and bounded fragments of predicate logic
- Modal logic
- Modal logic over finite structures
- On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
- Some modal aspects of XPath
- The modal -calculus hierarchy over restricted classes of transition systems
- Modal logic over finite structures
- The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs
- The finite model property for logics with the tangle modality
- Modal and guarded characterisation theorems over finite transition systems
- Basic logic, K4, and persistence
- A quantified coalgebraic van Benthem theorem
- On generalized van Benthem-type characterizations
- The monadic theory of finite representations of infinite words
- A general Lindström theorem for some normal modal logics
- Model theory of XPath on data trees. II: Binary bisimulation and definability
- Characterization, definability and separation via saturated models
- Semantical characterizations for irreflexive and generalized modal languages
- Some modal aspects of XPath
- On modal -calculus over finite graphs with small components or small tree width
- A sound and complete axiomatization for dynamic topological logic
- scientific article; zbMATH DE number 440120 (Why is no real title available?)
- Model theoretic methods for fragments of FO and special classes of (finite) structures
- Bisimulation in inquisitive modal logic
- A Note on Bisimulation Quantifiers and Fixed Points over Transitive Frames
- Modal frame characterization by way of auxiliary modalities
- The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
- INQUISITIVE BISIMULATION
- Complete intuitionistic temporal logics for topological dynamics
- Bisimulational categoricity
- scientific article; zbMATH DE number 7267340 (Why is no real title available?)
- A model-theoretic approach to descriptive general frames: the van Benthem characterization theorem
- Spatial logic of tangled closure operators and modal mu-calculus
- On expressive power of basic modal intuitionistic logic as a fragment of classical FOL
- The freedoms of (guarded) bisimulation
- Bisimulation invariance and finite models
- On the \(\mu \)-calculus over transitive and finite transitive frames
- Complexity of hybrid logics over transitive frames
- A correspondence theorem for interpretability logic with respect to Verbrugge semantics
- Characterizations of two basic hybrid logics
- A characterisation theorem for two-way bisimulation-invariant monadic least fixpoint logic over finite structures
- The topological mu-calculus: completeness and decidability
- Exponential lower bounds on definable fixed points
- Modal characterisation theorems over special classes of frames
- On the expressive power of inquisitive epistemic logic
- On the modal definability of simulability by finite transitive models
- Tangled modal logic for topological dynamics
This page was built for publication: Modal characterisation theorems over special classes of frames
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q732052)
