{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T05:25:26Z","timestamp":1754112326721},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,7,29]],"date-time":"2016-07-29T00:00:00Z","timestamp":1469750400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100010752","name":"National Graduate School in Computer Science (CUGS), Sweden","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010752","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100010752","name":"National Graduate School in Computer Science (CUGS), Sweden","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010752","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Swedish Research Council (VR)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2016,10]]},"DOI":"10.1007\/s10472-016-9521-y","type":"journal-article","created":{"date-parts":[[2016,7,29]],"date-time":"2016-07-29T03:30:29Z","timestamp":1469763029000},"page":"157-175","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Refining complexity analyses in planning by exploiting the exponential time hypothesis"],"prefix":"10.1007","volume":"78","author":[{"given":"Meysam","family":"Aghighi","sequence":"first","affiliation":[]},{"given":"Christer","family":"B\u00e4ckstr\u00f6m","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[]},{"given":"Simon","family":"St\u00e5hlberg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,7,29]]},"reference":[{"key":"9521_CR1","doi-asserted-by":"crossref","unstructured":"B\u00e4ckstr\u00f6m, C., Jonsson, P.: All PSPACE-complete planning problems are equal but some are more equal than others. In: Proceedings 4th Annual Symposium on Combinatorial Search (SOCS-11), pp 10\u201317, Barcelona, Spain (2011)","DOI":"10.1609\/socs.v2i1.18186"},{"key":"9521_CR2","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1613\/jair.3534","volume":"44","author":"C B\u00e4ckstr\u00f6m","year":"2012","unstructured":"B\u00e4ckstr\u00f6m, C., Jonsson, P.: Algorithms and limits for compact plan representations. J. Artif. Intell. Res. 44, 141\u2013177 (2012)","journal-title":"J. Artif. Intell. Res."},{"key":"9521_CR3","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1613\/jair.3968","volume":"47","author":"C B\u00e4ckstr\u00f6m","year":"2013","unstructured":"B\u00e4ckstr\u00f6m, C., Jonsson, P.: A refined view of causal graphs and component sizes: SP-closed graph classes and beyond. J. Artif. Intell. Res. 47, 575\u2013611 (2013)","journal-title":"J. Artif. Intell. Res."},{"key":"9521_CR4","doi-asserted-by":"crossref","unstructured":"B\u00e4ckstr\u00f6m, C., Jonsson, P., Ordyniak, S., Szeider, S.: A complete parameterized complexity analysis of bounded planning. J. Comput. Syst. Sci., 1311\u20131332 (2015)","DOI":"10.1016\/j.jcss.2015.04.002"},{"key":"9521_CR5","doi-asserted-by":"crossref","unstructured":"B\u00e4ckstr\u00f6m, C., Jonsson, P., St\u00e5hlberg, S.: Fast detection of unsolvable planning instances using local consistency. In: Proceedings 6th Annual Symposium on Combinatorial Search (SOCS-13), pp 29\u201337, WA, USA (2013)","DOI":"10.1609\/socs.v4i1.18294"},{"key":"9521_CR6","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1111\/j.1467-8640.1995.tb00052.x","volume":"11","author":"C B\u00e4ckstr\u00f6m","year":"1995","unstructured":"B\u00e4ckstr\u00f6m, C., Nebel, B.: Complexity results for SAS + planning. Comput. Intell. 11, 625\u2013656 (1995)","journal-title":"Comput. Intell."},{"key":"9521_CR7","doi-asserted-by":"crossref","unstructured":"Bogomolov, S., Magazzeni, D., Podelski, A., Wehrle, M.: Planning as model checking in hybrid domains. In: Proceedings 28th AAAI Conference on Artificial Intelligence (AAAI-14), pp 2228\u20132234, QC, Canada (2014)","DOI":"10.1609\/aaai.v28i1.9037"},{"issue":"1-2","key":"9521_CR8","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0004-3702(94)90081-7","volume":"69","author":"T Bylander","year":"1994","unstructured":"Bylander, T.: The computational complexity of propositional STRIPS planning. Artif. Intell. 69(1-2), 165\u2013204 (1994)","journal-title":"Artif. Intell."},{"issue":"2","key":"9521_CR9","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216\u2013231 (2005)","journal-title":"Inf. Comput."},{"issue":"8","key":"9521_CR10","doi-asserted-by":"crossref","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9521_CR11","doi-asserted-by":"crossref","first-page":"1228","DOI":"10.1137\/070687153","volume":"37","author":"Y Chen","year":"2007","unstructured":"Chen, Y., Grohe, M.: An isomorphism between subexponential and parameterized complexity theory. SIAM J. Comput. 37(4), 1228\u20131258 (2007)","journal-title":"SIAM J. Comput."},{"key":"9521_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness (1979)"},{"issue":"2","key":"9521_CR13","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/S0004-3702(02)00364-8","volume":"143","author":"M Helmert","year":"2003","unstructured":"Helmert, M.: Complexity results for standard benchmark domains in planning. Artif. Intell. 143(2), 219\u2013262 (2003)","journal-title":"Artif. Intell."},{"key":"9521_CR14","unstructured":"Hoffmann, J., Kissmann, P., Torralba, \u00c1.: Distance? Who cares? Tailoring merge-and-shrink heuristics to detect unsolvability. In: Proceedings 21st European Conference on Artificial Intelligence (ECAI-2014), pp 441\u2013446 (2014)"},{"issue":"2","key":"9521_CR15","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9521_CR16","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3-4","key":"9521_CR17","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1023\/A:1018995620232","volume":"22","author":"P Jonsson","year":"1998","unstructured":"Jonsson, P., B\u00e4ckstr\u00f6m, C.: Tractable plan existence does not imply tractable plan generation. Ann. Math. Artif. Intell. 22(3-4), 281\u2013296 (1998)","journal-title":"Ann. Math. Artif. Intell."},{"key":"9521_CR18","doi-asserted-by":"crossref","unstructured":"Jonsson, P., Lagerkvist, V., Nordh, G., Zanuttini, B.: Complexity of SAT problems, clone theory and the exponential time hypothesis. In: Proceedings 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-13), pp 1264\u20131277, LA, USA (2013)","DOI":"10.1137\/1.9781611973105.92"},{"key":"9521_CR19","doi-asserted-by":"crossref","unstructured":"Kanj, I., Szeider, S.: On the subexponential time complexity of CSP. In: Proceedings 27th AAAI Conference on Artificial Intelligence (AAAI-13), pp 459\u2013465, WA, USA (2013)","DOI":"10.1609\/aaai.v27i1.8609"},{"issue":"4","key":"9521_CR20","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/BF00297511","volume":"17","author":"H Levesque","year":"1988","unstructured":"Levesque, H.: Logic and the complexity of reasoning. J. Philos. Log. 17(4), 355\u2013389 (1988)","journal-title":"J. Philos. Log."},{"key":"9521_CR21","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.artint.2015.01.004","volume":"223","author":"C Linares L\u00f3pez","year":"2015","unstructured":"Linares L\u00f3pez, C., Celorrio, S.J., Olaya, A.G.: The deterministic part of the seventh international planning competition. Artif. Intell. 223, 82\u2013119 (2015)","journal-title":"Artif. Intell."},{"key":"9521_CR22","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. B. EATCS 105, 41\u201372 (2011)","journal-title":"B. EATCS"},{"key":"9521_CR23","doi-asserted-by":"crossref","unstructured":"Marx, D.: On the optiMality of planar and geometric approximation schemes. In: Proceedings 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS-07), pp 338\u2013348, RI, USA (2007)","DOI":"10.1109\/FOCS.2007.26"},{"key":"9521_CR24","unstructured":"Rintanen, J.: Generation of hard solvable planning problems. Technical report TR-CS-12-03, College of Engineering and Computer Science, The Australian National University, Canberra, Australia (2012)"},{"key":"9521_CR25","doi-asserted-by":"crossref","unstructured":"Santhanam, R., Srinivasan, S.: On the limits of sparsification. In: Proceeding of the 39th International Colloquium on Automata, Languages, and Programming (ICALP-12), pp 774\u2013785, Warwick, UK (2012)","DOI":"10.1007\/978-3-642-31594-7_65"},{"issue":"2","key":"9521_CR26","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W Savitch","year":"1970","unstructured":"Savitch, W.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"9521_CR27","unstructured":"Sipser, M.: Introduction to the theory of computation, 2nd edn. Thomson Course Technology (2006)"},{"issue":"11","key":"9521_CR28","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1145\/188280.188379","volume":"37","author":"RE Stearns","year":"1994","unstructured":"Stearns, R.E.: Turing award lecture: It\u2019s time to reconsider time. Commun. ACM 37(11), 95\u201399 (1994)","journal-title":"Commun. ACM"},{"issue":"1","key":"9521_CR29","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/602382.602409","volume":"50","author":"RE Stearns","year":"2003","unstructured":"Stearns, R.E.: Deterministic versus nondeterministic time and lower bound problems. J. ACM 50(1), 91\u201395 (2003)","journal-title":"J. ACM"},{"key":"9521_CR30","doi-asserted-by":"crossref","unstructured":"Stearns, R.E., Hunt, III, H.B.: Power indices and easier hard problems. Math. Syst. Theory 23(4), 209\u2013225 (1990)","DOI":"10.1007\/BF02090776"},{"key":"9521_CR31","doi-asserted-by":"crossref","unstructured":"Traxler, P.: The time complexity of constraint satisfaction. In: Proceeding of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC-08), pp 190\u2013201, BC, Canada (2008)","DOI":"10.1007\/978-3-540-79723-4_18"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-016-9521-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-016-9521-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-016-9521-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,19]],"date-time":"2023-08-19T11:43:20Z","timestamp":1692445400000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-016-9521-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,29]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["9521"],"URL":"https:\/\/doi.org\/10.1007\/s10472-016-9521-y","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,29]]}}}