Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
<|reference_start|>Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers: We show that the finite satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME. The method employed also yields a simple proof of a result recently obtained by Y. Kazakov, that the satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME.<|reference_end|>
@article{pratt-hartmann2006complexity,
    title={Complexity of the Guarded Two-Variable Fragment with Counting
  Quantifiers},
    author={Ian Pratt-Hartmann},
    journal={Journal of Logic and Computation, 17(1), 2007, pp. 133--155},
    year={2006},
    doi={10.1093/logcom/exl034},
    archivePrefix={arXiv},
    eprint={cs/0601112},
    primaryClass={cs.LO cs.CC}
}