Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426487 | Information and Computation | 2014 | 17 Pages |
Abstract
We study the two-variable fragments D2D2 and IF2IF2 of dependence logic and independence-friendly logic. We consider the satisfiability and finite satisfiability problems of these logics and show that for D2D2, both problems are NEXPTIME -complete, whereas for IF2IF2, the problems are Π10 and Σ10-complete, respectively. We also show that D2D2 is strictly less expressive than IF2IF2 and that already in D2D2, equicardinality of two unary predicates and infinity can be expressed (the latter in the presence of a constant symbol).This is an extended version of a publication in the proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Juha Kontinen, Antti Kuusisto, Peter Lohmann, Jonni Virtema,