Hierarchies in independence and inclusion logic with strict semantics

DOI10.1093/LOGCOM/EXU057zbMATH Open1345.03051arXiv1401.3232OpenAlexW2964104541MaRDI QIDQ5262488FDOQ5262488

Authors: Miika Hannula, Juha Kontinen 

Publication date: 15 July 2015

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

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).

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

Recommendations

• Hierarchies in independence logic
• Hierarchies in Inclusion Logic with Lax Semantics
• Hierarchies in Inclusion Logic with Lax Semantics
• Hierarchies in Dependence Logic
• Complexity thresholds in inclusion logic

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)

Cited In (17)

• Expressivity and Complexity of Dependence Logic
• Hierarchies in Inclusion Logic with Lax Semantics
• Title not available (Why is that?)
• Extended semantics and inference for the Independent Choice Logic
• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• Propositional union closed team logics
• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• The expressive power of \(k\)-ary exclusion logic
• Approximation and dependence via multiteam semantics
• Hierarchies in Dependence Logic
• On definability of team relations with \(k\)-invariant atoms
• The Expressive Power of k-ary Exclusion Logic
• Title not available (Why is that?)
• Capturing \(k\)-ary existential second order logic with \(k\)-ary inclusion-exclusion logic
• Model Checking and Validity in Propositional and Modal Inclusion Logics
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• Axiomatizing first order consequences in inclusion logic

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)