Expressivity and Complexity of Dependence Logic

DOI10.1007/978-3-319-31803-5_2zbMATH Open1429.03114OpenAlexW2505761605MaRDI QIDQ5213639FDOQ5213639

Heribert Vollmer, Arnaud Durand, Juha Kontinen

Publication date: 4 February 2020

Published in: Dependence Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-31803-5_2

Recommendations

• Complexity of validity for propositional dependence logics
• Complexity of validity for propositional dependence logics
• A parameterized view on the complexity of dependence logic
• Complexity results for modal dependence logic
• Complexity Results for Modal Dependence Logic
• A parameterized view on the complexity of dependence and independence logic
• Coherence and computational complexity of quantifier-free dependence logic formulas
• scientific article; zbMATH DE number 1140581
• Expressibility of higher order logics
• Propositional logics of dependence

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60)

Cites Work

• Dependence and independence
• Title not available (Why is that?)
• Axiomatizing first-order consequences in independence logic
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• Modal logic
• Compositional semantics for a language of imperfect information
• Title not available (Why is that?)
• A note on the Entscheidungsproblem
• Graph properties checkable in linear time in the number of vertices
• Finite-model theory -- A personal perspective
• Title not available (Why is that?)
• Expressing second-order sentences in intuitionistic dependence logic
• Complexity results for modal dependence logic
• Propositional logics of dependence
• Extended Modal Dependence Logic $\mathcal{EMDL}$
• Complexity of Model Checking for Modal Dependence Logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Expressive Power of Modal Dependence Logic
• Title not available (Why is that?)
• Axiomatizing Propositional Dependence Logics
• Lower bounds for multiplayer noncooperative games of incomplete information
• On definability in dependence logic
• From IF to BI. A tale of dependence and separation
• Title not available (Why is that?)
• Capturing complexity classes by fragments of second-order logic
• Title not available (Why is that?)
• Generalized quantifiers in dependence logic
• Complexity of the two-variable fragment with counting quantifiers
• Dependence logic with a majority quantifier
• Hierarchies in independence logic
• Title not available (Why is that?)
• Dependence logic with a majority quantifier
• A double team semantics for generalized quantifiers
• Model-theoretic and Computational Properties of Modal Dependence Logic
• Model-checking games for logics of imperfect information
• Complexity of two-variable dependence logic and IF-logic
• Characterizing quantifier extensions of dependence logic
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Hierarchies in Dependence Logic
• Relational queries computable in polynomial time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of Propositional Independence and Inclusion Logic
• A Van Benthem Theorem for Modal Team Semantics
• Decidability of predicate logics with team semantics
• The expressive power of modal logic with inclusion atoms
• Team Logic and Second-Order Logic
• The complexity of poor man's logic
• A fragment of dependence logic capturing polynomial time
• Coherence and computational complexity of quantifier-free dependence logic formulas
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hierarchies in independence and inclusion logic with strict semantics
• Title not available (Why is that?)
• Capturing \(k\)-ary existential second order logic with \(k\)-ary inclusion-exclusion logic
• Hierarchies in Inclusion Logic with Lax Semantics
• Modal Inclusion Logic: Being Lax is Simpler than Being Strict

Cited In (16)

• CHARACTERIZING DOWNWARDS CLOSED, STRONGLY FIRST-ORDER, RELATIVIZABLE DEPENDENCIES
• Title not available (Why is that?)
• Complexity Results for Modal Dependence Logic
• Characterizing quantifier extensions of dependence logic
• Characterising modal definability of team-based logics via the universal modality
• Title not available (Why is that?)
• A parameterized view on the complexity of dependence logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• A dependent dependency calculus
• Safe dependency atoms and possibility operators in team semantics
• Model Checking and Validity in Propositional and Modal Inclusion Logics
• A fragment of dependence logic capturing polynomial time
• Canonical Models and the Complexity of Modal Team Logic
• On the complexity of team logic and its two-variable fragment
• Team semantics for the specification and verification of hyperproperties

This page was built for publication: Expressivity and Complexity of Dependence Logic

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