The two-variable fragment with counting and equivalence

    Research output: Contribution to journalArticlepeer-review

    57 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 languageEnglish
    Pages (from-to)474-515
    Number of pages41
    JournalMathematical Logic Quarterly
    Volume61
    Issue number6
    DOIs
    Publication statusPublished - 25 Nov 2015

    Keywords

    • Two-variable fragment
    • Counting quantifier
    • Equivalence relation

    Fingerprint

    Dive into the research topics of 'The two-variable fragment with counting and equivalence'. Together they form a unique fingerprint.

    Cite this