{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T05:40:09Z","timestamp":1735710009398,"version":"3.32.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1990,12,1]],"date-time":"1990-12-01T00:00:00Z","timestamp":660009600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Arch Math Logic"],"published-print":{"date-parts":[[1990,12]]},"DOI":"10.1007\/bf01651329","type":"journal-article","created":{"date-parts":[[2005,5,7]],"date-time":"2005-05-07T17:32:39Z","timestamp":1115487159000},"page":"265-276","source":"Crossref","is-referenced-by-count":2,"title":["Satisfiability of formulae with one \u2200 is decidable in exponential time"],"prefix":"10.1007","volume":"29","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/BF01448869","volume":"100","author":"W. Ackermann","year":"1928","unstructured":"Ackermann, W.: \u00fcber die Erf\u00fcllbarkeit gewisser Z\u00e4hlausdr\u00fccke. Math. Ann.100, 638\u2013649 (1928)","journal-title":"Math. Ann."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/BF01459101","volume":"99","author":"P. Bernays","year":"1928","unstructured":"Bernays, P., Sch\u00f6nfinkel, M.: Zum Entscheidungsproblem der mathematischen Logik. Math. Ann.99, 342\u2013372 (1928)","journal-title":"Math. Ann."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6rger, E.: Decision problems in predicate logic. In: \u201cLogic Colloquium 82\u201d. North Holland: Elsevier, pp. 263\u2013301","DOI":"10.1016\/S0049-237X(08)71820-2"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"Chandra, A., Kozen, D., Stockmeyer, L.: Alternation. J. Assoc. Comput. Mach.28, 114\u2013133 (1981)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"40","DOI":"10.2307\/2269326","volume":"1","author":"A. Church","year":"1936","unstructured":"Church, A.: A note on the Entscheidungsproblem. J. Symb. Logic1, 40\u201341 (1936); Correction ibid, 101\u2013102","journal-title":"J. Symb. Logic"},{"key":"CR6","unstructured":"F\u00fcrer, M.: Alternation and the Ackermann case of the decision problem. In: \u201cLogic and Algorithmic\u201d, Monogr. Nr. 30 de L'Enseignement Math\u00e9matique. Gen\u00e8ve, pp. 161\u2013186, 1982"},{"key":"CR7","first-page":"27","volume":"2","author":"K. G\u00f6del","year":"1932","unstructured":"G\u00f6del, K.: Ein Spezialfall des Entscheidungsproblems der theoretischen Logik. Ergebnisse eines mathematischen Kolloquiums2, 27\u201328 (1932)","journal-title":"Ergebnisse eines mathematischen Kolloquiums"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"1237","DOI":"10.2307\/2274274","volume":"49","author":"W. Goldfarb","year":"1984","unstructured":"Goldfarb, W.: The unsolvability of the G\u00f6del class with identity. J. Symb. Logic49, 1237\u20131252 (1984)","journal-title":"J. Symb. Logic"},{"key":"CR9","unstructured":"Gr\u00e4del, E.: Subcases of the decision problem inP, NP andCo-NP. (Submitted for publication)"},{"key":"CR10","first-page":"294","volume":"8","author":"Y. Gurevich","year":"1969","unstructured":"Gurevich, Y.: The decision problem for the logic of predicates and operations. Algebra Logic8, 294\u2013308 (1969)","journal-title":"Algebra Logic"},{"key":"CR11","first-page":"97","volume-title":"\u201cIzbrannye voprosy algebry i logiki\u201d, (Selected Questions in Algebra and Logic; in memory of A. Mal\u0107ev)","author":"Y. Gurevich","year":"1973","unstructured":"Gurevich, Y.: Formuly s odnim \u2200 (formulas with one \u2200). In: \u201cIzbrannye voprosy algebry i logiki\u201d, (Selected Questions in Algebra and Logic; in memory of A. Mal\u0107ev), Nauka, Novosibirsk 1973, pp. 97\u2013110 (in Russian)"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1017\/S0022481200051513","volume":"41","author":"Y. Gurevich","year":"1976","unstructured":"Gurevich, Y.: The decision problem for standard classes. J. Symb. Logic41, 460\u2013464 (1976)","journal-title":"J. Symb. Logic"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1073\/pnas.48.3.365","volume":"48","author":"A. Kahr","year":"1962","unstructured":"Kahr, A., Moore, E., Wang, H.: Entscheidungsproblem reduced to the \u2200\u2203\u2200 case. Proc. Natl. Acad. Sci. USA48, 365\u2013377 (1962)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"Kolaitis, P., Vardi, M.: 0\u20131 Laws and Decision Problems for Fragments of Second-Order Logic. Proc. 3rd IEEE Symp. Logic Comput. Sci. pp. 2\u201311 (1988)","DOI":"10.1109\/LICS.1988.5095"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0022-0000(80)90027-6","volume":"21","author":"H. Lewis","year":"1980","unstructured":"Lewis, H.: Complexity Results for Classes of Quantificational formulas. J. Comput. Syst. Sci.21, 317\u2013353 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02021316","volume":"1","author":"J. Suranyi","year":"1950","unstructured":"Suranyi, J.: Contributions to the reduction theory of the decision problem, second paper. Acta Math. Acad. Sci. Hungaricae1, 261\u2013270 (1950)","journal-title":"Acta Math. Acad. Sci. Hungaricae"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","volume":"42","author":"A. Turing","year":"1937","unstructured":"Turing, A.: On computable numbers, with an application to the \u201cEntscheidungsproblem\u201d. Proc. London Math. Soc. 2nd ser.42, 230\u2013265 (1937); Correction ibid43, 544\u2013546 (1937)","journal-title":"Proc. London Math. Soc. 2nd ser."}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01651329.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01651329\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01651329","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T04:30:59Z","timestamp":1735705859000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01651329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,12]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1990,12]]}},"alternative-id":["BF01651329"],"URL":"https:\/\/doi.org\/10.1007\/bf01651329","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"type":"print","value":"0933-5846"},{"type":"electronic","value":"1432-0665"}],"subject":[],"published":{"date-parts":[[1990,12]]}}}