The expressive power of modal logic with inclusion atoms

MaRDI QIDQ5013883zbMATH OpenFDO

Authors Lauri Hella, Johanna Beate Stumpf

Publication date 3 December 2021

Full work available at URL https://arxiv.org/abs/1509.07204, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF2015.10

Mathematics Subject Classification ID

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

Abstract: Modal inclusion logic is the extension of basic modal logic with inclusion atoms, and its semantics is defined on Kripke models with teams. A team of a Kripke model is just a subset of its domain. In this paper we give a complete characterisation for the expressive power of modal inclusion logic: a class of Kripke models with teams is definable in modal inclusion logic if and only if it is closed under k-bisimulation for some integer k, it is closed under unions, and it has the empty team property. We also prove that the same expressive power can be obtained by adding a single unary nonemptiness operator to modal logic. Furthermore, we establish an exponential lower bound for the size of the translation from modal inclusion logic to modal logic with the nonemptiness operator.

Recommendations

• The expressive power of modal dependence logic
• Model checking and validity in propositional and modal inclusion logics
• scientific article; zbMATH DE number 6680142

Cites work

• Boolean dependence logic and partially-ordered connectives
• Complexity of model checking for modal dependence logic
• Complexity of validity for propositional dependence logics
• Complexity results for modal dependence logic
• Compositional semantics for a language of imperfect information
• Dependence logic. A new approach to independence friendly logic
• Extended modal dependence logic \(\mathcal{EMDL}\)
• Handbook of modal logic
• scientific article; zbMATH DE number 4118333 (Why is no real title available?)
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Modal dependence logic
• Modal inclusion logic: being lax is simpler than being strict
• Modal indepence logic
• Modal logic
• Model-theoretic and computational properties of modal dependence logic
• The expressive power of modal dependence logic

Cited in

(16)

• Capturing \(k\)-ary existential second order logic with \(k\)-ary inclusion-exclusion logic
• Propositional union closed team logics
• On definability of team relations with \(k\)-invariant atoms
• Axiomatizations of team logics
• The expressive power of modal dependence logic
• Canonical models and the complexity of modal team logic
• Model checking and validity in propositional and modal inclusion logics
• Expressivity and Complexity of Dependence Logic
• On the succinctness of atoms of dependency
• Propositional team logics
• scientific article; zbMATH DE number 7056228 (Why is no real title available?)
• Parameterized complexity of propositional inclusion and independence logic
• Dimension in team semantics
• Inclusion with repetitions and Boolean constants -- implication problems revisited
• Axiomatizing modal inclusion logic and its variants
• State-based modal logics for free choice

This page was built for publication: The expressive power of modal logic with inclusion atoms

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