{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T15:07:47Z","timestamp":1673449667641},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1991,4]]},"DOI":"10.1145\/103516.128681","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"472-494","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Space-bounded probabilistic game automata"],"prefix":"10.1145","volume":"38","author":[{"given":"Anne","family":"Condon","sequence":"first","affiliation":[{"name":"University of Wisconson-Madison, Madison, Wisconsin"}]}],"member":"320","published-online":{"date-parts":[[1991,4]]},"reference":[{"key":"e_1_2_1_1_2","first-page":"421","volume-title":"Proceedings of the 17th A CM Symposium on the Theory of Computing (Providence, R.I., May 6-8). ACM","author":"BABAI L.","year":"1985","unstructured":"BABAI , L. Trading group theory for randomness . In Proceedings of the 17th A CM Symposium on the Theory of Computing (Providence, R.I., May 6-8). ACM , New York , 1985 , pp. 421 - 429 . 10.1145\/22145.22192 BABAI, L. Trading group theory for randomness. In Proceedings of the 17th A CM Symposium on the Theory of Computing (Providence, R.I., May 6-8). ACM, New York, 1985, pp. 421-429. 10.1145\/22145.22192"},{"key":"e_1_2_1_2_2","first-page":"1","volume-title":"Proceedings of the 20th A CM Symposium on the Theory of Computing","author":"BEN-OR M.","year":"1988","unstructured":"BEN-OR , M. , GOLDWASSER , S. , AND WIGDERSON , A. Completeness theorems for non-crytographic fault-tolerant distributed computation . In Proceedings of the 20th A CM Symposium on the Theory of Computing ( Chicago, Ill., May 2-4). ACM, New York , 1988 , pp. 1 - 10 . 10.1145\/62212.62213 BEN-OR, M., GOLDWASSER, S., AND WIGDERSON, A. Completeness theorems for non-crytographic fault-tolerant distributed computation. In Proceedings of the 20th A CM Symposium on the Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, 1988, pp. 1-10. 10.1145\/62212.62213"},{"key":"e_1_2_1_3_2","first-page":"188","volume-title":"Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE","author":"BRASSARD G.","year":"1986","unstructured":"BRASSARD , G. , AND CREPEAU , C Nontransitive transfer of confidence: A perfect-zero knowledge protocol for SAT and beyond . In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE , New York , 1986 , 188 - 195 . BRASSARD, G., AND CREPEAU, C Nontransitive transfer of confidence: A perfect-zero knowledge protocol for SAT and beyond. In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE, New York, 1986, 188-195."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_2_1_5_2","first-page":"11","volume-title":"Proceedings of the 20th A CM Symposium on the Theory of Computing","author":"CHAUM D.","year":"1988","unstructured":"CHAUM , D. , CREPEAU , C. , AND DAMGARD , I. Multiparty unconditionally secure protocols . In Proceedings of the 20th A CM Symposium on the Theory of Computing ( Chicago, Ill., May 2-4), ACM, New York , 1988 , 11 - 19 . 10.1145\/62212.62214 CHAUM, D., CREPEAU, C., AND DAMGARD, I. Multiparty unconditionally secure protocols. In Proceedings of the 20th A CM Symposium on the Theory of Computing (Chicago, Ill., May 2-4), ACM, New York, 1988, 11-19. 10.1145\/62212.62214"},{"key":"e_1_2_1_6_2","first-page":"162","volume-title":"Conference on Structure in Complexity Theory (June). IEEE","author":"CONDON A.","year":"1988","unstructured":"CONDON , A. :Space bounded probabllistic game automata . In Conference on Structure in Complexity Theory (June). IEEE , New York , 1988 , pp. 162 - 174 . CONDON, A. :Space bounded probabllistic game automata. In Conference on Structure in Complexity Theory (June). IEEE, New York, 1988, pp. 162-174."},{"key":"e_1_2_1_7_2","volume-title":"Wis.","author":"CONDON A.","year":"1989","unstructured":"CONDON , A. The complexity of stochastic games. Tech. Rep. 863. Univ. Wisconsin-Madison, Madison , Wis. , 1989 . CONDON, A.The complexity of stochastic games. Tech. Rep. 863. Univ. Wisconsin-Madison, Madison, Wis., 1989."},{"key":"e_1_2_1_8_2","volume-title":"Computational Models of Games","author":"CONDON A.","year":"1989","unstructured":"CONDON , A. Computational Models of Games . MIT Press , Cambridge, Mass ., 1989 . CONDON, A. Computational Models of Games. MIT Press, Cambridge, Mass., 1989."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90038-4"},{"key":"e_1_2_1_10_2","first-page":"462","volume-title":"Proceedings of the 30th IEEE Symposium on the Foundauons of Computer Science (Oct.). IEEE","author":"CONDON A.","year":"1989","unstructured":"CONDON , A. , AND LIPTON , R. J. On the complexity of space bounded interactive proof systems . In Proceedings of the 30th IEEE Symposium on the Foundauons of Computer Science (Oct.). IEEE , New York , 1989 , pp. 462 - 467 . CONDON, A., AND LIPTON, R. J. On the complexity of space bounded interactive proof systems. In Proceedings of the 30th IEEE Symposium on the Foundauons of Computer Science (Oct.). IEEE, New York, 1989, pp. 462-467."},{"key":"e_1_2_1_11_2","volume-title":"Interacnve proof systems with finite state verifiers. Res. Rep. RJ 6262 (61659)","author":"DWORK C.","year":"1988","unstructured":"DWORK , C. AND STOCKMEYER , L. Interacnve proof systems with finite state verifiers. Res. Rep. RJ 6262 (61659) . IBM Almaden Research Center , San Jose , Calif., 1988 . DWORK, C. AND STOCKMEYER, L. Interacnve proof systems with finite state verifiers. Res. Rep. RJ 6262 (61659). IBM Almaden Research Center, San Jose, Calif., 1988."},{"key":"e_1_2_1_12_2","first-page":"210","volume-title":"Proceedings of the 19th ACM Symposium on the Theory of Computing","author":"FEIGE U.","year":"1987","unstructured":"FEIGE , U. , FIAT , A. , AND SHAMIR , A. Zero knowledge proofs of identity . In Proceedings of the 19th ACM Symposium on the Theory of Computing ( New York, N.Y., May 25-27). ACM, New York , 1987 , pp. 210 - 217 . 10.1145\/28395.28419 FEIGE, U., FIAT, A., AND SHAMIR, A. Zero knowledge proofs of identity. In Proceedings of the 19th ACM Symposium on the Theory of Computing (New York, N.Y., May 25-27). ACM, New York, 1987, pp. 210-217. 10.1145\/28395.28419"},{"key":"e_1_2_1_14_2","volume-title":"Interactive proof systems with a log space verifier. Manuscript. MIT","author":"FORTNOW L.","year":"1988","unstructured":"FORTNOW , L. , AND SIPSER , M. Interactive proof systems with a log space verifier. Manuscript. MIT , Cambridge , Mass ., 1988 . FORTNOW, L., AND SIPSER, M. Interactive proof systems with a log space verifier. Manuscript. MIT, Cambridge, Mass., 1988."},{"key":"e_1_2_1_15_2","volume-title":"Computers and Intractibility: A Guide to the Theory of NP-Completeness","author":"GAREY M. R.","year":"1979","unstructured":"GAREY . M. R. , AND JOHNSON , D. S. Computers and Intractibility: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company , New York , 1979 . GAREY. M. R., AND JOHNSON, D. S. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979."},{"key":"e_1_2_1_16_2","first-page":"174","volume-title":"Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE","author":"GOLDREICH","year":"1986","unstructured":"GOLDREICH , 0., MICALI , S. , AND WIGDERSON , A Proofs that yield nothing but their validity and a methodology of cryptographic design . In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE , New York , 1986 , pp. 174 - 187 . GOLDREICH, 0., MICALI, S., AND WIGDERSON, A Proofs that yield nothing but their validity and a methodology of cryptographic design. In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE, New York, 1986, pp. 174-187."},{"key":"e_1_2_1_17_2","first-page":"365","volume-title":"Proceedings of the 14th A CM Symposium on the Theory of Computing","author":"GOLDWASSER S.","year":"1982","unstructured":"GOLDWASSER , S. , AND MICALI , S. Probabflistic encryption and how to play mental poker keeping secret all partial information . In Proceedings of the 14th A CM Symposium on the Theory of Computing ( San Francisco, Cahf., May 5-7). ACM, New York , 1982 , pp. 365 - 377 . 10.1145\/800070.802212 GOLDWASSER, S., AND MICALI, S. Probabflistic encryption and how to play mental poker keeping secret all partial information. In Proceedings of the 14th A CM Symposium on the Theory of Computing (San Francisco, Cahf., May 5-7). ACM, New York, 1982, pp. 365-377. 10.1145\/800070.802212"},{"key":"e_1_2_1_18_2","first-page":"291","volume-title":"Proceedings of the 17th A CM Symposium on the Theory of Computing (Providence, R.I., May 6-8). ACM","author":"GOLDWASSER S.","year":"1985","unstructured":"GOLDWASSER , S. , MICALI , S. , AND RACKOFF , C. The knowledge complexity of interactive proof systems . In Proceedings of the 17th A CM Symposium on the Theory of Computing (Providence, R.I., May 6-8). ACM , New York , 1985 , pp. 291 - 304 . 10.1145\/22145.22178 GOLDWASSER, S., MICALI, S., AND RACKOFF, C. The knowledge complexity of interactive proof systems. In Proceedings of the 17th A CM Symposium on the Theory of Computing (Providence, R.I., May 6-8). ACM, New York, 1985, pp. 291-304. 10.1145\/22145.22178"},{"key":"e_1_2_1_19_2","first-page":"59","volume-title":"Proceedings of the 18th ACM Symposium on the Theory of Computing","author":"GOLDWASSER S.","year":"1986","unstructured":"GOLDWASSER , S. , AND SIPSER , M. Private coins versus pubhc coins in interactive proof systems . In Proceedings of the 18th ACM Symposium on the Theory of Computing ( Berkeley, Calif., May 28-30). ACM, New York , 1986 , pp. 59 - 68 . 10.1145\/12130.12137 GOLDWASSER, S., AND SIPSER, M. Private coins versus pubhc coins in interactive proof systems. In Proceedings of the 18th ACM Symposium on the Theory of Computing (Berkeley, Calif., May 28-30). ACM, New York, 1986, pp. 59-68. 10.1145\/12130.12137"},{"key":"e_1_2_1_20_2","first-page":"25","volume-title":"Proceedings of the 29th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE","author":"KILLIAN J.","year":"1988","unstructured":"KILLIAN , J. Zero knowledge with log-space verifiers . In Proceedings of the 29th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE , New York , 1988 , pp. 25 - 35 . KILLIAN, J. Zero knowledge with log-space verifiers. In Proceedings of the 29th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE, New York, 1988, pp. 25-35."},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90045-5"},{"key":"e_1_2_1_22_2","first-page":"348","volume-title":"Proceedings of the 20th IEEE Symposium on the Foundations of Computer Science. IEEE","author":"PETERSON G. L.","year":"1979","unstructured":"PETERSON , G. L. , AND REIF , J. H. Multiple person alternation . In Proceedings of the 20th IEEE Symposium on the Foundations of Computer Science. IEEE , New York , 1979 , pp. 348 - 363 . PETERSON, G. L., AND REIF, J. H. Multiple person alternation. In Proceedings of the 20th IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 1979, pp. 348-363."},{"key":"e_1_2_1_23_2","first-page":"2","volume":"29","author":"REIF J H","year":"1984","unstructured":"REIF , J H . The complexity of two-player games of incomplete reformation J. Comput. Syst. Sci. 29 , 2 ( 1984 ), 274-301 REIF, J H. The complexity of two-player games of incomplete reformation J. Comput. Syst. Sci. 29, 2 (1984), 274-301","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0022-0000(84)90073-4","volume":"28","author":"SIMON J.","year":"1984","unstructured":"Ruzzo, W. L., SIMON , J. , AND TOMPA , M. Space-bounded hierarchies and probabflistlc computatlons. J. Comput. Sys. Scl. 28 , 2 ( Apr. 1984 ), 216-230. Ruzzo, W. L., SIMON, J., AND TOMPA, M. Space-bounded hierarchies and probabflistlc computatlons. J. Comput. Sys. Scl. 28, 2 (Apr. 1984), 216-230.","journal-title":"J. Comput. Sys. Scl."},{"key":"e_1_2_1_25_2","first-page":"1095","volume-title":"Proceedings of the National Academy of Sciences, U.S.A. Vol, 39","author":"SHAPLEY L. S.","year":"1953","unstructured":"SHAPLEY , L. S. Stochastic games . In Proceedings of the National Academy of Sciences, U.S.A. Vol, 39 . 1953 , pp. 1095 - 1100 . SHAPLEY, L. S. Stochastic games. In Proceedings of the National Academy of Sciences, U.S.A. Vol, 39. 1953, pp. 1095-1100."},{"key":"e_1_2_1_26_2","first-page":"472","volume-title":"Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE","author":"TOMPA M.","year":"1987","unstructured":"TOMPA , M. , AND WOLL , H Random self-reducibility and zero-knowledge interactive proofs of possession of informaUon . In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE , New York , 1987 , pp. 472 - 482 . TOMPA, M., AND WOLL, H Random self-reducibility and zero-knowledge interactive proofs of possession of informaUon. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE, New York, 1987, pp. 472-482."},{"key":"e_1_2_1_27_2","volume-title":"CWI Tract 33. Centrum voor Wiskunde en Informatica","author":"VRIEZE J.","unstructured":"VRIEZE , 0. J. Stochastic games with finite state and action spaces , CWI Tract 33. Centrum voor Wiskunde en Informatica , Amsterdam, The Netherlands, I987. VRIEZE, 0. J. Stochastic games with finite state and action spaces, CWI Tract 33. Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands, I987."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/103516.128681","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:26:41Z","timestamp":1672244801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/103516.128681"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,4]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,4]]}},"alternative-id":["10.1145\/103516.128681"],"URL":"http:\/\/dx.doi.org\/10.1145\/103516.128681","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1991,4]]},"assertion":[{"value":"1991-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}