Complexity of validity for propositional dependence logics

DOI10.1016/J.IC.2016.07.008MaRDI QIDQ515658zbMATH OpenOpenAlexFDO

Authors Jonni Virtema

Publication date 16 March 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2016.07.008

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of validity for propositional dependence logics
• Validity and entailment in modal and propositional dependence logics
• scientific article; zbMATH DE number 7056228
• Complexity Results for Modal Dependence Logic
• Complexity results for modal dependence logic

Cites work

• A remark on negation in dependence logic
• A Van Benthem Theorem for Modal Team Semantics
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• 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
• Compositional semantics for a language of imperfect information
• Dependence and independence
• Dependence logic. A new approach to independence friendly logic
• Dependency Quantified Horn Formulas: Models and Complexity
• Extended modal dependence logic \(\mathcal{EMDL}\)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Lower bounds for multiplayer noncooperative games of incomplete information
• Modal dependence logic
• Modal independence logic
• Modal logic
• Model checking for modal dependence logic: an approach through Post's lattice
• Model checking for modal intuitionistic dependence logic
• Model-theoretic and computational properties of modal dependence logic
• Models and quantifier elimination for quantified Horn formulas
• Propositional dynamic logic of regular programs
• The complexity of theorem-proving procedures
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The expressive power of modal dependence logic

Cited in

(20)

• Complexity results for modal dependence logic
• Coherence and computational complexity of quantifier-free dependence logic formulas
• A parameterized view on the complexity of dependence logic
• Boolean dependence logic and partially-ordered connectives
• A fragment of dependence logic capturing polynomial time
• Complexity Results for Modal Dependence Logic
• Complexity of validity for propositional dependence logics
• Team semantics for the specification and verification of hyperproperties
• On quantified propositional logics and the exponential time hierarchy
• Validity and entailment in modal and propositional dependence logics
• Complexity of validity for propositional dependence logics
• Expressivity and Complexity of Dependence Logic
• On the succinctness of atoms of dependency
• Axiomatizing propositional dependence logics
• scientific article; zbMATH DE number 7056228 (Why is no real title available?)
• Computer Science Logic
• Parameterised complexity of model checking and satisfiability in propositional dependence logic
• Complexity thresholds in inclusion logic
• Parameterized complexity of propositional inclusion and independence logic
• Set semantics for asynchronous TeamLTL: expressivity and complexity

This page was built for publication: Complexity of validity for propositional dependence logics

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