Complexity of two-variable Dependence Logic and IF-Logic

被引：4

作者：

Kontinen, Juha ^{[1
]}

Kuusisto, Antti ^{[2
]}

Lohmann, Peter ^{[3
]}

Virtema, Jonni ^{[2
]}

机构：

[1] Univ Helsinki, FIN-00014 Helsinki, Finland

[2] Univ Tampere, FIN-33101 Tampere, Finland

[3] Leibniz Univ Hannover, Hannover, Germany

来源：

26TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2011) | 2011年

基金：

芬兰科学院;

关键词：

dependence logic; independence-friendly logic; two-variable logic; decidability; complexity; satisfiability; expressivity; 1ST-ORDER LOGIC; 2; VARIABLES; QUANTIFIERS;

D O I：

10.1109/LICS.2011.14

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the two-variable fragments D-2 and IF2 of dependence logic and independence-friendly logic. We consider the satisfiability and finite satisfiability problems of these logics and show that for D-2, both problems are NEXPTIME-complete, whereas for IF2, the problems are Pi(0)(1) and Sigma(0)(1)-complete, respectively. We also show that D-2 is strictly less expressive than IF2 and that already in D-2, equicardinality of two unary predicates and infinity can be expressed (the latter in the presence of a constant symbol). An extended version of this publication can be found at arxiv.org.

引用

页码：289 / 298

页数：10

共 33 条

[1]

Abramsky S., 2007, TEXTS LOGIC GAMES, V1, P11

[2]

Berger R, 1966, MEMOIRS AM MATH SOC

[3]

Bradfield J, 2005, LECT NOTES COMPUT SC, V3634, P355, DOI 10.1007/11538363_25

[4] Equivalence and quantifier rules for logic with imperfect information [J].