The ground-negative fragment of first-order logic is πp2-complete

Journal of Symbolic Logic 64 (3):984 - 990 (1999)
  Copy   BIBTEX

Abstract

We prove that for a natural class of first-order formulas the validity problem is Π p 2 -complete

Categories

Keywords

Reprint years

DOI

10.2307/2586615

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,225

External links

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

Through your library

My notes

Similar books and articles

Linguistic applications of first order intuitionistic linear logic.Richard Moot & Mario Piazza - 2001 - Journal of Logic, Language and Information 10 (2):211-232.
A Probabilistic Logic Between $$LPP1$$ L P P 1 and $$LPP2$$ L P P 2.Šejla Dautović - 2022 - Logica Universalis 16 (1):323-333.
Revisiting separation: Algorithms and complexity.Daniel Oliveira & João Rasga - 2021 - Logic Journal of the IGPL 29 (3):251-302.
The complexity of definability by open first-order formulas.Carlos Areces, Miguel Campercholi, Daniel Penazzi & Pablo Ventura - 2020 - Logic Journal of the IGPL 28 (6):1093-1105.
On the restraining power of guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Decidable fragments of first-order temporal logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
The Π₃-Theory of the [image] -Enumeration Degrees Is Undecidable.Thomas F. Kent - 2006 - Journal of Symbolic Logic 71 (4):1284 - 1302.
Completeness and Decidability of General First-Order Logic.Aldo Antonelli - 2017 - Journal of Philosophical Logic 46 (3):233-257.
Taming first-order logic.Szabolcs Mikulás - 1998 - Logic Journal of the IGPL 6 (2):305-316.
On the Decision Problem for Two-Variable First-Order Logic.Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.

Analytics

Added to PP
2009-01-28

Downloads
412 (#69,422)

6 months
12 (#293,221)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Add more references