Complexity of Propositional Independence and Inclusion Logic

DOI10.1007/978-3-662-48057-1_21MaRDI QIDQ2946342zbMATHOpenAlexFDO

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

dependenceindependenceteam semanticssatisfiabilityvaliditypropositional logicinclusionmodel-checking

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) Semantics in the theory of computing (68Q55)

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

• scientific article; zbMATH DE number 3825168 (Why is no real title available?)
• A Van Benthem Theorem for Modal Team Semantics
• A finite axiomatization of conditional independence and inclusion dependencies
• Alternation
• Axiomatizing propositional dependence logics
• Complexity of Propositional Independence and Inclusion Logic
• Complexity of model checking for modal dependence 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
• 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)

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