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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Grädel, E. and Otto, M., 1999, “On logics with two variables,” Theoretical Computer Science 224(1/2), 73–113.
Grädel, E., Otto, M., and Rosen, E., 1997, “Two-variable logic with counting is decidable,” in Proceedings of the 12th IEEE Symposium on Logic in Computer Science, pp. 306–317. IEEE Online Publications.
Pacholski, L., Szwast, W., and Tendera, L., 1997, “Complexity of two-variable logic with counting,” in Proceedings of the 12th IEEE Symposium on Logic in Computer Science, pp. 318–327. IEEE Online Publications.
Pacholski, L., Szwast, W., and Tendera, L., 1999, “Complexity results for first-order two-variable logic with counting,” SIAM Journal on Computing 29(4), 1083–1117.
Papadimitriou, C.H., 1981, “On the complexity of integer programming,” Journal of the Association for Computing Machinery 28(4), 765–768.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pratt-Hartmann, I. Complexity of the Two-Variable Fragment with Counting Quantifiers. J Logic Lang Inf 14, 369–395 (2005). https://doi.org/10.1007/s10849-005-5791-1
Issue Date:
DOI: https://doi.org/10.1007/s10849-005-5791-1