Complexity of the two-variable fragment with counting quantifiers

Journal of Logic, Language and Information 14 (3):369-395 (2005)
  Copy   BIBTEX

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,549

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The two‐variable fragment with counting and equivalence.Ian Pratt-Hartmann - 2015 - Mathematical Logic Quarterly 61 (6):474-515.
Fragments of first-order logic.Ian Pratt-Hartmann - 2023 - Oxford: Oxford University Press.
A Double Team Semantics for Generalized Quantifiers.Antti Kuusisto - 2015 - Journal of Logic, Language and Information 24 (2):149-191.
An Event-Based Fragment of First-Order Logic over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.
Dependence Logic with a Majority Quantifier.Arnaud Durand, Johannes Ebbing, Juha Kontinen & Heribert Vollmer - 2015 - Journal of Logic, Language and Information 24 (3):289-305.
The fluted fragment with transitive relations.Ian Pratt-Hartmann & Lidia Tendera - 2022 - Annals of Pure and Applied Logic 173 (1):103042.
Fragments of language.Ian Pratt-Hartmann - 2004 - Journal of Logic, Language and Information 13 (2):207-223.

Analytics

Added to PP
2009-01-28

Downloads
44 (#357,912)

6 months
5 (#880,810)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references