The expressive power of modal dependence logic

zbMATH Open1385.03018arXiv1406.6266MaRDI QIDQ4636299FDOQ4636299

Authors: Lauri Hella, Kerkko Luosto, Katsuhiko Sano, Jonni Virtema 

Publication date: 23 April 2018

Abstract: We study the expressive power of various modal logics with team semantics. We show that exactly the properties of teams that are downward closed and closed under team k-bisimulation, for some finite k, are definable in modal logic extended with intuitionistic disjunction. Furthermore, we show that the expressive power of modal logic with intuitionistic disjunction and extended modal dependence logic coincide. Finally we establish that any translation from extended modal dependence logic into modal logic with intuitionistic disjunction increases the size of some formulas exponentially.

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

Recommendations

• The expressive power of modal logic with inclusion atoms
• Model-theoretic and computational properties of modal dependence logic
• Modal dependence logics: axiomatizations and model-theoretic properties
• Modal dependence logic
• Complexity results for modal dependence logic

zbMATH Keywords

team semanticsbisimulationexpressive powermodal dependence logic

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Modal logic (including the logic of norms) (03B45)

Cited In (32)

• Expressivity and Complexity of Dependence Logic
• Diversity, dependence and independence
• Separation logics and modalities: a survey
• Propositional logics of dependence
• Modal indepence logic
• Modal independence logic
• Complexity Results for Modal Dependence Logic
• On definability in dependence logic
• The power of the filtration technique for modal logics with team semantics
• Canonical models and the complexity of modal team logic
• On temporal and separation logics
• Boolean dependence logic and partially-ordered connectives
• Positive modal logic beyond distributivity
• Uniform definability in propositional dependence logic
• Dimension in team semantics
• Dependency as question entailment
• Expressing second-order sentences in intuitionistic dependence logic
• Upwards closed dependencies in team semantics
• Structural completeness in propositional logics of dependence
• Title not available (Why is that?)
• Characterizing relative frame definability in team semantics via the universal modality
• Logics for propositional determinacy and independence
• On definability of team relations with \(k\)-invariant atoms
• Supervenience, dependence, disjunction
• Modal dependence logics: axiomatizations and model-theoretic properties
• On the succinctness of atoms of dependency
• Exemplaric Expressivity of Modal Logics
• The expressive power of modal logic with inclusion atoms
• On strongly first-order dependencies
• Title not available (Why is that?)
• Complexity of validity for propositional dependence logics
• Propositional team logics

This page was built for publication: The expressive power of modal dependence logic

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