Hierarchies in independence logic

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.

References in corpus (1)

• On Dependence Logic

Cited by in corpus (6)

• On Strongly First-Order Dependencies
• Modular SAT-based techniques for reasoning tasks in team semantics
• A Double Team Semantics for Generalized Quantifiers
• Hierarchies in inclusion logic with lax semantics
• Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics
• Axiomatizing first-order consequences in inclusion logic