Complexity thresholds in inclusion logic

DOI10.1016/J.IC.2021.104759MaRDI QIDQ5925562zbMATH OpenOpenAlexFDO

Authors Miika Hannula, Lauri Hella

Publication date 13 June 2022

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ic.2021.104759

zbMATH Keywords

complexityteam semanticsconsistent query answeringinclusion logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other nonclassical logic (03B60) Logic in computer science (03B70)

Recommendations

• Complexity thresholds in inclusion logic
• scientific article; zbMATH DE number 6680142
• Model checking and validity in propositional and modal inclusion logics
• Model checking and validity in propositional and modal inclusion logics
• Decidability of predicate logics with team semantics

Cites work

• scientific article; zbMATH DE number 6680142 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 7561483 (Why is no real title available?)
• A Logical Approach to Context-Specific Independence
• A finite axiomatization of conditional independence and inclusion dependencies
• A fragment of dependence logic capturing polynomial time
• Approximation and dependence via multiteam semantics
• Coherence and computational complexity of quantifier-free dependence logic formulas
• Complexity of propositional logics in team semantic
• Complexity of two-variable dependence logic and IF-logic
• Complexity of validity for propositional dependence logics
• Complexity thresholds in inclusion logic
• Compositional semantics for a language of imperfect information
• Dependence and Independence in Social Choice: Arrow’s Theorem
• Dependence logic. A new approach to independence friendly logic
• Extended modal dependence logic \(\mathcal{EMDL}\)
• Games for inclusion logic and fixed-point logic
• Hierarchies in independence logic
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Languages that Capture Complexity Classes
• Minimal-change integrity maintenance using tuple deletions
• Modal dependence logic
• Model-checking games for logics of imperfect information
• Nondeterministic Space is Closed under Complementation
• On the data complexity of consistent query answering
• Polyteam semantics
• Propositional logics of dependence
• Relational queries computable in polynomial time
• Satisfiability of modal inclusion logic. Lax and strict semantics
• Tractability frontier of data complexity in team semantics

Cited in

(11)

• Complexity thresholds in inclusion logic
• Modal inclusion logic: being lax is simpler than being strict
• Satisfiability of modal inclusion logic. Lax and strict semantics
• Games for inclusion logic and fixed-point logic
• Model checking and validity in propositional and modal inclusion logics
• Tractability frontier of data complexity in team semantics
• Computing repairs under functional and inclusion dependencies via argumentation
• Logics with probabilistic team semantics and the Boolean negation
• Tractability Frontier of Data Complexity in Team Semantics
• Model checking and validity in propositional and modal inclusion logics
• Logics with probabilistic team semantics and the Boolean negation

This page was built for publication: Complexity thresholds in inclusion logic

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