{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T05:06:18Z","timestamp":1737522378331,"version":"3.33.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,9,28]],"date-time":"2007-09-28T00:00:00Z","timestamp":1190937600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,2]]},"DOI":"10.1007\/s00224-007-9003-z","type":"journal-article","created":{"date-parts":[[2007,9,27]],"date-time":"2007-09-27T18:28:30Z","timestamp":1190917710000},"page":"239-255","source":"Crossref","is-referenced-by-count":6,"title":["Complexity of Clausal Constraints Over Chains"],"prefix":"10.1007","volume":"42","author":[{"given":"Nadia","family":"Creignou","sequence":"first","affiliation":[]},{"given":"Miki","family":"Hermann","sequence":"additional","affiliation":[]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[]},{"given":"Gernot","family":"Salzer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,9,28]]},"reference":[{"key":"9003_CR1","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1016\/B978-044450813-3\/50022-9","volume-title":"Handbook of Automated Reasoning","author":"M. Baaz","year":"2001","unstructured":"Baaz, M., Ferm\u00fcller, C.G., Salzer, G.: Automated deduction for many-valued logics. In: Robinson, J.A., Voronkov, A. (eds.) Handbook of Automated Reasoning, vol. 2, pp. 1355\u20131402. Elsevier, Amsterdam (2001). Chap. 20"},{"key":"9003_CR2","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A\u00a0dichotomy theorem for constraints on a\u00a0three-element set. In: Proceedings 43rd Symposium on Foundations of Computer Science (FOCS 2002), Vancouver (British Columbia, Canada), November 2002, pp. 649\u2013658","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"9003_CR3","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: Tractable conservative constraint satisfaction problems. In: Proceedings 18th IEEE Symposium on Logic in Computer Science (LICS 2003), Ottawa (Canada), June 2003, pp. 321\u2013330","DOI":"10.1109\/LICS.2003.1210072"},{"key":"9003_CR4","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Constraint satisfaction problems and finite algebras. Technical Report TR-4-99, Oxford University Computing Laboratory (1999)"},{"issue":"3","key":"9003_CR5","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J.\u00a0Comput. 34(3), 720\u2013742 (2005)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"5","key":"9003_CR6","doi-asserted-by":"crossref","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. J.\u00a0Assoc. Comput. Mach. 47(5), 826\u2013853 (2000)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"key":"9003_CR7","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a07. SIAM, Philadelphia (2001)"},{"key":"9003_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1007\/3-540-45465-9_36","volume-title":"Proceedings 29th International Conference on Automata, Languages, and Programming (ICALP 2002). Malaga (Spain)","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V.: Constraint satisfaction problems in non-deterministic logarithmic space. In: Widmayer, P., Triguero Ruiz, F., Morales Bueno, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) Proceedings 29th International Conference on Automata, Languages, and Programming (ICALP 2002). Malaga (Spain). Lecture Notes in Computer Science, vol. 2380, pp. 414\u2013425. Springer, New York (2002)"},{"issue":"1","key":"9003_CR9","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a\u00a0study through Datalog and group theory. SIAM J.\u00a0Comput. 28(1), 57\u2013104 (1998)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9003_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1007\/978-3-540-25984-8_17","volume-title":"Proceedings 2nd International Joint Conference on Automated Reasoning (IJCAR\u201904), Cork (Ireland)","author":"A. Gil","year":"2004","unstructured":"Gil, A., Hermann, M., Salzer, G., Zanuttini, B.: Efficient algorithms for constraint description problems over finite totally ordered domains. In: Basin, D., Rusinowitch, M. (eds.) Proceedings 2nd International Joint Conference on Automated Reasoning (IJCAR\u201904), Cork (Ireland). Lecture Notes in Computer Science, vol. 3097, pp. 244\u2013258. Springer, New York (2004)"},{"key":"9003_CR11","doi-asserted-by":"crossref","unstructured":"H\u00e4hnle, R.: Complexity of many-valued logics. In: Proceedings 31st IEEE International Symposium on Multiple-Valued Logic (ISMVL 2001), Warsaw (Poland), pp. 137\u2013148. IEEE Computer Society (May 2001)","DOI":"10.1109\/ISMVL.2001.924565"},{"key":"9003_CR12","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P. Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"issue":"2","key":"9003_CR13","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"P. Jeavons","year":"1995","unstructured":"Jeavons, P., Cooper, M.C.: Tractable constraints on ordered domains. Artif. Intell. 79(2), 327\u2013339 (1995)","journal-title":"Artif. Intell."},{"issue":"2","key":"9003_CR14","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P.G. Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J.\u00a0Comput. Syst. Sci. 61(2), 302\u2013332 (2000)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"1","key":"9003_CR15","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J.\u00a0Assoc. Comput. Mach. 22(1), 155\u2013171 (1975)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"key":"9003_CR16","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th Symposium on Theory of Computing (STOC\u201978), San Diego (California, USA), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9003-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9003-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9003-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T07:22:33Z","timestamp":1737444153000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9003-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,28]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["9003"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9003-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2007,9,28]]}}}