The two-variable fragment with counting and equivalence

Ian Pratt-Hartmann

doi:10.1002/malq.201400102

The two-variable fragment with counting and equivalence

Ian Pratt-Hartmann

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

101 Downloads (Pure)

Abstract

We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable.

Original language	English
Pages (from-to)	474-515
Number of pages	41
Journal	Mathematical Logic Quarterly
Volume	61
Issue number	6
DOIs	https://doi.org/10.1002/malq.201400102
Publication status	Published - 25 Nov 2015

Keywords

Two-variable fragment
Counting quantifier
Equivalence relation

Access to Document

10.1002/malq.201400102

POST-PEER-REVIEW-NON-PUBLISHERS.PDFAccepted author manuscript, 575 KBLicence: CC BY

Cite this

@article{2719aa0aa2eb418abc0d2e25e3dc4b0a,

title = "The two-variable fragment with counting and equivalence",

abstract = "We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable.",

keywords = "Two-variable fragment, Counting quantifier, Equivalence relation",

author = "Ian Pratt-Hartmann",

note = "This work is supported by the EPSRC, grant number EP/K017438/1.",

year = "2015",

month = nov,

day = "25",

doi = "10.1002/malq.201400102",

language = "English",

volume = "61",

pages = "474--515",

journal = "Mathematical Logic Quarterly",

issn = "0942-5616",

publisher = "John Wiley & Sons Ltd",

number = "6",

}

TY - JOUR

T1 - The two-variable fragment with counting and equivalence

AU - Pratt-Hartmann, Ian

N1 - This work is supported by the EPSRC, grant number EP/K017438/1.

PY - 2015/11/25

Y1 - 2015/11/25

N2 - We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable.

AB - We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable.

KW - Two-variable fragment

KW - Counting quantifier

KW - Equivalence relation

U2 - 10.1002/malq.201400102

DO - 10.1002/malq.201400102

M3 - Article

SN - 0942-5616

VL - 61

SP - 474

EP - 515

JO - Mathematical Logic Quarterly

JF - Mathematical Logic Quarterly

IS - 6

ER -

The two-variable fragment with counting and equivalence

Abstract

Keywords

Access to Document

Fingerprint

Cite this