Hierarchies in Dependence Logic
We study fragments D(ksic) and D(k-dep) of dependence logic defined either by restricting the number k of universal quantifiers or the width of dependence atoms in formulas. We find the sublogics of existential second-order logic corresponding to these fragments of dependence logic. We also show that, for any fixed signature, the fragments D(ksic) give rise to an infinite hierarchy with respect to expressive power. On the other hand, for the fragments D(k-dep), a hierarchy theorem is otained only in the case the signature is also allowed to vary. For any fixed signature, this question is open and is related to the so-called Spectrum Arity Hierarchy Conjecture.
dependence logic descriptive complexity expressibility hierarchies team languages theory