Complexity of Propositional Independence and Inclusion Logic

DOI10.1007/978-3-662-48057-1_21zbMATH Open1465.68104arXiv1504.06135OpenAlexW1736037452MaRDI QIDQ2946342FDOQ2946342

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)

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.

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)

Cites Work

• 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
• The complexity of theorem-proving procedures
• Alternation
• A Finite Axiomatization of Conditional Independence and Inclusion Dependencies
• Complexity results for modal dependence logic
• Propositional logics of dependence
• Complexity of model checking for modal dependence logic
• Title not available (Why is that?)
• Axiomatizing Propositional Dependence Logics
• Complexity of Propositional Independence and Inclusion Logic
• A Van Benthem Theorem for Modal Team Semantics
• Team logic and second-order logic
• Title not available (Why is that?)
• Modal Inclusion Logic: Being Lax is Simpler than Being Strict

Cited In (13)

• Expressivity and Complexity of Dependence Logic
• Title not available (Why is that?)
• LOGICS FOR PROPOSITIONAL DETERMINACY AND INDEPENDENCE
• Computer Science Logic
• Axiomatizations of team logics
• Complexity of Propositional Independence and Inclusion Logic
• Approximation and dependence via multiteam semantics
• Parameterized complexity of propositional inclusion and independence logic
• Title not available (Why is that?)
• Model Checking and Validity in Propositional and Modal Inclusion Logics
• Title not available (Why is that?)
• Complexity of validity for propositional dependence logics
• 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)