{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:17:13Z","timestamp":1725455833825},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540516590"},{"type":"electronic","value":"9783540467366"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/bfb0026298","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T05:35:17Z","timestamp":1132378517000},"page":"118-137","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Size of models versus length of computations"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Egon B\u00f6rger, Decision problems in predicate logic, in: Logic Colloquium 82, Elsevier (North Holland) 1984, 263\u2013301.","DOI":"10.1016\/S0049-237X(08)71820-2"},{"key":"7_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-87777-2","volume-title":"Berechenbarkeit, Komplexit\u00e4t, Logik","author":"E. B\u00f6rger","year":"1985","unstructured":"Egon B\u00f6rger, Berechenbarkeit, Komplexit\u00e4t, Logik, Vieweg-Verlag, Wiesbaden 1985."},{"key":"7_CR3","unstructured":"Kevin Compton and C. Ward 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":"7_CR4","volume-title":"The decision problem","author":"B. Dreben","year":"1979","unstructured":"Burton Dreben and Warren Goldfarb, The decision problem, Addison-Wesley, Reading (MA) 1979."},{"key":"7_CR5","doi-asserted-by":"crossref","first-page":"1237","DOI":"10.2307\/2274274","volume":"49","author":"W. Goldfarb","year":"1984","unstructured":"Warren Goldfarb, The unsolvability of the G\u00f6del class with identity, J. Symbolic Logic 49 (1984), 1237\u20131252.","journal-title":"J. Symbolic Logic"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0304-3975(88)90136-3","volume":"56","author":"E. Gr\u00e4del","year":"1988","unstructured":"Erich Gr\u00e4del, Subclasses of Presburger Arithmetic and the Polynomial-Time Hierarchy, Theoret. Comp. Sci. 56 (1988), 289\u2013301.","journal-title":"Theoret. Comp. Sci."},{"key":"7_CR7","unstructured":"Erich Gr\u00e4del, Dominoes and the Complexity of Subclasses of Logical Theories, to appear in Annals of Pure and Applied Logic."},{"key":"7_CR8","first-page":"25","volume":"5","author":"Y. Gurevich","year":"1966","unstructured":"Yuri Gurevich, Ob effektivnom raspoznavanii vipolnimosti formul UIP, Algebra i Logika 5 (1966), 25\u201355.","journal-title":"Algebra i Logika"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/BF02219647","volume":"8","author":"Y. Gurevich","year":"1969","unstructured":"Yuri Gurevich, The decision problem for the logic of predicates and operations, Algebra and Logic 8 (1969), 294\u2013308.","journal-title":"Algebra and Logic"},{"key":"7_CR10","unstructured":"Yuri Gurevich, Formulas with one \u2200, in: \u201cIzbrannye voprosy algebry i logika\u201d, (in memory of A. Mal\u0107ev), Novosibirsk 1973, 97\u2013110 (in Russian)."},{"key":"7_CR11","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1017\/S0022481200051513","volume":"41","author":"Y. Gurevich","year":"1976","unstructured":"Yuri Gurevich, The decision problem for standard classes, J. Symbolic Logic 41 (1976), 460\u2013464.","journal-title":"J. Symbolic Logic"},{"key":"7_CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF02297651","volume":"22","author":"Y. Gurevich","year":"1982","unstructured":"Yuri Gurevich, Existential Interpretation II, Arch. math. Logik 22 (1982), 103\u2013120.","journal-title":"Arch. math. Logik"},{"key":"7_CR13","volume-title":"Unsolvable Classes of Quantificational Formulas","author":"H. R. Lewis","year":"1979","unstructured":"Harry R. Lewis, Unsolvable Classes of Quantificational Formulas, Addison-Wesley, Reading (MA) 1979."},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"Joel Seiferas, Michael Fischer and Albert Meyer, Separating Nondeterministic Time Complexity Classes, J. ACM 25 (1978), 146\u2013167.","journal-title":"J. ACM"},{"key":"7_CR15","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BF02759780","volume":"28","author":"S. Shelah","year":"1977","unstructured":"Saharon Shelah, Decidability of a portion of the predicate calculus, Israel J. Math 28 (1977), 32\u201344.","journal-title":"Israel J. Math"},{"key":"7_CR16","first-page":"953","volume":"88","author":"B. Trachtenbrot","year":"1953","unstructured":"Boris Trachtenbrot, O recursivno otdelimosti, Dokl. Akad. Nauk SSSR 88 (1953), 953\u2013956.","journal-title":"Dokl. Akad. Nauk SSSR"}],"container-title":["Lecture Notes in Computer Science","CSL '88"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0026298","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:35:43Z","timestamp":1578526543000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0026298"}},"subtitle":["On Inseparability by nondeterministic time complexity classes"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540516590","9783540467366"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0026298","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}