{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T10:35:36Z","timestamp":1648636536630},"reference-count":18,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1991,9,1]],"date-time":"1991-09-01T00:00:00Z","timestamp":683683200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":7990,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[1991,9]]},"DOI":"10.1016\/0890-5401(91)90033-x","type":"journal-article","created":{"date-parts":[[2004,12,2]],"date-time":"2004-12-02T00:24:20Z","timestamp":1101947060000},"page":"62-82","source":"Crossref","is-referenced-by-count":0,"title":["Simple sentences that are hard to decide"],"prefix":"10.1016","volume":"94","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0890-5401(91)90033-X_BIB1","article-title":"The undecidability of the domino problem","volume":"66","author":"Berger","year":"1966","journal-title":"Mem. Amer. Math. Soc."},{"key":"10.1016\/0890-5401(91)90033-X_BIB2","series-title":"Logic Colloquium 82","first-page":"263","article-title":"Decision problems in predicate logic","author":"B\u00f6rger","year":"1984"},{"key":"10.1016\/0890-5401(91)90033-X_BIB3","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/0022-0000(86)90036-X","article-title":"Domino-tiling games","volume":"32","author":"Chlebus","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0890-5401(91)90033-X_BIB4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(90)90080-L","article-title":"A uniform method for proving lower bounds on the computational complexity of logical theories","volume":"48","author":"Compton","year":"1990","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0890-5401(91)90033-X_BIB5","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1070\/RM1965v020n04ABEH001188","article-title":"Elementary theories","volume":"20","author":"Er\u0161ov","year":"1965","journal-title":"Russian Math. Surveys"},{"key":"10.1016\/0890-5401(91)90033-X_BIB6","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90115-3","article-title":"The complexity of Presburger arithmetic with bounded quantifier alternation","volume":"18","author":"F\u00fcrer","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(91)90033-X_BIB7","series-title":"Proceedings of STACS 88","first-page":"98","article-title":"Domino games, with an application to the complexity of boolean algebras with bounded quantifier alternations","author":"Gr\u00e4del","year":"1988"},{"key":"10.1016\/0890-5401(91)90033-X_BIB8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(89)90023-7","article-title":"Dominoes and the complexity of subclasses of logical theories","volume":"43","author":"Gr\u00e4del","year":"1989","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0890-5401(91)90033-X_BIB9","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/0219055","article-title":"Domino games and complexity","volume":"19","author":"Gr\u00e4del","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(91)90033-X_BIB10","author":"Gr\u00e4tzer","year":"1978"},{"key":"10.1016\/0890-5401(91)90033-X_BIB11","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0304-3975(80)90048-1","article-title":"Complexity of boolean algebras","volume":"10","author":"Kozen","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(91)90033-X_BIB12","series-title":"Proceedings, 10th ACM Symposium on Theory of Computing","first-page":"320","article-title":"Presburger arithmetic with bounded quantifier alternation","author":"Reddy","year":"1978"},{"key":"10.1016\/0890-5401(91)90033-X_BIB13","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1090\/S0002-9947-1984-0742421-9","article-title":"Complexity of subcases of Presburger arithmetic","volume":"284","author":"Scarpellini","year":"1984","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0890-5401(91)90033-X_BIB14","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0020-0190(85)90076-6","article-title":"Real addition and the polynomial time hierarchy","volume":"20","author":"Sontag","year":"1985","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0890-5401(91)90033-X_BIB15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial time hierarchy","volume":"3","author":"Stockmeyer","year":"1977","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(91)90033-X_BIB16","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0304-3975(83)90038-5","article-title":"Turing machines with linear alternation, theories of bounded concatenation and the decision problem for first order theories","volume":"23","author":"Volger","year":"1983","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(91)90033-X_BIB17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/j.1538-7305.1961.tb03975.x","article-title":"Proving theorems by pattern recognition, II","volume":"40","author":"Wang","year":"1961","journal-title":"The Bell System Tech. J."},{"key":"10.1016\/0890-5401(91)90033-X_BIB18","series-title":"Efficient decision algorithms for locally finite theories","author":"Weispeenning","year":"1985"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:089054019190033X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:089054019190033X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,1]],"date-time":"2019-02-01T18:25:17Z","timestamp":1549045517000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/089054019190033X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["089054019190033X"],"URL":"https:\/\/doi.org\/10.1016\/0890-5401(91)90033-x","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}