Tractability frontier of data complexity in team semantics

MaRDI QIDQ5013879zbMATH OpenFDO

Authors Arnaud Durand, Juha Kontinen, Nicolas De Rugy-Altherre, Jouko Väänänen

Publication date 3 December 2021

Full work available at URL https://arxiv.org/abs/1503.01144, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF2015.6

Mathematics Subject Classification ID

Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Tractability Frontier of Data Complexity in Team Semantics
• Complexity thresholds in inclusion logic
• Complexity of propositional logics in team semantic
• Complexity thresholds in inclusion logic
• Decidability of predicate logics with team semantics

Cites work

• A finite axiomatization of conditional independence and inclusion dependencies
• A fragment of dependence logic capturing polynomial time
• Capturing complexity classes by fragments of second-order logic
• Coherence and computational complexity of quantifier-free dependence logic formulas
• Complexity of two-variable dependence logic and IF-logic
• Dependence and independence
• Dependence logic. A new approach to independence friendly logic
• Hierarchies in Dependence Logic
• Hierarchies in independence and inclusion logic with strict semantics
• Hierarchies in independence logic
• scientific article; zbMATH DE number 6680142 (Why is no real title available?)
• Identifying independence in bayesian networks
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Inquisitive logic
• Model-checking games for logics of imperfect information
• Quantum team logic and Bell's inequalities

Cited in

(10)

• Approximation and dependence via multiteam semantics
• On elementary logics for quantitative dependencies
• Decidability of predicate logics with team semantics
• Tractability Frontier of Data Complexity in Team Semantics
• Counting of Teams in First-Order Team Logics
• Model checking and validity in propositional and modal inclusion logics
• A parameterized view on the complexity of dependence and independence logic
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• Complexity thresholds in inclusion logic
• Complexity thresholds in inclusion logic

This page was built for publication: Tractability frontier of data complexity in team semantics

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