Complexity of Propositional Independence and Inclusion Logic

DOI10.1007/978-3-662-48057-1_21MaRDI QIDQ2946342zbMATH OpenOpenAlexFDO

Authors Miika Hannula, Juha Kontinen, Jonni Virtema, Heribert Vollmer

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

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

zbMATH Keywords

dependenceinclusionindependencemodel-checkingpropositional logicsatisfiabilityteam semanticsvalidity

Mathematics Subject Classification ID

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

Abstract: We classify the computational complexity of the satisfiability, validity and model-checking problems for propositional independence, inclusion, and team logic. Our main result shows that the satisfiability and validity problems for propositional team logic are complete for alternating exponential-time with polynomially many alternations.

Cites work

• A finite axiomatization of conditional independence and inclusion dependencies
• A Van Benthem Theorem for Modal Team Semantics
• Alternation
• Axiomatizing propositional dependence logics
• Complexity of model checking for modal dependence logic
• Complexity of Propositional Independence and Inclusion Logic
• Complexity of validity for propositional dependence logics
• Complexity results for modal dependence logic
• Dependence and independence
• Dependence logic. A new approach to independence friendly logic
• scientific article; zbMATH DE number 3825168 (Why is no real title available?)
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Modal inclusion logic: being lax is simpler than being strict
• Propositional logics of dependence
• Team logic and second-order logic
• The complexity of theorem-proving procedures

Cited in

(13)

• Approximation and dependence via multiteam semantics
• Axiomatizations of team logics
• Complexity of Propositional Independence and Inclusion Logic
• scientific article; zbMATH DE number 4114609 (Why is no real title available?)
• Logics for propositional determinacy and independence
• On quantified propositional logics and the exponential time hierarchy
• Canonical models and the complexity of modal team logic
• Model checking and validity in propositional and modal inclusion logics
• Complexity of validity for propositional dependence logics
• Expressivity and Complexity of Dependence Logic
• scientific article; zbMATH DE number 7056228 (Why is no real title available?)
• Computer Science Logic
• Parameterized complexity of propositional inclusion and independence logic

This page was built for publication: Complexity of Propositional Independence and Inclusion Logic

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