{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T09:10:54Z","timestamp":1779268254699,"version":"3.51.4"},"reference-count":50,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2003,7,1]],"date-time":"2003-07-01T00:00:00Z","timestamp":1057017600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"vor","delay-in-days":3677,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[2003,7]]},"DOI":"10.1016\/s0004-3702(02)00378-8","type":"journal-article","created":{"date-parts":[[2003,2,17]],"date-time":"2003-02-17T12:19:30Z","timestamp":1045484370000},"page":"5-34","source":"Crossref","is-referenced-by-count":141,"title":["On the undecidability of probabilistic planning and related stochastic optimization problems"],"prefix":"10.1016","volume":"147","author":[{"given":"Omid","family":"Madani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steve","family":"Hanks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anne","family":"Condon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0004-3702(02)00378-8_BIB001","series-title":"Proc. of 27th STOC","first-page":"363","article-title":"Distinguishing tests for nondeterministic and probabilistic machines","author":"Alur","year":"1995"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB002","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0016-0032(65)90528-4","article-title":"Optimal control of partially observable Markovian systems","volume":"280","author":"Aoki","year":"1965","journal-title":"J. Franklin Inst."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB003","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/0022-247X(65)90154-X","article-title":"Optimal control of Markov processes with incomplete state information","volume":"10","author":"\u00c4strom","year":"1965","journal-title":"J. Math. Anal. Appl."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB004","series-title":"Vierte Jahrestagung der Gesellschaft f\u00fcr Informatik","first-page":"107","article-title":"The solution to problems relative to probabilistic automata in the frame of the formal languages theory","author":"Bertoni","year":"1975"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB005","series-title":"Automata, Languages and Programming","first-page":"87","article-title":"Some recursively unsolvable problems relating to isolated cutpoints in probabilistic automata","author":"Bertoni","year":"1977"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB006","series-title":"Dynamic Programming: Deterministic and Stochastic Models","author":"Bertsekas","year":"1987"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB007","unstructured":"V.D. Blondel, V. Canterini, Undecidable problems for probabilistic finite automata of fixed dimension, Technical Report, University of Louvain (Belgium), 2001. Available from: http:\/\/www.inma.ucl.ac.be\/~blondel\/publications\/"},{"issue":"9","key":"10.1016\/S0004-3702(02)00378-8_BIB008","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1016\/S0005-1098(00)00050-9","article-title":"A survey of computational complexity results in systems and control","volume":"36","author":"Blondel","year":"2000","journal-title":"Automatica"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB009","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.575","article-title":"Decision theoretic planning: Structural assumptions and computational leverage","volume":"11","author":"Boutilier","year":"2000","journal-title":"J. Artificial Intelligence Res."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB010","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0304-3975(95)00158-1","article-title":"On the complexity of partially observed Markov decision processes","author":"Burago","year":"1996","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB011","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0004-3702(94)90081-7","article-title":"The computational complexity of propositional STRIPS planning","volume":"69","author":"Bylander","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB012","unstructured":"A.R. Cassandra, Exact and approximate algorithms for partially observable Markov decision processes, PhD Thesis, Brown University, 1998"},{"issue":"3","key":"10.1016\/S0004-3702(02)00378-8_BIB013","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0004-3702(87)90092-0","article-title":"Planning for conjunctive goals","volume":"32","author":"Chapman","year":"1987","journal-title":"Artificial Intelligence"},{"issue":"2","key":"10.1016\/S0004-3702(02)00378-8_BIB014","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","article-title":"The complexity of simple stochastic games","volume":"96","author":"Condon","year":"1992","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB015","series-title":"Proc. 30th Annual Symposium on Foundations of Computer Science","article-title":"On the complexity of space bounded interactive proofs","author":"Condon","year":"1989"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB016","unstructured":"A.W. Drake, Observation of a Markov process through a noisy channel, PhD Thesis, Massachusetts Institute of Technology, 1962"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB017","series-title":"Proceedings of the Second International Conference on Artificial Intelligence Planning Systems","first-page":"31","article-title":"Probabilistic planning with information gathering and contingent execution","author":"Draper","year":"1994"},{"issue":"3\u20134","key":"10.1016\/S0004-3702(02)00378-8_BIB018","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0004-3702(71)90010-5","article-title":"STRIPS: A new approach to the application of theorem proving to problem solving","volume":"2","author":"Fikes","year":"1971","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB019","first-page":"33","article-title":"Probabilistic two way machines","volume":"118","author":"Freivalds","year":"1981"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB020","series-title":"Proc. IEEE Conference on Computational Complexity","first-page":"272","article-title":"Complexity issues in Markov decision processes","author":"Goldsmith","year":"1998"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB021","unstructured":"E.A. Hansen, Finite memory control of partially observable systems, PhD Thesis, University of Massachusetts, Amherst, 1998"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB022","series-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB023","series-title":"Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling","first-page":"323","article-title":"Approximate solutions to factored Markov decision processes via greedy search in the space of finite controllers","author":"Dean","year":"2000"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB024","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0004-3702(94)00087-H","article-title":"An algorithm for probabilistic planning","volume":"76","author":"Kushmerick","year":"1995","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB025","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","article-title":"Arthur\u2013Merlin games: A randomized proof system, and a hierarchy of complexity classes","volume":"36","author":"Moran","year":"1988","journal-title":"J. Computer System Sci."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB026","unstructured":"M.L. Littman, Algorithms for sequential decision making, PhD Thesis, Brown, 1996"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB027","series-title":"Proceedings of the 14th National Conference on AI","article-title":"Probabilistic propositional planning: Representations and complexity","author":"Littman","year":"1997"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB028","series-title":"Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence","article-title":"On the complexity of solving Markov decision problems","author":"Littman","year":"1995"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB029","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.505","article-title":"The computational complexity of probabilistic planning","volume":"9","author":"Littman","year":"1998","journal-title":"J. Artificial Intelligence Res."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB030","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02055574","article-title":"A survey of algorithmic methods for partially observable Markov decision processes","author":"Lovejoy","year":"1991","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB031","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1006\/inco.1995.1035","article-title":"A subexponential randomized algorithm for the simple stochastic game problem","volume":"117","author":"Ludwig","year":"1995","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB032","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1613\/jair.714","article-title":"Nonapproximability results for partially observable Markov decision processes","volume":"14","author":"Lusena","year":"2001","journal-title":"J. Artificial Intelligence Res."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB033","unstructured":"O. Madani, Complexity results for infinite-horizon Markov decision processes, PhD Thesis, University of Washington, 2000"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB034","series-title":"Proc. of 16th National Conference in Artificial Intelligence","first-page":"541","article-title":"On the computability of infinite-horizon partially observable Markov decision processes","author":"Madani","year":"1999"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB035","series-title":"Proc. 11th Annual IEEE Symposium on Logic in Computer Science","first-page":"523","article-title":"Decision problems for semi-thue systems with a few rules","author":"Matiyasevich","year":"1996"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB036","series-title":"Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI-99)","first-page":"427","article-title":"Learning finite-state controllers for partially observable environments","author":"Meuleau","year":"1999"},{"issue":"1","key":"10.1016\/S0004-3702(02)00378-8_BIB037","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.28.1.1","article-title":"A survey of partially observable Markov decision processes: Theory, models, and algorithms","volume":"28","author":"Monahan","year":"1982","journal-title":"Management Sci."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB038","series-title":"Proc. 22nd Mathematical Foundations of Computer Science","first-page":"129","article-title":"The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes","author":"Mundhenk","year":"1997"},{"issue":"4","key":"10.1016\/S0004-3702(02)00378-8_BIB039","doi-asserted-by":"crossref","DOI":"10.1145\/347476.347480","article-title":"Complexity results for finite-horizon Markov decision processs problems","volume":"47","author":"Mundhenk","year":"2000","journal-title":"J. ACM"},{"issue":"3","key":"10.1016\/S0004-3702(02)00378-8_BIB040","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1287\/moor.12.3.441","article-title":"The complexity of Markov decision processes","volume":"12","author":"Papadimitriou","year":"1987","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB041","series-title":"Introduction to Probabilistic Automata","author":"Paz","year":"1971"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB042","series-title":"Markov Decision Processes","author":"Puterman","year":"1994"},{"issue":"3","key":"10.1016\/S0004-3702(02)00378-8_BIB043","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","article-title":"Probabilistic automata","volume":"6","author":"Rabin","year":"1963","journal-title":"Inform. and Control"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB044","series-title":"Automata Theory","article-title":"Lectures on classical and probabilistic automata","author":"Rabin","year":"1966"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB045","series-title":"Proc. IJCAI-01, Seattle, WA","first-page":"503","article-title":"Complexity of probabilistic planning under average rewards","author":"Rintanen","year":"2001"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB046","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.1287\/opre.21.5.1071","article-title":"The optimal control of partially observable Markov processes over a finite horizon","volume":"21","author":"Smallwood","year":"1973","journal-title":"Oper. Res."},{"issue":"2","key":"10.1016\/S0004-3702(02)00378-8_BIB047","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1287\/opre.26.2.282","article-title":"The optimal control of partially observable Markov processes over the infinite horizon: Discounted costs","volume":"26","author":"Sondik","year":"1978","journal-title":"Oper. Res."},{"issue":"5","key":"10.1016\/S0004-3702(02)00378-8_BIB048","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0167-6377(90)90022-W","article-title":"Solving H-horizon stationary Markov decision process in time proportional to log(H)","volume":"9","author":"Tseng","year":"1990","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0004-3702(02)00378-8_BIB049","series-title":"Markov Decision Processes","author":"White","year":"1993"},{"key":"10.1016\/S0004-3702(02)00378-8_BIB050","unstructured":"W. Zhang, Algorithms for partially observable Markov decision processes, PhD Thesis, Hong Kong University of Science and Technology, 2001"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370202003788?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370202003788?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,27]],"date-time":"2019-03-27T07:57:46Z","timestamp":1553673466000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0004370202003788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,7]]},"references-count":50,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2003,7]]}},"alternative-id":["S0004370202003788"],"URL":"https:\/\/doi.org\/10.1016\/s0004-3702(02)00378-8","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[2003,7]]}}}