Characterizing frame definability in team semantics via the universal modality

DOI10.1007/978-3-662-47709-0_11zbMATH Open1471.03050arXiv1502.07884OpenAlexW2963584125MaRDI QIDQ2273015FDOQ2273015

Authors: Katsuhiko Sano, Jonni Virtema 

Publication date: 18 September 2019

Published in: Annals of Pure and Applied Logic, Logic, Language, Information, and Computation (Search for Journal in Brave)

Abstract: We study model and frame definability of various modal logics. Let ML(A+) denote the fragment of modal logic extended with the universal modality in which the universal modality occurs only positively. We show that a class of Kripke models is definable in ML(A+) if and only if the class is elementary and closed under disjoint unions and surjective bisimulations. We also characterise the definability of ML(A+) in the spirit of the well-known Goldblatt--Thomason theorem. We show that an elementary class F of Kripke frames is definable in ML(A+) if and only if F is closed under taking generated subframes and bounded morphic images, and reflects ultrafilter extensions and finitely generated subframes. In addition we study frame definability relative to finite transitive frames and give an analogous characterisation of ML(A+)-definability relative to finite transitive frames. Finally, we initiate the study of model and frame definability in team-based logics. We study (extended) modal dependence logic, (extended) modal inclusion logic, and modal team logic. We establish strict linear hierarchies with respect to model definability and frame definability, respectively. We show that, with respect to model and frame definability, the before mentioned team-based logics, except modal dependence logic, either coincide with ML(A+) or plain modal logic ML. Thus as a corollary we obtain model theoretic characterisation of model and frame definability for the team-based logics.

Full work available at URL: https://arxiv.org/abs/1502.07884

Recommendations

• Characterizing relative frame definability in team semantics via the universal modality
• Characterizing frame definability in team semantics via the universal modality
• First-order modal logic: frame definability and a Lindström theorem
• The expressive power of modal dependence logic
• Existential definability of modal frame classes

zbMATH Keywords

team semanticsmodal logicuniversal modalityframe definabilitymodel definability

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45)

Cites Work

• Dependence and independence
• A finite axiomatization of conditional independence and inclusion dependencies
• Dependence logic. A new approach to independence friendly logic
• Reasoning about embedded dependencies using inclusion dependencies
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Modal logic
• Title not available (Why is that?)
• Algebraic laws for nondeterminism and concurrency
• Using the Universal Modality: Gains and Questions
• On the finite and general implication problems of independence atoms and keys
• Handbook of modal logic
• Model theory.
• Complexity results for modal dependence logic
• Extended modal dependence logic \(\mathcal{EMDL}\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Modal dependence logic
• The Expressive Power of Modal Dependence Logic
• Model checking for modal intuitionistic dependence logic
• Title not available (Why is that?)
• Axiomatizing propositional dependence logics
• Interpolation for extended modal languages
• Model-theoretic and computational properties of modal dependence logic
• Modal logic with names
• Characterizing frame definability in team semantics via the universal modality
• Model checking for modal dependence logic: an approach through Post's lattice
• Modal independence logic:
• Complexity of validity for propositional dependence logics
• A Van Benthem Theorem for Modal Team Semantics
• The expressive power of modal logic with inclusion atoms
• Title not available (Why is that?)
• Some characterization and preservation theorems in modal logic
• Notes on modal definability
• Goldblatt-Thomason-style theorems for graded modal language
• Expressivity and Complexity of Dependence Logic
• Characterizing relative frame definability in team semantics via the universal modality
• Title not available (Why is that?)
• A generalization of modal frame definability
• Dependence logic vs. constraint satisfaction

Cited In (8)

• Title not available (Why is that?)
• Characterizing frame definability in team semantics via the universal modality
• Questions and dependency in intuitionistic logic
• Characterizing relative frame definability in team semantics via the universal modality
• On definability of team relations with \(k\)-invariant atoms
• Model Checking and Validity in Propositional and Modal Inclusion Logics
• A Van Benthem Theorem for Modal Team Semantics
• Complexity of validity for propositional dependence logics

This page was built for publication: Characterizing frame definability in team semantics via the universal modality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2273015)