{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:01:08Z","timestamp":1725858068881},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319401881"},{"type":"electronic","value":"9783319401898"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40189-8_33","type":"book-chapter","created":{"date-parts":[[2016,6,13]],"date-time":"2016-06-13T15:34:07Z","timestamp":1465832047000},"page":"323-332","source":"Crossref","is-referenced-by-count":1,"title":["Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic"],"prefix":"10.1007","author":[{"given":"Christian","family":"Gla\u00dfer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,14]]},"reference":[{"key":"33_CR1","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: FOCS, pp. 595\u2013603 (2009)","DOI":"10.1109\/FOCS.2009.32"},{"issue":"5","key":"33_CR2","doi-asserted-by":"crossref","first-page":"1782","DOI":"10.1137\/070708093","volume":"38","author":"L Barto","year":"2009","unstructured":"Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38(5), 1782\u20131802 (2009)","journal-title":"SIAM J. Comput."},{"key":"33_CR3","unstructured":"B\u00e8s, A.: A tribute to Maurice Boffa. Soc. Math. Belgique, 1\u201354 (2002)"},{"key":"33_CR4","doi-asserted-by":"crossref","first-page":"4","DOI":"10.2168\/LMCS-8(4:5)2012","volume":"8","author":"M Bodirsky","year":"2012","unstructured":"Bodirsky, M., Jonsson, P., von Oertzen, T.: Essential convexity and complexity of semi-algebraic constraints. Log. Methods Comput. Sci. 8, 4 (2012). Extended abstract titled Semilinear Program Feasibility at ICALP 2010","journal-title":"Log. Methods Comput. Sci."},{"key":"33_CR5","doi-asserted-by":"crossref","first-page":"2","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. J. ACM 57, 2 (2010)","journal-title":"J. ACM"},{"key":"33_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/978-3-662-47672-7_21","volume-title":"Automata, Languages, and Programming","author":"M Bodirsky","year":"2015","unstructured":"Bodirsky, M., Martin, B., Mottet, A.: Constraint satisfaction problems over the integers with successor. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 256\u2013267. Springer, Heidelberg (2015)"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Pinsker, M.: Schaefer\u2019s theorem for graphs. In: Proceedings of STOC 2011, pp. 655\u2013664 (2011). Preprint of the long version available at arxiv.org\/abs\/1011.2894","DOI":"10.1145\/1993636.1993724"},{"key":"33_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-540-74240-1_12","volume-title":"Fundamentals of Computation Theory","author":"H-G Breunig","year":"2007","unstructured":"Breunig, H.-G.: The complexity of membership problems for circuits over sets of positive numbers. In: Csuhaj-Varj\u00fa, E., \u00c9sik, Z. (eds.) FCT 2007. LNCS, vol. 4639, pp. 125\u2013136. Springer, Heidelberg (2007)"},{"issue":"1","key":"33_CR9","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A Bulatov","year":"2006","unstructured":"Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A Bulatov","year":"2005","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.G.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"33_CR11","unstructured":"Dose, T.: Complexity of constraint satisfaction problems over finite subsets of natural numbers. In: ECCC (2016)"},{"issue":"1\u20132","key":"33_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2003.12.015","volume":"314","author":"T Feder","year":"2004","unstructured":"Feder, T., Madelaine, F.R., Stewart, I.A.: Dichotomies for classes of homomorphism problems involving unary functions. Theor. Comput. Sci. 314(1\u20132), 1\u201343 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR13","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1999","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28, 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"33_CR14","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0062837","volume-title":"The Computational Complexity of Logical Theories","author":"J Ferrante","year":"1979","unstructured":"Ferrante, J., Rackoff, C.W.: The Computational Complexity of Logical Theories. Lecture Notes in Mathematics. Springer, Heidelberg (1979)"},{"issue":"1","key":"33_CR15","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/s00224-008-9144-8","volume":"46","author":"C Gla\u00dfer","year":"2010","unstructured":"Gla\u00dfer, C., Herr, K., Reitwie\u00dfner, C., Travers, S.D., Waldherr, M.: Equivalence problems for circuits over sets of natural numbers. Theor. Comput. Syst. 46(1), 80\u2013103 (2010)","journal-title":"Theor. Comput. Syst."},{"issue":"13","key":"33_CR16","doi-asserted-by":"crossref","first-page":"1394","DOI":"10.1016\/j.dam.2010.04.001","volume":"158","author":"C Gla\u00dfer","year":"2010","unstructured":"Gla\u00dfer, C., Reitwie\u00dfner, C., Travers, S.D., Waldherr, M.: Satisfiability of algebraic circuits over sets of natural numbers. Discrete Appl. Math. 158(13), 1394\u20131403 (2010)","journal-title":"Discrete Appl. Math."},{"key":"33_CR17","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. J. Comb. Theor. Ser. B 48, 92\u2013110 (1990)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"2","key":"33_CR18","first-page":"319","volume":"48","author":"A Jez","year":"2011","unstructured":"Jez, A., Okhotin, A.: Complexity of equations over sets of natural numbers. Theor. Comput. Sci. 48(2), 319\u2013342 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR19","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.ic.2014.05.001","volume":"237","author":"A Jez","year":"2014","unstructured":"Jez, A., Okhotin, A.: Computational completeness of equations over sets of natural numbers. Inform. Comput. 237, 56\u201394 (2014)","journal-title":"Inform. Comput."},{"key":"33_CR20","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.artint.2012.10.001","volume":"195","author":"P Jonsson","year":"2013","unstructured":"Jonsson, P., L\u00f6\u00f6w, T.: Computational complexity of linear constraints over the integers. Artif. Intell. 195, 44\u201362 (2013). An extended abstract appeared at IJCAI 2011","journal-title":"Artif. Intell."},{"issue":"3","key":"33_CR21","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s00037-007-0229-6","volume":"16","author":"P McKenzie","year":"2007","unstructured":"McKenzie, P., Wagner, K.W.: The complexity of membership problems for circuits over sets of natural numbers. Comput. Complex. 16(3), 211\u2013244 (2007). Extended abstract appeared at STACS 2003","journal-title":"Comput. Complex."},{"issue":"3","key":"33_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2267454","volume":"17","author":"A Mostowski","year":"1952","unstructured":"Mostowski, A.: On direct products of theories. J. Symb. Log. 17(3), 1\u201331 (1952)","journal-title":"J. Symb. Log."},{"key":"33_CR23","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"33_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/978-3-642-03073-4_42","volume-title":"Mathematical Theory and Computational Practice","author":"I Pratt-Hartmann","year":"2009","unstructured":"Pratt-Hartmann, I., D\u00fcntsch, I.: Functions definable by arithmetic circuits. In: Ambos-Spies, K., L\u00f6we, B., Merkle, W. (eds.) CiE 2009. LNCS, vol. 5635, pp. 409\u2013418. Springer, Heidelberg (2009)"},{"key":"33_CR25","unstructured":"Presburger, M.: \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen. In: welchem die Addition als einzige Operation hervortritt, Comptes Rendus du I congres de Math\u00e9maticiens des Pays Slaves, pp. 92\u2013101 (1929)"},{"key":"33_CR26","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"33_CR27","unstructured":"Skolem, T.: \u00dcber gewisse satzfunktionen in der arithmetik. Skr, Norske Videnskaps-Akademie i Oslo (1930)"},{"key":"33_CR28","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1016\/S0049-237X(08)71123-6","volume-title":"Handbook of Mathematical Logic","author":"C Smorynski","year":"1977","unstructured":"Smorynski, C.: The incompleteness theorems. In: Barwise, J. (ed.) Handbook of Mathematical Logic, pp. 821\u2013865. North-Holland, Amsterdam (1977)"},{"key":"33_CR29","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: preliminary report. In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, (STOC), pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"issue":"1\u20133","key":"33_CR30","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.tcs.2006.08.017","volume":"369","author":"SD Travers","year":"2006","unstructured":"Travers, S.D.: The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci. 369(1\u20133), 211\u2013229 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR31","doi-asserted-by":"crossref","unstructured":"Wagner, K.: The complexity of problems concerning graphs with regularities. In: MFCS, pp. 544\u2013552 (1984)","DOI":"10.1007\/BFb0030338"},{"issue":"2","key":"33_CR32","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1006\/jcss.2001.1768","volume":"63","author":"K Yang","year":"2001","unstructured":"Yang, K.: Integer circuit evaluation is Pspace-complete. J. Comput. Syst. Sci. 63(2), 288\u2013303 (2001). An extended abstract of appeared at CCC 2000","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Pursuit of the Universal"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40189-8_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T16:17:31Z","timestamp":1498321051000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40189-8_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319401881","9783319401898"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40189-8_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}