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 条

[21]

Kieronski E, 2005, IEEE S LOG, P448

[22]

Lohmann P, 2010, LECT NOTES COMPUT SC, V6247, P411, DOI 10.1007/978-3-642-15205-4_32

[23]

Mann A. L., INDEPENDENC IN PRESS

[24]

Mortimer M., 1975, MATH LOGIC QUART, V21, P135

[25]

PACHOLSKI L., 1997, LICS, P318

[26] Complexity of the Two-Variable Fragment with Counting Quantifiers [J].

Ian Pratt-Hartmann .

Journal of Logic, Language and Information, 2005, 14 (3) :369-395

[27]

Scott Dana, 1962, Journal of Symbolic Logic, V27, P74

[28] Model-theoretic and Computational Properties of Modal Dependence Logic [J].

Sevenster, Merlijn .

JOURNAL OF LOGIC AND COMPUTATION, 2009, 19 (06) :1157-1173

[29]

Turing AM, 1937, P LOND MATH SOC, V42, P230, DOI 10.1112/plms/s2-42.1.230

[30]

Vaananen J., 2007, LONDON MATH SOC STUD

← 1 2 3 4 →