{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:19:55Z","timestamp":1725560395468},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540287025"},{"type":"electronic","value":"9783540318675"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11549345_8","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T14:05:47Z","timestamp":1127829947000},"page":"71-82","source":"Crossref","is-referenced-by-count":19,"title":["The Complexity of Satisfiability Problems: Refining Schaefer\u2019s Theorem"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Michael","family":"Bauland","sequence":"additional","affiliation":[]},{"given":"Neil","family":"Immerman","sequence":"additional","affiliation":[]},{"given":"Henning","family":"Schnoor","sequence":"additional","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1137\/S0097539794270236","volume":"26","author":"E. Allender","year":"1997","unstructured":"Allender, E., Balcazar, J., Immerman, N.: A first-order isomorphism theorem. SIAM Journal on Computing\u00a026, 557\u2013567 (1997)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"8_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/PL00001603","volume":"9","author":"C. Alvarez","year":"2000","unstructured":"Alvarez, C., Greenlaw, R.: A compendium of problems complete for symmetric logarithmic space. Computational Complexity\u00a09(2), 123\u2013145 (2000)","journal-title":"Computational Complexity"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/3-540-45294-X_6","volume-title":"FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science","author":"M. Agrawal","year":"2001","unstructured":"Agrawal, M.: The first-order isomorphism theorem. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS 2001. LNCS, vol.\u00a02245, pp. 58\u201369. Springer, Heidelberg (2001)"},{"issue":"4","key":"8_CR4","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/954092.954101","volume":"34","author":"E. B\u00f6hler","year":"2003","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part I: Post\u2019s lattice with applications to complexity theory. SIGACT News\u00a034(4), 38\u201352 (2003)","journal-title":"SIGACT News"},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/970831.970840","volume":"35","author":"E. B\u00f6hler","year":"2004","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part II: Constraint satisfaction problems. SIGACT News\u00a035(1), 22\u201335 (2004)","journal-title":"SIGACT News"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"B\u00f6hler, E., Reith, S., Schnoor, H., Vollmer, H.: Simple bases for Boolean co-clones. Information Processing Letters (2005) (to appear)","DOI":"10.1016\/j.ipl.2005.06.003"},{"key":"8_CR7","first-page":"649","volume-title":"Proceedings 43rd Symposium on Foundations of Computer Science","author":"A. Bulatov","year":"2002","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings 43rd Symposium on Foundations of Computer Science, pp. 649\u2013658. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"8_CR8","volume-title":"Monographs on Discrete Applied Mathematics","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. In: Monographs on Discrete Applied Mathematics, SIAM, Philadelphia (2001)"},{"key":"8_CR9","unstructured":"Dalmau, V.: Computational complexity of problems over generalized formulas. PhD thesis, Department de Llenguatges i Sistemes Inform\u00e0tica, Universitat Polit\u00e9cnica de Catalunya (2000)"},{"issue":"4","key":"8_CR10","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P.G. Jeavons","year":"1997","unstructured":"Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1145\/244795.244798","volume":"19","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Pure versus impure Lisp. ACM Transactions on Programming Languages and Systems\u00a019, 223\u2013238 (1997)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"8_CR12","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"8_CR13","unstructured":"Reith, S.: Generalized Satisfiability Problems. PhD thesis, Fachbereich Mathematik und Informatik, Universit\u00e4t W\u00fcrzburg (2001)"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1145\/1060590.1060647","volume-title":"STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, New York, NY, USA, pp. 376\u2013385. ACM Press, New York (2005)"},{"key":"8_CR15","first-page":"216","volume-title":"Proceedings 10th Symposium on Theory of Computing","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th Symposium on Theory of Computing, pp. 216\u2013226. ACM Press, New York (1978)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11549345_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:58:37Z","timestamp":1619506717000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11549345_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540287025","9783540318675"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11549345_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}