Tractability Frontier of Data Complexity in Team Semantics

DOI10.1145/3471618MaRDI QIDQ5056358zbMATH OpenOpenAlexWikidataFDO

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

Publication date 8 December 2022

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3471618

zbMATH Keywords

dependenceindependenceteam semanticsmodel checkinginclusiondata complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Logic in computer science (03B70)

Recommendations

• Tractability frontier of data complexity in team semantics
• Complexity thresholds in inclusion logic
• Complexity of propositional logics in team semantic
• Decidability of predicate logics with team semantics
• Complexity thresholds in inclusion logic

Cited in

(9)

• Complexity thresholds in inclusion logic
• Modular SAT-based techniques for reasoning tasks in team semantics
• Parameterized complexity of weighted team definability
• Tractability frontier of data complexity in team semantics
• Logics with probabilistic team semantics and the Boolean negation
• Counting of teams in first-order team logics
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• The flattening operator in team-based logics
• Logics with probabilistic team semantics and the Boolean negation

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