Hierarchies in independence logic

DOI10.4230/LIPICS.CSL.2013.263zbMATH Open1356.03070arXiv1304.4391OpenAlexW2964084990MaRDI QIDQ2958527FDOQ2958527

Miika Hannula, Juha Kontinen, Pietro Galliani

Publication date: 2 February 2017

Abstract: We study the expressive power of fragments of inclusion and independence logic defined either by restricting the number of universal quantifiers or the arity of inclusion and independence atoms in formulas. Assuming the so-called lax semantics for these logics, we relate these fragments of inclusion and independence logic to familiar sublogics of existential second-order logic. We also show that, with respect to the stronger strict semantics, inclusion logic is equivalent to existential second-order logic.

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

zbMATH Keywords

existential second-order logicindependence logicinclusion logicexpressiveness hierarchies

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Logic in computer science (03B70)

Cited In (29)

• CHARACTERIZING DOWNWARDS CLOSED, STRONGLY FIRST-ORDER, RELATIVIZABLE DEPENDENCIES
• Expressivity and Complexity of Dependence Logic
• On Hierarchical Reasoning in Combinations of Theories
• Title not available (Why is that?)
• Propositional union closed team logics
• A finite axiomatization of conditional independence and inclusion dependencies
• A double team semantics for generalized quantifiers
• COMPLETE LOGICS FOR ELEMENTARY TEAM PROPERTIES
• Title not available (Why is that?)
• Modal Inclusion Logic: Being Lax is Simpler than Being Strict
• Hierarchical deduction
• Modular SAT-based techniques for reasoning tasks in team semantics
• Dimension in team semantics
• The expressive power of \(k\)-ary exclusion logic
• On Dependence Logic
• Approximation and dependence via multiteam semantics
• Hierarchies in Dependence Logic
• On Strongly First-Order Dependencies
• Title not available (Why is that?)
• Complexity thresholds in inclusion logic
• On definability of team relations with \(k\)-invariant atoms
• The Expressive Power of k-ary Exclusion Logic
• Title not available (Why is that?)
• Safe dependency atoms and possibility operators in team semantics
• Capturing \(k\)-ary existential second order logic with \(k\)-ary inclusion-exclusion logic
• Model Checking and Validity in Propositional and Modal Inclusion Logics
• Axiomatizing first order consequences in inclusion logic
• Title not available (Why is that?)
• Doubly strongly first order dependencies

This page was built for publication: Hierarchies in independence logic

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