Hierarchies in independence and inclusion logic with strict semantics

DOI10.1093/LOGCOM/EXU057zbMATH1345.03051OpenAlexW2964104541MaRDI QIDQ5262488FDOQ5262488

Authors Miika Hannula, Juha Kontinen

Publication date 15 July 2015

Published in Journal Of Logic And Computation (Search for Journal in Brave)

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

zbMATH Keywords

hierarchyteam semanticsdependence logicinclusion logic

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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(kforall) of existential second-order logic, which in turn are known to capture the complexity classes NTIME_{RAM}(n^k).

Recommendations

• Hierarchies in independence logic
• Hierarchies in Dependence Logic
• Complexity thresholds in inclusion logic

Cited in

(17)

• Extended semantics and inference for the Independent Choice Logic
• The expressive power of \(k\)-ary exclusion logic
• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• Axiomatizing first order consequences in inclusion logic
• Tractability frontier of data complexity in team semantics
• Hierarchies in independence logic
• scientific article; zbMATH DE number 1256653 (Why is no real title available?)
• Capturing \(k\)-ary existential second order logic with \(k\)-ary inclusion-exclusion logic
• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• Expressivity and Complexity of Dependence Logic
• Hierarchies in Dependence Logic
• The expressive power of \(k\)-ary exclusion logic
• On definability of team relations with \(k\)-invariant atoms
• Propositional union closed team logics
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• Model checking and validity in propositional and modal inclusion logics
• Approximation and dependence via multiteam semantics

This page was built for publication: Hierarchies in independence and inclusion logic with strict semantics

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