Complexity of validity for propositional dependence logics

DOI10.1016/j.ic.2016.07.008zbMath1362.68114OpenAlexW2963866037MaRDI QIDQ515658

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

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items

Boolean dependence logic and partially-ordered connectives, Unnamed Item, Parameterized complexity of propositional inclusion and independence logic, Team semantics for the specification and verification of hyperproperties, Complexity of validity for propositional dependence logics, Characterising modal definability of team-based logics via the universal modality, Parameterised complexity of model checking and satisfiability in propositional dependence logic, Unnamed Item, Complexity thresholds in inclusion logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of validity for propositional dependence logics
• A remark on negation in dependence logic
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Models and quantifier elimination for quantified Horn formulas
• Propositional dynamic logic of regular programs
• Dependence and independence
• Complexity results for modal dependence logic
• Characterising modal definability of team-based logics via the universal modality
• Extended Modal Dependence Logic $\mathcal{EMDL}$
• Model Checking for Modal Dependence Logic: An Approach through Post’s Lattice
• Complexity of Model Checking for Modal Dependence Logic
• Complexity of Propositional Independence and Inclusion Logic
• Modal independence logic:
• Model-theoretic and Computational Properties of Modal Dependence Logic
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Compositional semantics for a language of imperfect information
• The Expressive Power of Modal Dependence Logic
• Model Checking for Modal Intuitionistic Dependence Logic
• A Van Benthem Theorem for Modal Team Semantics
• The complexity of theorem-proving procedures
• Dependency Quantified Horn Formulas: Models and Complexity
• Lower bounds for multiplayer noncooperative games of incomplete information