{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T12:53:04Z","timestamp":1692363184534},"reference-count":24,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"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":3942,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2002,10]]},"DOI":"10.1016\/s0304-3975(01)00179-7","type":"journal-article","created":{"date-parts":[[2002,10,7]],"date-time":"2002-10-07T20:25:18Z","timestamp":1034022318000},"page":"829-843","source":"Crossref","is-referenced-by-count":2,"title":["Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete"],"prefix":"10.1016","volume":"289","author":[{"given":"Wolfgang","family":"Slany","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00179-7_BIB1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB2","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1090\/S0002-9904-1972-12927-6","article-title":"Generalized Ramsey theory for graphs","volume":"78","author":"Chv\u00e1tal","year":"1972","journal-title":"Bull. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB3","series-title":"Infinite and Finite Sets","first-page":"323","article-title":"A generalization of Ramsey's theorem","volume":"Vol. 10","author":"Deuber","year":"1975"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB4","series-title":"Infinite and Finite Sets","first-page":"585","article-title":"Strong embeddings of graphs into colored graphs","volume":"Vol. 10","author":"Erd\u0151s","year":"1975"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB5","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","article-title":"On a combinatorial game","volume":"14","author":"Erd\u0151s","year":"1973","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB6","doi-asserted-by":"crossref","unstructured":"S. Even, R.E. Tarjan, A combinatorial problem which is complete in polynomial space, J. Assoc. Comput. Mach. 23 (1976) 710\u2013719, also appeared in: Proc. 7th Ann. ACM Symp. Theory of Computing, Albuquerque, NM, Assoc. Comput. Mach., New York, NY, 1975, pp. 66\u201371.","DOI":"10.1145\/321978.321989"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB7","doi-asserted-by":"crossref","unstructured":"J.R. Gilbert, T. Lengauer, R.E. Tarjan, The pebbling problem is complete in polynomial space, SIAM J. Comput. 9 (1980) 513\u2013524, preliminary version in: Proc. 11th Ann. ACM Symp. Theory of Computing, Atlanta, GA, Assoc. Comput. Mach., New York, NY, 1979, pp. 237\u2013248.","DOI":"10.1137\/0209038"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4153\/CJM-1955-001-4","article-title":"Combinatorial relations and chromatic graphs","volume":"VII","author":"Greenwood","year":"1955","journal-title":"Canad. J. Math."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB9","unstructured":"F. Harary, W. Slany, O. Verbitsky, A symmetric strategy in graph avoidance games, Presented at the Combinatorial Game Theory Research Workshop, Mathematical Sciences Research Institute in Berkeley, California, July 2000."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB10","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0304-3975(94)90131-7","article-title":"The Othello game on an n\u00d7n board is PSPACE-complete","volume":"123","author":"Iwata","year":"1994","journal-title":"Theoret. Comput. Sci. (Math Games)"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB11","doi-asserted-by":"crossref","unstructured":"D. Lichtenstein, M. Sipser, Go is polynomial-space hard, J. Assoc. Comput. Mach. 27 (1980) 393\u2013401, earlier draft appeared in: Proc. 19th Ann. Symp. Foundations of Computer Science, Ann Arbor, MI, October, IEEE Computer Soc., Long Beach, CA, 1978, pp. 48\u201354.","DOI":"10.1145\/322186.322201"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB12","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1006\/jctb.1996.1741","article-title":"Subgraph counting identities and Ramsey numbers, to the fond memory of Paul Erd\u0151s","volume":"69","author":"McKay","year":"1997","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01755964","article-title":"Playing disjunctive sums is polynomial space complete","volume":"10","author":"Morris","year":"1981","journal-title":"Internat. J. Game Theory"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB14","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/0022-0000(85)90045-5","article-title":"Games against Nature","volume":"31","author":"Papadimitriou","year":"1985","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB15","unstructured":"S. Radziszowski, Electron. J. Combin. (dynamic surveys) (1994) Revision No. 6: July 5, 1999. Small Ramsey numbers. URL http:\/\/www.combinatorics.org\/Surveys\/ds1.ps."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB16","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF00288536","article-title":"Gobang ist PSPACE-vollst\u00e4ndig","volume":"13","author":"Reisch","year":"1980","journal-title":"Acta Inform."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB17","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00288964","article-title":"Hex ist PSPACE-vollst\u00e4ndig","volume":"15","author":"Reisch","year":"1981","journal-title":"Acta Inform."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB18","unstructured":"V. R\u00f6dl, 1973. A generalization of Ramsey theorem and dimension of graphs. MSC Thesis, Charles University, Prague."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB19","doi-asserted-by":"crossref","unstructured":"M. Schaefer, Graph Ramsey theory and the polynomial hierarchy. Proc. 31st ACM Symp on Theory of Computing (STOC), SIGACT (the ACM Special Interest Group on Algorithms and Computation Theory), Atlanta, Georgia, May 1999.","DOI":"10.1145\/301250.301411"},{"issue":"2","key":"10.1016\/S0304-3975(01)00179-7_BIB20","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","article-title":"On the complexity of some two-person perfect-information games","volume":"16","author":"Schaefer","year":"1978","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"10.1016\/S0304-3975(01)00179-7_BIB21","first-page":"66","article-title":"The game of SIM","volume":"2","author":"Simmons","year":"1969","journal-title":"J. Recreational Math."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB22","unstructured":"W. Slany, Graph Ramsey games, Technical Report DBAI-TR-99-34, Institut f\u00fcr Informationssysteme der Technischen Universit\u00e4t Wien, 1999. URL http:\/\/www.arXiv.org\/abs\/cs.CC\/9911004\/."},{"key":"10.1016\/S0304-3975(01)00179-7_BIB23","doi-asserted-by":"crossref","unstructured":"W. Slany, The complexity of graph Ramsey games, in: T. Marsland, I. Frank (Eds.), Proc. 2nd Internat. Conf. on Computers and Games, Hamamatsu, Japan, October 2000.","DOI":"10.1007\/3-540-45579-5_12"},{"key":"10.1016\/S0304-3975(01)00179-7_BIB24","first-page":"92","article-title":"Towards global computations guided by concurrency theory","volume":"66","author":"Thomsen","year":"1998","journal-title":"Bull. European Assoc. Theoret. Comput. Sci."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001797?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001797?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T17:57:11Z","timestamp":1583776631000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501001797"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0304397501001797"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00179-7","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}