{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:09:21Z","timestamp":1743142161140,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319232188"},{"type":"electronic","value":"9783319232195"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23219-5_14","type":"book-chapter","created":{"date-parts":[[2015,8,12]],"date-time":"2015-08-12T10:17:33Z","timestamp":1439374653000},"page":"183-199","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs"],"prefix":"10.1007","author":[{"given":"Peter","family":"Jonsson","sequence":"first","affiliation":[]},{"given":"Victor","family":"Lagerkvist","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,13]]},"reference":[{"issue":"2","key":"14_CR1","first-page":"185","volume":"30","author":"D Berend","year":"2010","unstructured":"Berend, D., Tassa, T.: Improved bounds on Bell numbers and on moments of sums of random variables. Probability and Mathematical Statistics 30(2), 185\u2013205 (2010)","journal-title":"Probability and Mathematical Statistics"},{"issue":"2","key":"14_CR2","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM Journal on Computing 39(2), 546\u2013563 (2009)","journal-title":"SIAM Journal on Computing"},{"unstructured":"Bodirsky, M.: Complexity classification in infinite-domain constraint satisfaction. M\u00e9moire d\u2019habilitation \u00e0 diriger des recherches, Universit\u00e9 Diderot - Paris 7. arXiv:1201.0856 (2012)","key":"14_CR3"},{"key":"14_CR4","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1613\/jair.3747","volume":"45","author":"M Bodirsky","year":"2012","unstructured":"Bodirsky, M., Hils, M.: Tractable set constraints. Journal of Artificial Intelligence Research 45, 731\u2013759 (2012)","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"14_CR5","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/s00224-007-9083-9","volume":"43","author":"M Bodirsky","year":"2008","unstructured":"Bodirsky, M., K\u00e1ra, J.: The complexity of equality constraint languages. Theory of Computing Systems 43(2), 136\u2013158 (2008)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"14_CR6","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/1667053.1667058","volume":"57","author":"M Bodirsky","year":"2010","unstructured":"Bodirsky, M., K\u00e1ra, J.: The complexity of temporal constraint satisfaction problems. Journal of the ACM 57(2), 9:1\u20139:41 (2010)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Mueller, J.K.: The complexity of rooted phylogeny problems. Logical Methods in Computer Science 7(4) (2011)","key":"14_CR7","DOI":"10.2168\/LMCS-7(4:6)2011"},{"issue":"2","key":"14_CR8","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0004-3702(03)00075-4","volume":"149","author":"M Broxvall","year":"2003","unstructured":"Broxvall, M., Jonsson, P.: Point algebras for temporal reasoning: Algorithms and complexity. Artificial Intelligence 149(2), 179\u2013220 (2003)","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"14_CR9","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0004-3702(02)00224-2","volume":"140","author":"M Broxvall","year":"2002","unstructured":"Broxvall, M., Jonsson, P., Renz, J.: Disjunctions, independence, refinements. Artificial Intelligence 140(1\u20132), 153\u2013173 (2002)","journal-title":"Artificial Intelligence"},{"unstructured":"Calabro, C.: The Exponential Complexity of Satisfiability Problems. PhD thesis, University of California, San Diego, CA, USA (2009)","key":"14_CR10"},{"issue":"5","key":"14_CR11","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1145\/355483.355485","volume":"47","author":"D Cohen","year":"2000","unstructured":"Cohen, D., Jeavons, P., Jonsson, P., Koubarakis, M.: Building tractable disjunctive constraints. Journal of the ACM 47(5), 826\u2013853 (2000)","journal-title":"Journal of the ACM"},{"issue":"1","key":"14_CR12","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J.M., Papadimitriou, C.H., Raghavan, P., Sch\u00f6ning, U.: A deterministic $$(2-2\/(k+1))^n$$ algorithm for $$k$$-SAT based on local search. Theoretical Computer Science 289(1), 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"14_CR13","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1093\/comjnl\/32.3.281","volume":"32","author":"B Djokic","year":"1989","unstructured":"Djokic, B., Miyakawa, M., Sekiguchi, S., Semba, I., Stojmenovic, I.: A fast iterative algorithm for generating set partitions. The Computer Journal 32(3), 281\u2013282 (1989)","journal-title":"The Computer Journal"},{"unstructured":"Gaspers, S.: Exponential Time Algorithms - Structures, Measures, and Bounds. VDM (2010)","key":"14_CR14"},{"key":"14_CR15","volume-title":"A Shorter Model Theory","author":"W Hodges","year":"1997","unstructured":"Hodges, W.: A Shorter Model Theory. Cambridge University Press, New York (1997)"},{"issue":"2","key":"14_CR16","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences 62(2), 367\u2013375 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-03898-8_1","volume-title":"Parameterized and Exact Computation","author":"R Impagliazzo","year":"2013","unstructured":"Impagliazzo, R., Paturi, R.: Exact complexity and satisfiability. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 1\u20133. Springer, heidelberg (2013)"},{"issue":"4","key":"14_CR18","doi-asserted-by":"publisher","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? Journal of Computer and System Sciences 63(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"14_CR19","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0004-3702(98)00031-9","volume":"102","author":"P Jonsson","year":"1998","unstructured":"Jonsson, P., B\u00e4ckstr\u00f6m, C.: A unifying approach to temporal constraint reasoning. Artificial Intelligence 102(1), 143\u2013155 (1998)","journal-title":"Artificial Intelligence"},{"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 of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013), pp. 1264\u20131277 (2013)","key":"14_CR20","DOI":"10.1137\/1.9781611973105.92"},{"doi-asserted-by":"crossref","unstructured":"Kanj, I., Szeider, S.: On the subexponential time complexity of CSP. In: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-2013) (2013)","key":"14_CR21","DOI":"10.1609\/aaai.v27i1.8609"},{"issue":"5","key":"14_CR22","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1145\/876638.876639","volume":"50","author":"A Krokhin","year":"2003","unstructured":"Krokhin, A., Jeavons, P., Jonsson, P.: Reasoning about temporal relations: The tractable subalgebras of Allen\u2019s interval algebra. Journal of the ACM 50(5), 591\u2013640 (2003)","journal-title":"Journal of the ACM"},{"unstructured":"Ligozat, G.: Qualitative Spatial and Temporal Reasoning. Wiley-ISTE (2011)","key":"14_CR23"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-540-28633-2_8","volume-title":"PRICAI 2004: Trends in Artificial Intelligence","author":"G Ligozat","year":"2004","unstructured":"Ligozat, G., Renz, J.: What Is a qualitative calculus? a general framework. In: Zhang, C., W. Guesgen, H., Yeap, W.-K. (eds.) PRICAI 2004. LNCS (LNAI), vol. 3157, pp. 53\u201364. Springer, Heidelberg (2004)"},{"unstructured":"Liu, B., Jaffar, J.: Using constraints to model disjunctions in rule-based reasoning. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence, AAAI 1996, Portland, Oregon, vol. 2, pp. 1248\u20131255 (1996)","key":"14_CR25"},{"unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bulletin of EATCS 3(105) (2013)","key":"14_CR26"},{"key":"14_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/3-540-45578-7_25","volume-title":"Principles and Practice of Constraint Programming - CP 2001","author":"K Marriott","year":"2001","unstructured":"Marriott, K., Moulder, P., Stuckey, P.J.: Solving disjunctive constraints for interactive graphical applications. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, p. 361. Springer, Heidelberg (2001)"},{"key":"14_CR28","first-page":"742","volume":"27","author":"H Pr\u00fcfer","year":"1918","unstructured":"Pr\u00fcfer, H.: Neuer beweis eines satzes \u00fcber permutationen. Archiv der Mathematik und Physik 27, 742\u2013744 (1918)","journal-title":"Archiv der Mathematik und Physik"},{"issue":"1","key":"14_CR29","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1613\/jair.872","volume":"15","author":"J Renz","year":"2001","unstructured":"Renz, J., Nebel, B.: Efficient methods for qualitative spatial reasoning. Journal of Artificial Intelligence Research 15(1), 289\u2013318 (2001)","journal-title":"Journal of Artificial Intelligence Research"},{"unstructured":"Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming. Elsevier (2006)","key":"14_CR30"},{"issue":"1","key":"14_CR31","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0004-3702(00)00019-9","volume":"120","author":"K Stergiou","year":"2000","unstructured":"Stergiou, K., Koubarakis, M.: Backtracking algorithms for disjunctions of temporal constraints. Artificial Intelligence 120(1), 81\u2013117 (2000)","journal-title":"Artificial Intelligence"},{"issue":"3","key":"14_CR32","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/BF01931658","volume":"30","author":"I Stojmenovi\u0107","year":"1990","unstructured":"Stojmenovi\u0107, I.: An optimal algorithm for generating equivalence relations on a linear array of processors. BIT Numerical Mathematics 30(3), 424\u2013436 (1990)","journal-title":"BIT Numerical Mathematics"},{"key":"14_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-540-79723-4_18","volume-title":"Parameterized and Exact Computation","author":"P Traxler","year":"2008","unstructured":"Traxler, P.: The time complexity of constraint satisfaction. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 190\u2013201. Springer, Heidelberg (2008)"},{"unstructured":"Vilain, M.B., Kautz, H.A.: Constraint propagation algorithms for temporal reasoning. In: Proceedings of the 5th National Conference on Artificial Intelligence (AAAI 1986), pp. 377\u2013382 (1986)","key":"14_CR34"},{"issue":"2","key":"14_CR35","doi-asserted-by":"publisher","first-page":"4948","DOI":"10.1023\/A:1025645221773","volume":"118","author":"M Vsemirnov","year":"2003","unstructured":"Vsemirnov, M., Hirsch, E., Dantsin, E., Ivanov, S.: Algorithms for SAT and upper bounds on their complexity. Journal of Mathematical Sciences 118(2), 4948\u20134962 (2003)","journal-title":"Journal of Mathematical Sciences"},{"key":"14_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka! You Shrink!","author":"G Woeginger","year":"2000","unstructured":"Woeginger, G.: Exact algorithms for NP-hard problems: a survey. In: Juenger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka! You Shrink!. LNCS, vol. 2570, pp. 185\u2013207. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23219-5_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T14:51:00Z","timestamp":1676472660000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23219-5_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319232188","9783319232195"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23219-5_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"13 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}