{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:10:37Z","timestamp":1737436237952,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540442400"},{"type":"electronic","value":"9783540457930"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45793-3_28","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T12:03:26Z","timestamp":1187265806000},"page":"412-426","source":"Crossref","is-referenced-by-count":17,"title":["Equivalence and Isomorphism for Boolean Constraint Satisfaction"],"prefix":"10.1007","author":[{"given":"Elmar","family":"B\u00f6hler","sequence":"first","affiliation":[]},{"given":"Edith","family":"Hemaspaandra","sequence":"additional","affiliation":[]},{"given":"Steffen","family":"Reith","sequence":"additional","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,9,2]]},"reference":[{"issue":"3","key":"28_CR1","doi-asserted-by":"publisher","first-page":"990","DOI":"10.1137\/S0097539798343647","volume":"30","author":"M. Agrawal","year":"2000","unstructured":"M. Agrawal and T. Thierauf. The formula isomorphism problem. SIAM Journal on Computing, 30(3):990\u20131009, 2000.","journal-title":"SIAM Journal on Computing"},{"unstructured":"K.S. Booth and C. J. Colbourn. Problems polynomially equivalent to graph isomorphism. Technical Report CS-77-01, University of Waterloo, 1979.","key":"28_CR2"},{"issue":"2","key":"28_CR3","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0890-5401(91)90075-D","volume":"90","author":"S. Buss","year":"1991","unstructured":"S. Buss and L. Hay. On truth-table reducibility to SAT. Information and Computation, 90(2):86\u2013102, 1991.","journal-title":"Information and Computation"},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s002240000109","volume":"31","author":"B. Borchert","year":"1998","unstructured":"B. Borchert, D. Ranjan, and F. Stephan. On the computational complexity of some classical equivalence relations on Boolean functions. Theory of Computing Systems, 31:679\u2013693, 1998.","journal-title":"Theory of Computing Systems"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"N. Creignou and M. Hermann. Complexity of generalized satisfiability counting problems. Information and Computation, 125:1\u201312, 1996.","journal-title":"Information and Computation"},{"issue":"6","key":"28_CR6","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1051\/ita\/1997310604991","volume":"31","author":"N. Creignou","year":"1997","unstructured":"N. Creignou and J.-J. H\u00e9brard. On generating all solutions of generalized satisfiability problems. Informatique Th\u00e9orique et Applications \/Theoretical Informatics and Applications, 31(6):499\u2013511, 1997.","journal-title":"Informatique Th\u00e9orique et Applications \/Theoretical Informatics and Applications"},{"doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems. Monographs on Discrete Applied Mathematics. SIAM, 2000.","key":"28_CR7","DOI":"10.1137\/1.9780898718546"},{"key":"28_CR8","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N. Creignou","year":"1995","unstructured":"N. Creignou. A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences, 51:511\u2013522, 1995.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"28_CR9","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1137\/S0097539793250299","volume":"24","author":"T. Eiter","year":"1995","unstructured":"T. Eiter and G. Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6):1278\u20131304, 1995.","journal-title":"SIAM Journal on Computing"},{"unstructured":"M. Fontet. Automorphismes de graphes et planarit\u00e9. In Asterisque, pages 73\u201390. 1976.","key":"28_CR10"},{"issue":"3","key":"28_CR11","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. Hemachandra","year":"1989","unstructured":"L. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299\u2013322, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR12","first-page":"407","volume":"2010","author":"L. M. Kirousis","year":"2001","unstructured":"L. M. Kirousis and P. G. Kolaitis. The complexity of minimal satisfiability problems. In Proceedings 18th Symposium on Theoretical Aspects of Computer Science, volume 2010, pages 407\u2013418. Springer Verlag, 2001.","journal-title":"Proceedings 18th Symposium on Theoretical Aspects of Computer Science"},{"doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and J. Tor\u00e1n. The Graph Isomorphism Problem: its Structureal Complexity. Progress in Theoretical Computer Science. Birkh\u00e4user, 1993.","key":"28_CR13","DOI":"10.1007\/978-1-4612-0333-9"},{"issue":"6","key":"28_CR14","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2001","unstructured":"S. Khanna, M. Sudan, L. Trevisan, and D. Williamson. The approximability of constraint satisfaction problems. SIAM Journal on Computing, 30(6):1863\u20131920, 2001.","journal-title":"SIAM Journal on Computing"},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. Ladner","year":"1975","unstructured":"R. Ladner. On the structure of polynomial-time reducibility. Journal of the ACM, 22:155\u2013171, 1975.","journal-title":"Journal of the ACM"},{"unstructured":"E. L. Post. Two-valued iterative systems of mathematical logic. In Annals of Math. Studies, volume 5. Princeton University Press, 1941.","key":"28_CR16"},{"key":"28_CR17","series-title":"Lect Notes Comput Sci","first-page":"269","volume-title":"Proceedings 6th GI Conference on Theoretical Computer Science","author":"C. Papadimitriou","year":"1983","unstructured":"C. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings 6th GI Conference on Theoretical Computer Science, volume 145 of Lecture Notes in Computer Science, pages 269\u2013276. Springer Verlag, 1983."},{"unstructured":"S. Reith. Generalized Satisfiability Problems. PhD thesis, University of W\u00fcrzburg, 2001.","key":"28_CR18"},{"key":"28_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1007\/3-540-44612-5_59","volume-title":"Proceedings 25thInternational Symposium on Mathematical Foundations of Computer Science","author":"S. Reith","year":"2000","unstructured":"S. Reith and H. Vollmer. Optimal satisfiability for propositional calculi and constraint satisfaction problems. In Proceedings 25th International Symposium on Mathematical Foundations of Computer Science, volume 1893 of Lecture Notes in Computer Science, pages 640\u2013649. Springer Verlag, 2000."},{"unstructured":"S. Reith and K.W. Wagner. The complexity of problems defined by Boolean circuits. Technical Report 255, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, 2000. To appear in Proceedings International Conference Mathematical Foundation of Informatics, Hanoi, October 25\u201328, 1999.","key":"28_CR20"},{"doi-asserted-by":"crossref","unstructured":"T. J. Schaefer. The complexity of satisfiability problems. In Proccedings 10th Symposium on Theory of Computing, pages 216\u2013226. ACM Press, 1978","key":"28_CR21","DOI":"10.1145\/800133.804350"},{"doi-asserted-by":"crossref","unstructured":"J. Tor\u00e1n. On the hardness of graph isomorphism. In Proceedings 41st Foundations of Computer Science, pages 180\u2013186, 2000.","key":"28_CR22","DOI":"10.1109\/SFCS.2000.892080"},{"issue":"5","key":"28_CR23","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"K. Wagner. Bounded query classes. SIAM Journal on Computing, 19(5):833\u2013846, 1990.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45793-3_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T11:39:38Z","timestamp":1737373178000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45793-3_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540442400","9783540457930"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-45793-3_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}