Complexity of the two-variable fragment with counting quantifiers

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


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.



    Upload a copy of this work     Papers currently archived: 84,292

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

An Event-Based Fragment of First-Order Logic over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.
A two-variable fragment of English.Ian Pratt-Hartmann - 2003 - Journal of Logic, Language and Information 12 (1):13-45.
Two variable first-order logic over ordered domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
On the restraining power of guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Fragments of language.Ian Pratt-Hartmann - 2004 - Journal of Logic, Language and Information 13 (2):207-223.


Added to PP

38 (#333,580)

6 months
1 (#510,180)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references