Archive for Mathematical Logic 29 (4):265-276 (1990)

In first order logic without equality, but with arbitrary relations and functions the ∃*∀∃* class is the unique maximal solvable prefix class. We show that the satisfiability problem for this class is decidable in deterministic exponential time The result is established by a structural analysis of a particular infinite subset of the Herbrand universe and by a polynomial space bounded alternating procedure
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/BF01651329
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 55,856
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

A Note on the Entscheidungsproblem.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.
The Unsolvability of the Gödel Class with Identity.Warren D. Goldfarb - 1984 - Journal of Symbolic Logic 49 (4):1237-1252.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

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.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Undecidability Results on Two-Variable Logics.Erich Grädel, Martin Otto & Eric Rosen - 1999 - Archive for Mathematical Logic 38 (4-5):313-354.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Decidable Fragments of First-Order Modal Logics.Frank Wolter & Michael Zakharyaschev - 2001 - Journal of Symbolic Logic 66 (3):1415-1438.
On the Relations Between Discrete and Continuous Complexity Theory.Klaus Meer - 1995 - Mathematical Logic Quarterly 41 (2):281-286.


Added to PP index

Total views
21 ( #487,788 of 2,401,715 )

Recent downloads (6 months)
1 ( #551,964 of 2,401,715 )

How can I increase my downloads?


My notes