{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:29:32Z","timestamp":1725564572852},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212362"},{"type":"electronic","value":"9783540247494"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24749-4_15","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T15:01:54Z","timestamp":1283958114000},"page":"164-175","source":"Crossref","is-referenced-by-count":7,"title":["The Complexity of Boolean Constraint Isomorphism"],"prefix":"10.1007","author":[{"given":"Elmar","family":"B\u00f6hler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edith","family":"Hemaspaandra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steffen","family":"Reith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","first-page":"743","volume-title":"Proceedings 43rd Symposium on Foundations of Computer Science","author":"V. Arvind","year":"2002","unstructured":"Arvind, V., Kurur, P.: Graph isomorphism is in SPP. In: Proceedings 43rd Symposium on Foundations of Computer Science, pp. 743\u2013750. IEEE Computer Society Press, Los Alamitos (2002)"},{"issue":"3","key":"15_CR2","doi-asserted-by":"publisher","first-page":"990","DOI":"10.1137\/S0097539798343647","volume":"30","author":"M. Agrawal","year":"2000","unstructured":"Agrawal, M., Thierauf, T.: The formula isomorphism problem. SIAM Journal on Computing\u00a030(3), 990\u20131009 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/3-540-45793-3_28","volume-title":"Computer Science Logic","author":"E. B\u00f6hler","year":"2002","unstructured":"B\u00f6hler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: Equivalence and isomorphism for Boolean constraint satisfaction. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol.\u00a02471, pp. 412\u2013426. Springer, Heidelberg (2002)"},{"key":"15_CR4","first-page":"667","volume-title":"Proceedings 33rd Symposium on Theory of Computing","author":"A. Bulatov","year":"2001","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: The complexity of maximal constraint languages. In: Proceedings 33rd Symposium on Theory of Computing, pp. 667\u2013674. ACM Press, New York (2001)"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s002240000109","volume":"31","author":"B. Borchert","year":"1998","unstructured":"Borchert, B., Ranjan, D., Stephan, F.: On the computational complexity of some classical equivalence relations on Boolean functions. Theory of Computing Systems\u00a031, 679\u2013693 (1998)","journal-title":"Theory of Computing Systems"},{"key":"15_CR6","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":"15_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Information and Computation\u00a0125, 1\u201312 (1996)","journal-title":"Information and Computation"},{"issue":"6","key":"15_CR8","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1051\/ita\/1997310604991","volume":"31","author":"N. Creignou","year":"1997","unstructured":"Creignou, N., H\u00e9brard, J.-J.: On generating all solutions of generalized satisfiability problems. Informatique Th\u00e9orique et Applications\/Theoretical Informatics and Applications\u00a031(6), 499\u2013511 (1997)","journal-title":"Informatique Th\u00e9orique et Applications\/Theoretical Informatics and Applications"},{"key":"15_CR9","series-title":"Monographs on Discrete Applied Mathematics","doi-asserted-by":"publisher","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. Monographs on Discrete Applied Mathematics. SIAM, Philadelphia (2001)"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N. Creignou","year":"1995","unstructured":"Creignou, N.: A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences\u00a051, 511\u2013522 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR11","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)"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/3-540-36494-3_40","volume-title":"STACS 2003","author":"A. Durand","year":"2003","unstructured":"Durand, A., Hermann, M.: The inference problem for propositional circumscription of affine formulas is coNP-complete. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 451\u2013462. Springer, Heidelberg (2003)"},{"issue":"1","key":"15_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadis SNP and constraint satisfaction: a study through Datalog and group theory. SIAM Journal on Computing\u00a028(1), 57\u2013104 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., Cooper, M.C.: Constraints, consistency and closure. Artificial Intelligence\u00a0101, 251\u2013265 (1998)","journal-title":"Artificial Intelligence"},{"issue":"4","key":"15_CR15","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1023\/A:1009890709297","volume":"4","author":"P. Jeavons","year":"1999","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: How to determine the expressive power of constraints. Constraints\u00a04, 113\u2013131 (1999)","journal-title":"Constraints"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/3-540-48321-7_27","volume-title":"Fundamentals of Computation Theory","author":"L. Juban","year":"1999","unstructured":"Juban, L.: Dichotomy theorem for generalized unique satisfiability problem. In: Ciobanu, G., P\u0103un, G. (eds.) FCT 1999. LNCS, vol.\u00a01684, pp. 327\u2013337. Springer, Heidelberg (1999)"},{"key":"15_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/3-540-44693-1_36","volume-title":"STACS 2001","author":"L. Kirousis","year":"2001","unstructured":"Kirousis, L., Kolaitis, P.: The complexity of minimal satisfiability problems. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 407\u2013418. Springer, Heidelberg (2001)"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Kirousis, L., Kolaitis, P.: A dichotomy in the complexity of propositional circumscription. In: Proceedings 16th Logic in Computer Science, pp. 71\u201380 (2001)","DOI":"10.1109\/LICS.2001.932484"},{"key":"15_CR20","unstructured":"Kolaitis, P.: Constraint satisfaction, databases, and logic. In: Proceedings 18th International Joint Conference on Artificial Intelligence, pp. 1587\u20131595 (2003)"},{"issue":"1","key":"15_CR21","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1137\/S0097539795285114","volume":"28","author":"D. Kavvadias","year":"1998","unstructured":"Kavvadias, D., Sideri, M.: The inverse satisfiability problem. SIAM Journal of Computing\u00a028(1), 152\u2013163 (1998)","journal-title":"SIAM Journal of Computing"},{"key":"15_CR22","volume-title":"Progress in Theoretical Computer Science","author":"J. K\u00f6bler","year":"1993","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: its Structural Complexity. In: Progress in Theoretical Computer Science, Birkh\u00e4user, Basel (1993)"},{"issue":"6","key":"15_CR23","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2001","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.: The approximability of constraint satisfaction problems. SIAM Journal on Computing\u00a030(6), 1863\u20131920 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Kolaitis, P., Vardi, M.: Conjunctive-query containment and constraint satisfaction. In: Proceedings 17th ACM Symposium on Principles of Database Systems, pp. 205\u2013213 (1998)","DOI":"10.1145\/275487.275511"},{"key":"15_CR25","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. Ladner","year":"1975","unstructured":"Ladner, R.: On the structure of polynomial-time reducibility. Journal of the ACM\u00a022, 155\u2013171 (1975)","journal-title":"Journal of the ACM"},{"key":"15_CR26","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Information Sciences\u00a07, 95\u2013132 (1974)","journal-title":"Information Sciences"},{"issue":"1","key":"15_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0890-5401(03)00092-0","volume":"186","author":"S. Reith","year":"2003","unstructured":"Reith, S., Vollmer, H.: Optimal satisfiability for propositional calculi and constraint satisfaction problems. Information and Computation\u00a0186(1), 1\u201319 (2003)","journal-title":"Information and Computation"},{"key":"15_CR28","first-page":"216","volume-title":"Proccedings 10th Symposium on Theory of Computing","author":"T. Schaefer","year":"1978","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proccedings 10th Symposium on Theory of Computing, pp. 216\u2013226. ACM Press, New York (1978)"},{"key":"15_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45303-2","volume-title":"The Computational Complexity of Equivalence and Isomorphism Problems","author":"T. Thierauf","year":"2000","unstructured":"Thierauf, T.: The Computational Complexity of Equivalence and Isomorphism Problems. LNCS, vol.\u00a01852. Springer, Heidelberg (2000)"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"Tor\u00e1n, J.: On the hardness of graph isomorphism. In: Proceedings 41st Foundations of Computer Science, pp. 180\u2013186 (2000)","DOI":"10.1109\/SFCS.2000.892080"},{"key":"15_CR31","first-page":"551","volume-title":"Proceedings 30th Symposium on Theory of Computing","author":"U. Zwick","year":"1998","unstructured":"Zwick, U.: Finding almost-satisfying assignments. In: Proceedings 30th Symposium on Theory of Computing, pp. 551\u2013560. ACM Press, New York (1998)"}],"container-title":["Lecture Notes in Computer Science","STACS 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24749-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T01:31:41Z","timestamp":1553045501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24749-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212362","9783540247494"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24749-4_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}