{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:35:13Z","timestamp":1787506513781,"version":"build-2736575974"},"publisher-location":"Berlin\/Heidelberg","reference-count":17,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540188347","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0035836","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T10:40:10Z","timestamp":1138185610000},"page":"98-107","source":"Crossref","is-referenced-by-count":2,"title":["Domino games with an application to the complexity of boolean algebras with bounded quantifier alternations"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"R.Berger, The undecidability of the domino problem, Memoirs of the AMS 66, 1966","DOI":"10.1090\/memo\/0066"},{"key":"11_CR2","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0304-3975(80)90037-7","volume":"11","author":"L. Berman","year":"1980","unstructured":"L. Berman, The complexity of logical theories, Theor. Comp. Sci. 11 (1980), 71\u201377","journal-title":"Theor. Comp. Sci."},{"key":"11_CR3","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"A.K. Chandra, D.C. Kozen & L. Stockmeyer, Alternation, J. ACM 28 (1981), 114\u2013133","journal-title":"J. ACM"},{"key":"11_CR4","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/0022-0000(86)90036-X","volume":"32","author":"B. Chlebus","year":"1986","unstructured":"B. Chlebus, Domino-Tiling Games, J. Comp. System Sci. 32 (1986), 374\u2013392","journal-title":"J. Comp. System Sci."},{"key":"11_CR5","unstructured":"P. van Emde Boas, Dominoes are forever, Report 83-04, Department of Mathematics, University of Amsterdam 1983"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"M.F\u00fcrer, The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems), in: Logic and Machines. Decision problems and complexity, Lecture Notes in Computer Science Nr.171, Springer 1984, 312\u2013319","DOI":"10.1007\/3-540-13331-3_48"},{"key":"11_CR7","unstructured":"E.Gr\u00e4del, The Complexity of Subclasses of Logical Theories, Dissertation Basel 1987"},{"key":"11_CR8","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. of Symbolic Logic 41 (1976), 460\u2013464","journal-title":"J. of Symbolic Logic"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"D.Harel, Recurring dominoes: Making the highly undecidable highly understandable, in: Foundation of Computation Theory, Lecture Notes in Computer Science Nr. 158, Springer 1983, 177\u2013194","DOI":"10.1007\/3-540-12689-9_103"},{"key":"11_CR10","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1073\/pnas.48.3.365","volume":"48","author":"A.S. Kahr","year":"1962","unstructured":"A.S. Kahr, E.F. Moore and H. Wang, Entscheidungsproblem reduced to the \u2200\u2203\u2200-case, Proc. Nat. Acad. Sci. USA 48 (1962), 365\u2013377","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"11_CR11","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0304-3975(80)90048-1","volume":"10","author":"D. Kozen","year":"1980","unstructured":"D. Kozen, Complexity of Boolean algebras, Theor. Comp. Sci. 10 (1980), 221\u2013247","journal-title":"Theor. Comp. Sci."},{"key":"11_CR12","unstructured":"H.R.Lewis, Unsolvable Classes of Quantificational Formulas, Reading 1979"},{"key":"11_CR13","unstructured":"H.R.Lewis, C.H.Papadimitriou, Elements of the Theory of Computation, Prentice-Hall 1981"},{"key":"11_CR14","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0020-0190(85)90076-6","volume":"20","author":"E.D. Sontag","year":"1985","unstructured":"E.D. Sontag, Real addition and the polynomial-time hierarchy, Inform. Process. Letters 20 (1985), 115\u2013120","journal-title":"Inform. Process. Letters"},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer, The polynomial-time hierarchy, Theor. Comp. Sci. 3 (1977), 1\u201322","journal-title":"Theor. Comp. Sci."},{"key":"11_CR16","first-page":"64","volume":"55","author":"A. Tarski","year":"1949","unstructured":"A. Tarski, Arithmetical classes and types of Boolean algebras, Bull. AMS 55 (1949) 64, 1192","journal-title":"Bull. AMS"},{"key":"11_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/j.1538-7305.1961.tb03975.x","volume":"40","author":"H. Wang","year":"1961","unstructured":"H. Wang, Proving theorems by pattern recognition II, The Bell System Technical Journal 40 (1961), 1\u201341","journal-title":"The Bell System Technical Journal"}],"container-title":["Lecture Notes in Computer Science","STACS 88"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0035836.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T17:15:27Z","timestamp":1607534127000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0035836"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540188347"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0035836","relation":{},"subject":[]}}