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: 90,221

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.

Analytics

Added to PP
2009-01-28

Downloads
40 (#345,973)

6 months
2 (#658,848)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references