Complexity of the Two-Variable Fragment with Counting Quantifiers

被引：78

作者：

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

共 6 条

[1]

Grädel E.(1999)On logics with two variables Theoretical Computer Science 224 73-113

[2]

Otto M.(1999)Complexity results for first-order two-variable logic with counting SIAM Journal on Computing 29 1083-1117

[3]

Pacholski L.(1981)On the complexity of integer programming Journal of the Association for Computing Machinery 28 765-768

[4]

Szwast W.(undefined)undefined undefined undefined undefined-undefined

[5]

Tendera L.(undefined)undefined undefined undefined undefined-undefined

[6]

Papadimitriou C.H.(undefined)undefined undefined undefined undefined-undefined

← 1 →