Complexity of two-variable dependence logic and IF-logic

DOI10.1016/j.ic.2014.08.004zbMath1310.03042OpenAlexW2077145135MaRDI QIDQ476186

Antti Kuusisto, Peter Lohmann, Jonni Virtema, Juha Kontinen

Publication date: 28 November 2014

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

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

zbMATH Keywords

complexityindependence-friendly logicdecidabilitysatisfiabilityexpressivitydependence logictwo-variable logic

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Boolean dependence logic and partially-ordered connectives ⋮ A double team semantics for generalized quantifiers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the complexity of team logic and its two-variable fragment ⋮ Approximation and dependence via multiteam semantics ⋮ Expressivity and Complexity of Dependence Logic ⋮ Complexity thresholds in inclusion logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dependence of variables construed as an atomic formula
• On logics with two variables
• First-order logic with two variables and unary temporal logic
• Remarks on Berger's paper on the domino problem
• Complexity of the two-variable fragment with counting quantifiers
• Complexity Results for Modal Dependence Logic
• Equivalence and quantifier rules for logic with imperfect information
• Model-theoretic and Computational Properties of Modal Dependence Logic
• On languages with two variables
• On the Decision Problem for Two-Variable First-Order Logic
• Compositional semantics for a language of imperfect information
• Undecidability results on two-variable logics
• Computer Science Logic
• Finite Partially‐Ordered Quantifiers
• The undecidability of the domino problem
• Finite partially-ordered quantification

This page was built for publication: Complexity of two-variable dependence logic and IF-logic