Complexity of the two-variable fragment with counting quantifiers

    Research output: Contribution to journalArticlepeer-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 languageEnglish
    Pages (from-to)369-395
    Number of pages26
    JournalJournal of Logic, Language and Information
    Volume14
    Issue number3
    DOIs
    Publication statusPublished - Jun 2005

    Keywords

    • Complexity
    • Counting quantifiers
    • Logic
    • Two-variable fragment

    Fingerprint

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

    Cite this