Data-complexity of the two-variable fragment with counting quantifiers

Ian Pratt-Hartmann

doi:10.1016/j.ic.2009.02.004

Data-complexity of the two-variable fragment with counting quantifiers

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

Abstract

The data-complexity of both satisfiability and finite satisfiability for the two-variable fragment with counting quantifiers is NP-complete; the data-complexity of both query answering and finite query answering for the two-variable guarded fragment with counting quantifiers is co-NP-complete. © 2009 Elsevier Inc. All rights reserved.

Original language	English
Pages (from-to)	867-888
Number of pages	21
Journal	Information and Computation
Volume	207
Issue number	8
DOIs	https://doi.org/10.1016/j.ic.2009.02.004
Publication status	Published - Aug 2009

Keywords

Data-complexity
Query answering
Two-variable fragment with counting

Access to Document

10.1016/j.ic.2009.02.004

Cite this

@article{55778b94233f4686941063eb0494d447,

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

abstract = "The data-complexity of both satisfiability and finite satisfiability for the two-variable fragment with counting quantifiers is NP-complete; the data-complexity of both query answering and finite query answering for the two-variable guarded fragment with counting quantifiers is co-NP-complete. {\textcopyright} 2009 Elsevier Inc. All rights reserved.",

keywords = "Data-complexity, Query answering, Two-variable fragment with counting",

author = "Ian Pratt-Hartmann",

year = "2009",

month = aug,

doi = "10.1016/j.ic.2009.02.004",

language = "English",

volume = "207",

pages = "867--888",

journal = "Information and Computation",

issn = "1090-2651",

publisher = "Elsevier BV",

number = "8",

}

TY - JOUR

T1 - Data-complexity of the two-variable fragment with counting quantifiers

AU - Pratt-Hartmann, Ian

PY - 2009/8

Y1 - 2009/8

N2 - The data-complexity of both satisfiability and finite satisfiability for the two-variable fragment with counting quantifiers is NP-complete; the data-complexity of both query answering and finite query answering for the two-variable guarded fragment with counting quantifiers is co-NP-complete. © 2009 Elsevier Inc. All rights reserved.

AB - The data-complexity of both satisfiability and finite satisfiability for the two-variable fragment with counting quantifiers is NP-complete; the data-complexity of both query answering and finite query answering for the two-variable guarded fragment with counting quantifiers is co-NP-complete. © 2009 Elsevier Inc. All rights reserved.

KW - Data-complexity

KW - Query answering

KW - Two-variable fragment with counting

U2 - 10.1016/j.ic.2009.02.004

DO - 10.1016/j.ic.2009.02.004

M3 - Article

SN - 1090-2651

VL - 207

SP - 867

EP - 888

JO - Information and Computation

JF - Information and Computation

IS - 8

ER -

Data-complexity of the two-variable fragment with counting quantifiers

Abstract

Keywords

Access to Document

Fingerprint

Cite this