{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T00:39:56Z","timestamp":1783643996581,"version":"3.55.0"},"reference-count":42,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[1994,9]]},"DOI":"10.1016\/0004-3702(94)90081-7","type":"journal-article","created":{"date-parts":[[2003,3,14]],"date-time":"2003-03-14T13:02:52Z","timestamp":1047646972000},"page":"165-204","source":"Crossref","is-referenced-by-count":356,"title":["The computational complexity of propositional STRIPS planning"],"prefix":"10.1016","volume":"69","author":[{"given":"Tom","family":"Bylander","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/0004-3702(94)90081-7_BIB1","year":"1990"},{"key":"10.1016\/0004-3702(94)90081-7_BIB2","series-title":"Proceedings IJCAI-91","first-page":"286","article-title":"The downward refinement property","author":"Bacchus","year":"1991"},{"key":"10.1016\/0004-3702(94)90081-7_BIB3","series-title":"Proceedings IJCAI-91","first-page":"268","article-title":"Parallel non-binary planning in polynomial time","author":"B\u00e4ckstr\u00f6m","year":"1991"},{"key":"10.1016\/0004-3702(94)90081-7_BIB4","series-title":"Proceedings IJCAI-93","article-title":"Complexity results for SAS+ planning","author":"B\u00e4ckstr\u00f6m","year":"1993"},{"key":"10.1016\/0004-3702(94)90081-7_BIB5","series-title":"Proceedings IJCAI-91","first-page":"274","article-title":"Complexity results for planning","author":"Bylander","year":"1991"},{"key":"10.1016\/0004-3702(94)90081-7_BIB6","series-title":"Proceedings First International Conference on AI Planning Systems","first-page":"20","article-title":"Complexity results for extended planning","author":"Bylander","year":"1992"},{"key":"10.1016\/0004-3702(94)90081-7_BIB7","series-title":"Proceedings AAAI-92","first-page":"729","article-title":"Complexity results for serial decomposability","author":"Bylander","year":"1992"},{"key":"10.1016\/0004-3702(94)90081-7_BIB8","series-title":"Proceedings AAAI-93","first-page":"480","article-title":"An average case analysis of planning","author":"Bylander","year":"1993"},{"issue":"3","key":"10.1016\/0004-3702(94)90081-7_BIB9_1","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":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)90081-7_BIB9_2","year":"1990"},{"key":"10.1016\/0004-3702(94)90081-7_BIB10","series-title":"Proceedings IJCAI-91","first-page":"331","article-title":"Where the really hard problems are","author":"Cheeseman","year":"1991"},{"key":"10.1016\/0004-3702(94)90081-7_BIB11","series-title":"Proceedings AAAI-91","first-page":"623","article-title":"On the NP-hardness of blocks world","author":"Chenoweth","year":"1991"},{"issue":"3","key":"10.1016\/0004-3702(94)90081-7_BIB12","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0004-3702(88)90087-2","article-title":"Reasoning about partially ordered events","volume":"36","author":"Dean","year":"1988","journal-title":"Artif. Intell."},{"issue":"1","key":"10.1016\/0004-3702(94)90081-7_BIB13_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90061-0","article-title":"Temporal data base management","volume":"32","author":"Dean","year":"1987","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)90081-7_BIB13_2","year":"1990"},{"key":"10.1016\/0004-3702(94)90081-7_BIB14","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0004-3702(91)90007-7","article-title":"Impediments to universal preference-based default theories","volume":"49","author":"Doyle","year":"1991","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)90081-7_BIB15","series-title":"Reasoning about Actions and Plans: Proceedings of the 1986 Workshop","first-page":"189","article-title":"A representation of action and belief for automatic planning systems","author":"Drummond","year":"1987"},{"key":"10.1016\/0004-3702(94)90081-7_BIB16","article-title":"Complexity, decidability, and undecidability results for domain-independent planning","author":"Erol","year":"1991"},{"issue":"3\u20134","key":"10.1016\/0004-3702(94)90081-7_BIB17_1","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":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)90081-7_BIB17_2","year":"1990"},{"key":"10.1016\/0004-3702(94)90081-7_BIB18","author":"Garey","year":"1979"},{"key":"10.1016\/0004-3702(94)90081-7_BIB19_1","first-page":"349","article-title":"Planning","volume":"2","author":"Georgeff","year":"1987"},{"key":"10.1016\/0004-3702(94)90081-7_BIB19_2","year":"1990"},{"issue":"2","key":"10.1016\/0004-3702(94)90081-7_BIB20","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0004-3702(88)90011-2","article-title":"Reasoning about actions I: a possible worlds approach","volume":"35","author":"Ginsberg","year":"1988","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)90081-7_BIB21","series-title":"Proceedings AAAI-91","first-page":"629","article-title":"Complexity results for blocks-world planning","author":"Gupta","year":"1991"},{"key":"10.1016\/0004-3702(94)90081-7_BIB22","series-title":"Artificial and Human Thinking","first-page":"45","article-title":"The frame problem and related problems in artificial intelligence","author":"Hayes","year":"1973"},{"issue":"2","key":"10.1016\/0004-3702(94)90081-7_BIB23","first-page":"61","article-title":"AI planning: systems and techniques","volume":"11","author":"Hendler","year":"1990","journal-title":"AI Mag."},{"issue":"1","key":"10.1016\/0004-3702(94)90081-7_BIB24","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0004-3702(85)90012-8","article-title":"Macro-operators: a weak method for learning","volume":"26","author":"Korf","year":"1985","journal-title":"Artif. Intell."},{"issue":"1","key":"10.1016\/0004-3702(94)90081-7_BIB25_1","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0004-3702(87)90051-8","article-title":"Planning as search: a quantitative approach","volume":"33","author":"Korf","year":"1987","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)90081-7_BIB25_2","year":"1990"},{"issue":"1","key":"10.1016\/0004-3702(94)90081-7_BIB26","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1002\/malq.19670130104","article-title":"The decision problem for a class of first-order formulas in which all disjunctions are binary","volume":"13","author":"Krom","year":"1967","journal-title":"Z. Math. Logik Grundl. Math."},{"issue":"1","key":"10.1016\/0004-3702(94)90081-7_BIB27","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1111\/j.1467-8640.1987.tb00176.x","article-title":"Expressiveness and tractability in knowledge representation and reasoning","volume":"3","author":"Levesque","year":"1987","journal-title":"Comput. Intell."},{"key":"10.1016\/0004-3702(94)90081-7_BIB28_1","series-title":"Reasoning about Actions and Plans: Proceedings of the 1986 Workshop","first-page":"1","article-title":"On the semantics of STRIPS","author":"Lifschitz","year":"1987"},{"key":"10.1016\/0004-3702(94)90081-7_BIB28_2","series-title":"Readings in Planning","year":"1990"},{"key":"10.1016\/0004-3702(94)90081-7_BIB29","series-title":"Proceedings 21st IEEE Annual Symposium on Foundations of Computer Science","first-page":"17","article-title":"An O(\u221a|v|\u00b7|E|) algorithm for finding maximum matching in general graphs","author":"Micali","year":"1980"},{"key":"10.1016\/0004-3702(94)90081-7_BIB30","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0004-3702(92)90007-K","article-title":"Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems","volume":"58","author":"Minton","year":"1992","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)90081-7_BIB31","series-title":"Proceedings AAAI-92","first-page":"459","article-title":"Hard and easy distributions of SAT problems","author":"Mitchell","year":"1992"},{"key":"10.1016\/0004-3702(94)90081-7_BIB32","series-title":"Proceedings AAAI-92","first-page":"466","article-title":"How long will it take?","author":"Musick","year":"1992"},{"key":"10.1016\/0004-3702(94)90081-7_BIB33","author":"Nilsson","year":"1980"},{"key":"10.1016\/0004-3702(94)90081-7_BIB34","series-title":"Proceedings AAAI-86","first-page":"168","article-title":"Finding a shortest solution for the n \u00d7 n extension of the 15-puzzle is intractable","author":"Ratner","year":"1986"},{"key":"10.1016\/0004-3702(94)90081-7_BIB35","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","article-title":"Relationship between nondeterministic and deterministic tape complexities","volume":"4","author":"Savitch","year":"1970","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/0004-3702(94)90081-7_BIB36","author":"Shoham","year":"1988"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0004370294900817?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0004370294900817?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,27]],"date-time":"2019-03-27T00:56:32Z","timestamp":1553648192000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0004370294900817"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":42,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["0004370294900817"],"URL":"https:\/\/doi.org\/10.1016\/0004-3702(94)90081-7","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}