Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers
<|reference_start|>Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers: We show that 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.<|reference_end|>
@article{pratt-hartmann2004complexity,
    title={Complexity of the Two-Variable Fragment with (Binary-Coded) Counting
  Quantifiers},
    author={Ian Pratt-Hartmann},
    journal={Journal of Logic, Language and Information, 14(3), 2005, pp.
  369--395},
    year={2004},
    doi={10.1007/s10849-005-5791-1},
    archivePrefix={arXiv},
    eprint={cs/0411031},
    primaryClass={cs.LO}
}