Archive for Mathematical Logic 29 (4):265-276 (1990)
| Abstract |
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 |
| Options |
Mark as duplicate
Export citation
Request removal from index
|
Download options
References found in this work BETA
The Unsolvability of the Gödel Class with Identity.Warren D. Goldfarb - 1984 - Journal of Symbolic Logic 49 (4):1237-1252.
Citations of this work BETA
On the Decision Problem for Two-Variable First-Order Logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
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 Decision Problem for Two-Variable First-Order Logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
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.
Small Substructures and Decidability Issues for First-Order Logic with Two Variables.Emanuel Kieroński & Martin Otto - 2012 - Journal of Symbolic Logic 77 (3):729-765.
The Bernays—Schönfinkel—Ramsey Class for Set Theory: Decidability.Alberto Policriti & Eugenio Omodeo - 2012 - Journal of Symbolic Logic 77 (3):896-918.
Undecidability Results on Two-Variable Logics.Erich Grädel, Martin Otto & Eric Rosen - 1999 - Archive for Mathematical Logic 38 (4-5):313-354.
Complexity Results for Modal Dependence Logic.Peter Lohmann & Heribert Vollmer - 2013 - Studia Logica 101 (2):343-366.
Periodicity Based Decidable Classes in a First Order Timed Logic.Danièle Beauquier & Anatol Slissenko - 2006 - Annals of Pure and Applied Logic 139 (1):43-73.
The Bernays-Schönfinkel-Ramsey Class for Set Theory: Semidecidability.Eugenio Omodeo & Alberto Policriti - 2010 - Journal of Symbolic Logic 75 (2):459-480.
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.
Analytics
Added to PP index
2013-11-23
Total views
21 ( #487,788 of 2,401,715 )
Recent downloads (6 months)
1 ( #551,964 of 2,401,715 )
2013-11-23
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?
Downloads
