Expressivity and Complexity of Dependence Logic

DOI10.1007/978-3-319-31803-5_2MaRDI QIDQ5213639zbMATH OpenOpenAlexFDO

Authors Arnaud Durand, Juha Kontinen, Heribert Vollmer

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60)

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

Cites work

• scientific article; zbMATH DE number 6680142 (Why is no real title available?)
• scientific article; zbMATH DE number 5295726 (Why is no real title available?)
• scientific article; zbMATH DE number 4041866 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3562523 (Why is no real title available?)
• scientific article; zbMATH DE number 1500520 (Why is no real title available?)
• scientific article; zbMATH DE number 4118333 (Why is no real title available?)
• scientific article; zbMATH DE number 3263218 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• A Van Benthem Theorem for Modal Team Semantics
• A double team semantics for generalized quantifiers
• A fragment of dependence logic capturing polynomial time
• A note on the Entscheidungsproblem
• Axiomatizing first-order consequences in independence logic
• Axiomatizing propositional dependence logics
• Capturing \(k\)-ary existential second order logic with \(k\)-ary inclusion-exclusion logic
• Capturing complexity classes by fragments of second-order logic
• Characterizing quantifier extensions of dependence logic
• Coherence and computational complexity of quantifier-free dependence logic formulas
• Complexity of Propositional Independence and Inclusion Logic
• Complexity of model checking for modal dependence logic
• Complexity of the two-variable fragment with counting quantifiers
• Complexity of two-variable dependence logic and IF-logic
• Complexity of validity for propositional dependence logics
• Complexity results for modal dependence logic
• Compositional semantics for a language of imperfect information
• Decidability of predicate logics with team semantics
• Dependence and independence
• Dependence logic with a majority quantifier
• Dependence logic with a majority quantifier
• Dependence logic. A new approach to independence friendly logic
• Expressing second-order sentences in intuitionistic dependence logic
• Extended modal dependence logic \(\mathcal{EMDL}\)
• Finite-model theory -- A personal perspective
• From IF to BI. A tale of dependence and separation
• Generalized quantifiers in dependence logic
• Graph properties checkable in linear time in the number of vertices
• Hierarchies in Dependence Logic
• Hierarchies in independence and inclusion logic with strict semantics
• Hierarchies in independence logic
• 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 inclusion logic: being lax is simpler than being strict
• Modal indepence logic
• Modal logic
• Model-checking games for logics of imperfect information
• Model-theoretic and computational properties of modal dependence logic
• On definability in dependence logic
• Propositional logics of dependence
• Relational queries computable in polynomial time
• Team logic
• Team logic and second-order logic
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of poor man's logic
• The expressive power of modal dependence logic
• The expressive power of modal logic with inclusion atoms

Cited in

(25)

• Team semantics for the specification and verification of hyperproperties
• On quantified propositional logics and the exponential time hierarchy
• Dependence logic. A new approach to independence friendly logic
• scientific article; zbMATH DE number 4061208 (Why is no real title available?)
• Complexity Results for Modal Dependence Logic
• On definability in dependence logic
• Characterizing quantifier extensions of dependence logic
• Canonical models and the complexity of modal team logic
• Boolean dependence logic and partially-ordered connectives
• Boolean dependence logic and partially-ordered connectives
• Characterizing downwards closed, strongly first-order, relativizable dependencies
• scientific article; zbMATH DE number 7447734 (Why is no real title available?)
• Dependence logic vs. constraint satisfaction
• A parameterized view on the complexity of dependence logic
• scientific article; zbMATH DE number 3978447 (Why is no real title available?)
• Expressivity landscape for logics with probabilistic interventionist counterfactuals
• Dependence of variables construed as an atomic formula
• A dependent dependency calculus
• Team Logic and Second-Order Logic
• Safe dependency atoms and possibility operators in team semantics
• On dependence logic
• Model checking and validity in propositional and modal inclusion logics
• A fragment of dependence logic capturing polynomial time
• On strongly first-order dependencies
• On the complexity of team logic and its two-variable fragment

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)