Complexity of the guarded two-variable fragment with counting quantifiers

Ian Pratt-Hartmann

doi:10.1093/logcom/exl034

Complexity of the guarded two-variable fragment with counting quantifiers

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

Abstract

The finite satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME. © The Author, 2006.

Original language	English
Pages (from-to)	133-155
Number of pages	22
Journal	Journal of Logic and Computation
Volume	17
Issue number	1
DOIs	https://doi.org/10.1093/logcom/exl034
Publication status	Published - Feb 2007

Keywords

Complexity
Counting quantifiers
Guarded fragment
Logic
Two-variable fragment

Access to Document

10.1093/logcom/exl034

Cite this

@article{c6060390271b4294813a00fd4bb804b6,

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

abstract = "The finite satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME. {\textcopyright} The Author, 2006.",

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

author = "Ian Pratt-Hartmann",

note = "Pratt-Hartmann, Ian 14 OXFORD UNIV PRESS OXFORD 140UH",

year = "2007",

month = feb,

doi = "10.1093/logcom/exl034",

language = "English",

volume = "17",

pages = "133--155",

journal = "Journal of Logic and Computation",

issn = "0955-792X",

publisher = "Oxford University Press",

number = "1",

}

TY - JOUR

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

AU - Pratt-Hartmann, Ian

N1 - Pratt-Hartmann, Ian 14 OXFORD UNIV PRESS OXFORD 140UH

PY - 2007/2

Y1 - 2007/2

N2 - The finite satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME. © The Author, 2006.

AB - The finite satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME. © The Author, 2006.

KW - Complexity

KW - Counting quantifiers

KW - Guarded fragment

KW - Logic

KW - Two-variable fragment

U2 - 10.1093/logcom/exl034

DO - 10.1093/logcom/exl034

M3 - Article

VL - 17

SP - 133

EP - 155

JO - Journal of Logic and Computation

JF - Journal of Logic and Computation

SN - 0955-792X

IS - 1

ER -

Complexity of the guarded two-variable fragment with counting quantifiers

Abstract

Keywords

Access to Document

Fingerprint

Cite this