Complexity of the two-variable fragment with counting quantifiers

Ian Pratt-Hartmann

doi:10.1007/s10849-005-5791-1

Complexity of the two-variable fragment with counting quantifiers

Ian Pratt-Hartmann

Research output: Contribution to journal › Article › peer-review

Abstract

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. © Springer 2005.

Original language	English
Pages (from-to)	369-395
Number of pages	26
Journal	Journal of Logic, Language and Information
Volume	14
Issue number	3
DOIs	https://doi.org/10.1007/s10849-005-5791-1
Publication status	Published - Jun 2005

Keywords

Complexity
Counting quantifiers
Logic
Two-variable fragment

Access to Document

10.1007/s10849-005-5791-1

Cite this

@article{be5cf3ead786471683923b0d7d4ebc0a,

title = "Complexity of the two-variable fragment with counting quantifiers",

abstract = "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. {\textcopyright} Springer 2005.",

keywords = "Complexity, Counting quantifiers, Logic, Two-variable fragment",

author = "Ian Pratt-Hartmann",

year = "2005",

month = jun,

doi = "10.1007/s10849-005-5791-1",

language = "English",

volume = "14",

pages = "369--395",

journal = "Journal of Logic, Language and Information",

issn = "0925-8531",

publisher = "Springer Nature",

number = "3",

}

TY - JOUR

T1 - Complexity of the two-variable fragment with counting quantifiers

AU - Pratt-Hartmann, Ian

PY - 2005/6

Y1 - 2005/6

N2 - 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. © Springer 2005.

AB - 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. © Springer 2005.

KW - Complexity

KW - Counting quantifiers

KW - Logic

KW - Two-variable fragment

U2 - 10.1007/s10849-005-5791-1

DO - 10.1007/s10849-005-5791-1

M3 - Article

SN - 0925-8531

VL - 14

SP - 369

EP - 395

JO - Journal of Logic, Language and Information

JF - Journal of Logic, Language and Information

IS - 3

ER -

Complexity of the two-variable fragment with counting quantifiers

Abstract

Keywords

Access to Document

Fingerprint

Cite this