{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:09Z","timestamp":1725663249221},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514985"},{"type":"electronic","value":"9783540481805"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51498-8_21","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:00:50Z","timestamp":1330203650000},"page":"224-233","source":"Crossref","is-referenced-by-count":2,"title":["Complexity of formula classes in first order logic with functions"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/BF01448869","volume":"100","author":"W. Ackermann","year":"1928","unstructured":"W. Ackermann, \u00dcber die Erf\u00fcllbarkeit gewisser Z\u00e4hlausdr\u00fccke, Math. Annalen 100 (1928), 638\u2013649.","journal-title":"Math. Annalen"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/BF01459101","volume":"99","author":"P. Bernays","year":"1928","unstructured":"P. Bernays and M. Sch\u00f6nfinkel, Zum Entscheidungsproblem der mathematischen Logik, Math. Annalen 99 (1928), 342\u2013372.","journal-title":"Math. Annalen"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"E. B\u00f6rger, Decision problems in predicate logic, in: \u201cLogic Colloquium 82\u201d, Elsevier (North Holland) 1984, 263\u2013301.","DOI":"10.1016\/S0049-237X(08)71820-2"},{"key":"21_CR4","unstructured":"K. Compton and C. W. Henson, A uniform method for proving lower bounds on the computational complexity of logical theories, to appear in Annals of Pure and Applied Logic."},{"key":"21_CR5","volume-title":"The decision problem","author":"B. Dreben","year":"1979","unstructured":"B. Dreben and W. Goldfarb, The decision problem, Addison-Wesley, Reading (MA) 1979."},{"key":"21_CR6","unstructured":"M. F\u00fcrer, Alternation and the Ackermann case of the decision problem, in: \u201cLogic and Algorithmic\u201d, Monographie Nr. 30 de L'Enseignement Math\u00e9matique, Gen\u00e8ve 1982, 161\u2013186."},{"key":"21_CR7","first-page":"27","volume":"2","author":"K. G\u00f6del","year":"1932","unstructured":"K. G\u00f6del, Ein Spezialfall des Entscheidungsproblems der theoretischen Logik, Ergebnisse eines mathematischen Kolloquiums 2 (1932), 27\u201328.","journal-title":"Ergebnisse eines mathematischen Kolloquiums"},{"key":"21_CR8","doi-asserted-by":"crossref","first-page":"1237","DOI":"10.2307\/2274274","volume":"49","author":"W. Goldfarb","year":"1984","unstructured":"W. Goldfarb, The unsolvability of the G\u00f6del class with identity, J. Symbolic Logic 49 (1984), 1237\u20131252.","journal-title":"J. Symbolic Logic"},{"key":"21_CR9","unstructured":"E. Gr\u00e4del, Satisfiability of formulas with one \u2200 is decidable in exponential time, submitted for publication."},{"key":"21_CR10","first-page":"25","volume":"5","author":"Y. Gurevich","year":"1966","unstructured":"Y. Gurevich, Ob effektivnom rasponznavanii vipolnimosti formul UIP, Algebra i Logika 5 (1966), 25\u201355 (in Russian).","journal-title":"Algebra i Logika"},{"key":"21_CR11","first-page":"294","volume":"8","author":"Y. Gurevich","year":"1969","unstructured":"Y. Gurevich, The decision problem for the logic of predicates and operations, Algebra and Logic 8 (1969), 294\u2013308.","journal-title":"Algebra and Logic"},{"key":"21_CR12","unstructured":"Y. Gurevich, 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, 97\u2013110 (in Russian)."},{"key":"21_CR13","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1017\/S0022481200051513","volume":"41","author":"Y. Gurevich","year":"1976","unstructured":"Y. Gurevich, The decision problem for standard classes, J. Symbolic Logic 41 (1976), 460\u2013464.","journal-title":"J. Symbolic Logic"},{"key":"21_CR14","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1073\/pnas.48.3.365","volume":"48","author":"A. Kahr","year":"1962","unstructured":"A. Kahr, E. Moore and H. Wang, Entscheidungsproblem reduced to the \u2200\u2203\u2200 case, Proc. Nat. Acad. Sci. U.S.A. 48 (1962), 365\u2013377.","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"P. Kolaitis and M. Vardi, 0\u20131 Laws and Decision Problems for Fragments of Second-Order Logic, Proceedings of 3rd IEEE Symposium on Logic in Computer Science 1988, 2\u201311.","DOI":"10.1109\/LICS.1988.5095"},{"key":"21_CR16","volume-title":"Unsolvable Classes of Quantificational Formulas","author":"H. Lewis","year":"1979","unstructured":"H. Lewis, Unsolvable Classes of Quantificational Formulas, Addison Wesley, Reading (MA) 1979."},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0022-0000(80)90027-6","volume":"21","author":"H. Lewis","year":"1980","unstructured":"H. Lewis, Complexity Results for Classes of Quantificational Formulas, J. of Computer and System Sciences 21 (1980), 317\u2013353.","journal-title":"J. of Computer and System Sciences"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/BF01458217","volume":"76","author":"L. L\u00f6wenheim","year":"1915","unstructured":"L. L\u00f6wenheim, \u00dcber M\u00f6glichkeiten im Relativkalk\u00fcl, Math. Annalen 76 (1915), 447\u2013470.","journal-title":"Math. Annalen"},{"key":"21_CR19","unstructured":"A. Meyer, The inherent computational complexity of theories of ordered sets, in: \u201cProc. 1974 Int. Cong. of Mathematicians\u201d, Vancouver (1974), 477\u2013482."},{"key":"21_CR20","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BF02759780","volume":"28","author":"S. Shelah","year":"1977","unstructured":"S. Shelah, Decidability of a portion of the predicate calculus, Israel J. Math 28 (1977), 32\u201344.","journal-title":"Israel J. Math"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51498-8_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:03:33Z","timestamp":1619571813000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51498-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514985","9783540481805"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-51498-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}