{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:25:42Z","timestamp":1725456342771},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540634379"},{"type":"electronic","value":"9783540695479"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0029956","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T06:24:59Z","timestamp":1133418299000},"page":"129-138","source":"Crossref","is-referenced-by-count":4,"title":["The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes"],"prefix":"10.1007","author":[{"given":"Martin","family":"Mundhenk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Judy","family":"Goldsmith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Allender","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"issue":"1","key":"13_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ita\/1996300100011","volume":"30","author":"E. Allender","year":"1996","unstructured":"E. Allender and M. Ogihara. Relationships among PL, #L, and the determinant. RAIRO Theoretical Informatics and Applications, 30(1):1\u201321, 1996.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C. \u00c0Ivarez","year":"1993","unstructured":"C. \u00c0Ivarez and B. Jenner. A very hard log-space counting class. Theoretical Computer Science, 107:3\u201330, 1993.","journal-title":"Theoretical Computer Science"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0004-3702(96)00014-8","volume":"86","author":"J.L. Balc\u00e1zar","year":"1996","unstructured":"J.L. Balc\u00e1zar. The complexity of searching implicit graphs. Artificial Intelligence, 86:171\u2013188, 1996.","journal-title":"Artificial Intelligence"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar, A. Lozano, and J. Tor\u00e1n. The complexity of algorithmic problems on succinct instances. In R. Baeza-Yates and U. Manber, editors, Computer Science, pages 351\u2013377. Plenum Press, 1992.","DOI":"10.1007\/978-1-4615-3422-8_30"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"D. Beauquier, D. Burago, and A. Slissenko. On the complexity of finite memory policies for Markov decision processes. In Math. Foundations of Computer Science, pages 191\u2013200. Lecture Notes in Computer Science #969, Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60246-1_125"},{"issue":"13","key":"13_CR6","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0019-9958(83)80060-6","volume":"58","author":"A. Borodin","year":"1983","unstructured":"A. Borodin, S. Cook, and N. Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58(13):113\u2013136, 1983.","journal-title":"Information and Control"},{"key":"13_CR7","unstructured":"C. Boutilier and D. Poole. Computing optimal policies for partially observable decision processes using compact representations. In Proc. 13th National Conference on Artificial Intelligence, pages 1168\u20131175. AAAI Press \/ MIT Press, 1996."},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0004-3702(94)90081-7","volume":"69","author":"T. Bylander","year":"1994","unstructured":"T. Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69:165\u2013204, 1994.","journal-title":"Artificial Intelligence"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"K. Erol, J. Hendler, and D. Nau. Complexity results for hierarchical task-network planning. Annals of Mathematics and Artificial Intelligence, 1996.","DOI":"10.1007\/BF02136175"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0004-3702(94)00080-K","volume":"76","author":"K. Erol","year":"1995","unstructured":"K. Erol, D. Nau, and V. S. Subrahmanian. Complexity, decidability and undecidability results for domain-independent planning. Artificial Intelligence, 76:75\u201388, 1995.","journal-title":"Artificial Intelligence"},{"issue":"1","key":"13_CR11","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. Fenner","year":"1994","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48(1):116\u2013148, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"H. Galperin and A. Wigderson. Succinct representation of graphs. Information and Control, 56:183\u2013198, 1983.","journal-title":"Information and Control"},{"key":"13_CR13","unstructured":"J. Goldsmith, M. Littman, and M. Mundhenk. The complexity of plan existence and evaluation in probabilistic domains. In Proc. 13th Conf. on Uncertainty in AI. Morgan Kaufmann Publishers, 1997."},{"key":"13_CR14","unstructured":"J. Goldsmith, C. Lusena, and M. Mundhenk. The complexity of deterministically observable finite-horizon Markov decision processes. Technical Report 269-96, University of Kentucky Department of Computer Science, 1996."},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"H. Jung. On probabilistic time and space. In Proceedings 12th ICALP, pages 281\u2013291. Lecture Notes in Computer Science #194, Springer-Verlag, 1985.","DOI":"10.1007\/BFb0015756"},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/0218073","volume":"18","author":"R. Ladner","year":"1989","unstructured":"R. Ladner. Polynomial space counting problems. SIAM Journal on Computing, 18:1087\u20131097, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"13_CR17","unstructured":"M.L. Littman. Probabilistic propositional planning: Representations and complexity. In Proc. 14th National Conference on AI. AAAI Press \/ MIT Press, 1997."},{"key":"13_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF02055574","volume":"28","author":"W.S. Lovejoy","year":"1991","unstructured":"W.S. Lovejoy. A survey of algorithmic methods for partially observed Markov decision processes. Annals of Operations Research, 28:47\u201366, 1991.","journal-title":"Annals of Operations Research"},{"key":"13_CR19","unstructured":"C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou and J.N. Tsitsiklis. Intractable problems in control theory. SIAM Journal of Control and Optimization, pages 639\u2013654, 1986.","DOI":"10.1137\/0324038"},{"issue":"3","key":"13_CR21","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1287\/moor.12.3.441","volume":"12","author":"C.H. Papadimitriou","year":"1987","unstructured":"C.H. Papadimitriou and J.N. Tsitsiklis. The complexity of Markov decision processes. Mathematics of Operations Research, 12(3):441\u2013450, 1987.","journal-title":"Mathematics of Operations Research"},{"key":"13_CR22","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov decision processes","author":"M.L. Puterman","year":"1994","unstructured":"M.L. Puterman. Markov decision processes. John Wiley & Sons, New York, 1994."},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"V. Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proc. 6th Structure in Complexity Theory Conference, pages 270\u2013284. IEEE, 1991.","DOI":"10.1109\/SCT.1991.160269"},{"key":"13_CR24","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. W. Wagner","year":"1986","unstructured":"K. W. Wagner. The complexity of combinatorial problems with succinct input representation. Acta Informatica, 23:325\u2013356, 1986.","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1997"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T15:12:40Z","timestamp":1554736360000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540634379","9783540695479"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0029956","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}