Complexity of two-variable dependence logic and IF-logic
DOI10.1016/J.IC.2014.08.004zbMATH Open1310.03042OpenAlexW2077145135MaRDI QIDQ476186FDOQ476186
Authors: 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
Recommendations
complexityindependence-friendly logicdecidabilitysatisfiabilitydependence logicexpressivitytwo-variable logic
Other nonclassical logic (03B60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Dependence logic. A new approach to independence friendly logic
- Independence-friendly logic. A game-theoretic approach
- Compositional semantics for a language of imperfect information
- Title not available (Why is that?)
- Finite Partially‐Ordered Quantifiers
- Finite partially-ordered quantification
- Title not available (Why is that?)
- Title not available (Why is that?)
- Remarks on Berger's paper on the domino problem
- Title not available (Why is that?)
- On the Decision Problem for Two-Variable First-Order Logic
- The undecidability of the domino problem
- On logics with two variables
- On languages with two variables
- Complexity of the two-variable fragment with counting quantifiers
- Model-theoretic and computational properties of modal dependence logic
- Title not available (Why is that?)
- First-order logic with two variables and unary temporal logic
- Undecidability results on two-variable logics
- Complexity Results for Modal Dependence Logic
- Equivalence and quantifier rules for logic with imperfect information
- Computer Science Logic
- Title not available (Why is that?)
- Dependence of variables construed as an atomic formula
Cited In (12)
- Expressivity and Complexity of Dependence Logic
- Title not available (Why is that?)
- Dependence logic. A new approach to independence friendly logic
- Complexity Results for First-Order Two-Variable Logic with Counting
- A double team semantics for generalized quantifiers
- Boolean dependence logic and partially-ordered connectives
- Dependence logic vs. constraint satisfaction
- Approximation and dependence via multiteam semantics
- Tractability frontier of data complexity in team semantics
- Complexity thresholds in inclusion logic
- Decidability of predicate logics with team semantics
- On the complexity of team logic and its two-variable fragment
This page was built for publication: Complexity of two-variable dependence logic and IF-logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476186)
