Complexity of the Two-Variable Fragment with Counting Quantifiers

被引：76

作者：

Ian Pratt-Hartmann

机构：

[1] University of Manchester,School of Computer Science

来源：

Journal of Logic, Language and Information | 2005年 / 14卷 / 3期

关键词：

two-variable fragment; counting quantifiers; logic; complexity;

D O I：

10.1007/s10849-005-5791-1

中图分类号：

学科分类号：

摘要：

The satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when counting quantifiers are coded succinctly.

引用

页码：369 / 395

页数：26

共 50 条

[1] Complexity of the guarded two-variable fragment with counting quantifiers
Pratt-Hartmann, Ian
JOURNAL OF LOGIC AND COMPUTATION, 2007, 17 (01) : 133 - 155
[2] Data-complexity of the two-variable fragment with counting quantifiers
Pratt-Hartmann, Ian
INFORMATION AND COMPUTATION, 2009, 207 (08) : 867 - 888
[3] Weighted first-order model counting in the two-variable fragment with counting quantifiers
Kuželka O.
Journal of Artificial Intelligence Research, 2021, 70 : 1281 - 1307
[4] Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers
Kuzelka, Ondrej
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2021, 70 : 1281 - 1307
[5] Two-Variable First Order Logic with Counting Quantifiers: Complexity Results
Lodaya, Kamal
Sreejith, A. V.
DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017, 2017, 10396 : 260 - 271
[6] The two-variable fragment with counting and equivalence
Pratt-Hartmann, Ian
MATHEMATICAL LOGIC QUARTERLY, 2015, 61 (06) : 474 - 515
[7] The Two-Variable Fragment with Counting Revisited
Pratt-Hartmann, Ian
LOGIC, LANGUAGE, INFORMATION AND COMPUTATION, 2010, 6188 : 42 - 54
[8] Complexity of two-variable logic with counting
Pacholski, L
Szwast, W
Tendera, L
12TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 1997, : 318 - 327
[9] On the complexity of the two-variable guarded fragment with transitive guards
Kieronski, Emanuel
INFORMATION AND COMPUTATION, 2006, 204 (11) : 1663 - 1703
[10] A Two-Variable Fragment of English
Ian Pratt-Hartmann
Journal of Logic, Language and Information, 2003, 12 (1) : 13 - 45

← 1 2 3 4 5 →