Complexity results for modal dependence logic

DOI10.1007/s11225-013-9483-6zbMath1432.03043OpenAlexW2003216212MaRDI QIDQ1956378

Heribert Vollmer, Peter Lohmann

Publication date: 13 June 2013

Published in: Studia Logica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2524/

zbMATH Keywords

computational complexitymodal logicsatisfiability problemdependence logicpoor man's logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Other nonclassical logic (03B60)

Related Items (17)

Boolean dependence logic and partially-ordered connectives ⋮ Propositional logics of dependence ⋮ Dependence logic with a majority quantifier ⋮ A parameterized view on the complexity of dependence logic ⋮ Structural completeness in propositional logics of dependence ⋮ Complexity of Propositional Independence and Inclusion Logic ⋮ The expressive power of modal logic with inclusion atoms ⋮ Parameterized complexity of propositional inclusion and independence logic ⋮ Complexity of validity for propositional dependence logics ⋮ Propositional team logics ⋮ Characterising modal definability of team-based logics via the universal modality ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ LOGICS FOR PROPOSITIONAL DETERMINACY AND INDEPENDENCE ⋮ Expressivity and Complexity of Dependence Logic ⋮ Approximation Logics for Subclasses of Probabilistic Conditional Independence and Hierarchical Dependence on Incomplete Data ⋮ Canonical Models and the Complexity of Modal Team Logic ⋮ Unnamed Item

Cites Work

• From IF to BI. A tale of dependence and separation
• Generalized modal satisfiability
• The complexity of existential quantification in concept languages.
• Complete sets and the polynomial-time hierarchy
• The complexity of problems for quantified constraints
• The Complexity of Poor Man's Logic
• Complexity Results for Modal Dependence Logic
• Model-theoretic and Computational Properties of Modal Dependence Logic
• Satisfiability problems for propositional calculi
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The Complexity of Satisfiability for Fragments of CTL and CTL⋆
• The complexity of theorem-proving procedures
• Lower bounds for multiplayer noncooperative games of incomplete information
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity results for modal dependence logic