Hierarchies in independence and inclusion logic with strict semantics

2014/01/14 by Hannula, Miika, Kontinen, Juha
#03C80 #F.4.1 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1401.3232

Abstract

We study the expressive power of fragments of inclusion and independence logic defined by restricting the number k of universal quantifiers in formulas. Assuming the so-called strict semantics for these logics, we relate these fragments of inclusion and independence logic to sublogics ESO_f(k∀) of existential second-order logic, which in turn are known to capture the complexity classes NTIME_RAM(n^k).

Related

• Hierarchies in independence logic
• Hierarchies in inclusion logic with lax semantics
• Hierarchies in Dependence Logic
• Characterizing Quantifier Extensions of Dependence Logic
• The Expressive Power of k-ary Exclusion Logic