Expressivity and Complexity of Dependence Logic

DOI10.1007/978-3-319-31803-5_2zbMath1429.03114OpenAlexW2505761605MaRDI QIDQ5213639

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

Mathematics Subject Classification ID

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

Related Items (9)

Unnamed Item ⋮ Unnamed Item ⋮ Team semantics for the specification and verification of hyperproperties ⋮ On the complexity of team logic and its two-variable fragment ⋮ Characterising modal definability of team-based logics via the universal modality ⋮ CHARACTERIZING DOWNWARDS CLOSED, STRONGLY FIRST-ORDER, RELATIVIZABLE DEPENDENCIES ⋮ Safe dependency atoms and possibility operators in team semantics ⋮ Canonical Models and the Complexity of Modal Team Logic ⋮ Model Checking and Validity in Propositional and Modal Inclusion Logics

Cites Work

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

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