{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T04:00:15Z","timestamp":1649131215208},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T00:00:00Z","timestamp":1189728000000},"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":[[2009,1]]},"DOI":"10.1007\/s00224-007-9038-1","type":"journal-article","created":{"date-parts":[[2007,9,13]],"date-time":"2007-09-13T14:27:47Z","timestamp":1189693667000},"page":"117-139","source":"Crossref","is-referenced-by-count":0,"title":["Isomorphic Implication"],"prefix":"10.1007","volume":"44","author":[{"given":"Michael","family":"Bauland","sequence":"first","affiliation":[]},{"given":"Edith","family":"Hemaspaandra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,9,14]]},"reference":[{"issue":"3","key":"9038_CR1","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1137\/S0097539798343647","volume":"30","author":"M. Agrawal","year":"2000","unstructured":"Agrawal, M., Thierauf, T.: The formula isomorphism problem. SIAM J. Comput. 30(3), 990\u20131009 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9038_CR2","doi-asserted-by":"crossref","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 35(1), 22\u201335 (2004)","journal-title":"SIGACT News"},{"issue":"1","key":"9038_CR3","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0890-5401(91)90075-D","volume":"91","author":"S. Buss","year":"1991","unstructured":"Buss, S., Hay, L.: On truth-table reducibility to SAT. Inf. Comput. 91(1), 86\u2013102 (1991)","journal-title":"Inf. Comput."},{"key":"9038_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1007\/3-540-45793-3_28","volume-title":"Proceedings of the 16th Annual Conference of the EACSL (CSL 2002)","author":"E. B\u00f6hler","year":"2002","unstructured":"B\u00f6hler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: Equivalence and isomorphism for Boolean constraint satisfaction. In: Proceedings of the 16th Annual Conference of the EACSL (CSL 2002). Lecture Notes in Computer Science, vol.\u00a02471, pp.\u00a0412\u2013426. Springer, Berlin (2002)"},{"key":"9038_CR5","doi-asserted-by":"crossref","unstructured":"B\u00f6hler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: The complexity of Boolean constraint isomorphism. Technical Report cs.CC\/0306134, Computing Research Repository, http:\/\/www.acm.org\/repository\/ , June 2003. Revised, April 2004","DOI":"10.1007\/978-3-540-24749-4_15"},{"key":"9038_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/978-3-540-24749-4_15","volume-title":"Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science","author":"E. B\u00f6hler","year":"2004","unstructured":"B\u00f6hler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: The complexity of Boolean constraint isomorphism. In: Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol.\u00a02996, pp.\u00a0164\u2013175. Springer, Berlin (2004)"},{"key":"9038_CR7","unstructured":"Borchert, B., Ranjan, D.: The circuit subfunction relations are \u03a3 2 p -complete. Technical Report MPI-I-93-121, MPI, Saarbr\u00fccken (1993)"},{"issue":"6","key":"9038_CR8","doi-asserted-by":"crossref","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 Comput. Syst. 31(6), 679\u2013693 (1998)","journal-title":"Theory Comput. Syst."},{"key":"9038_CR9","doi-asserted-by":"crossref","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. Inf. Comput. 125, 1\u201312 (1996)","journal-title":"Inf. Comput."},{"key":"9038_CR10","series-title":"Monographs on Discrete Applied Mathematics","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. Monographs on Discrete Applied Mathematics. SIAM, Philadelphia (2001)"},{"key":"9038_CR11","first-page":"151","volume-title":"Proceedings of the 3rd ACM Symposium on Theory of Computing","author":"S. Cook","year":"1971","unstructured":"Cook, S.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM, New York (1971)"},{"key":"9038_CR12","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 51, 511\u2013522 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9038_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9038_CR14","unstructured":"Hemaspaandra, E.: Dichotomy theorems for alternation-bounded quantified Boolean formulas. Technical Report cs.CC\/0406006, Computing Research Repository, http:\/\/www.acm.org\/repository\/ , June 2004"},{"issue":"2","key":"9038_CR15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/261342.261344","volume":"28","author":"E. Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Raising NP lower bounds to parallel NP lower bounds. SIGACT News 28(2), 2\u201313 (1997)","journal-title":"SIGACT News"},{"issue":"6","key":"9038_CR16","doi-asserted-by":"crossref","first-page":"1948","DOI":"10.1137\/S0097539799362639","volume":"31","author":"E. Hemaspaandra","year":"2002","unstructured":"Hemaspaandra, E., Wechsung, G.: The minimization problem for Boolean formulas. SIAM J. Comput. 31(6), 1948\u20131958 (2002)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9038_CR17","doi-asserted-by":"crossref","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. J. ACM 44(4), 527\u2013548 (1997)","journal-title":"J. ACM"},{"key":"9038_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/3-540-48321-7_27","volume-title":"Proceedings of the 12th Conference on Fundamentals of Computation Theory","author":"L. Juban","year":"1999","unstructured":"Juban, L.: Dichotomy theorem for generalized unique satisfiability problem. In: Proceedings of the 12th Conference on Fundamentals of Computation Theory. Lecture Notes in Computer Science, vol.\u00a01684, pp.\u00a0327\u2013337. Springer, Berlin (1999)"},{"issue":"1","key":"9038_CR19","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/S0890-5401(03)00037-3","volume":"187","author":"L. Kirousis","year":"2003","unstructured":"Kirousis, L., Kolaitis, P.: The complexity of minimal satisfiability problems. Inf. Comput. 187(1), 20\u201339 (2003)","journal-title":"Inf. Comput."},{"issue":"1","key":"9038_CR20","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1137\/S0097539795285114","volume":"28","author":"D. Kavvadias","year":"1998","unstructured":"Kavvadias, D., Sideri, M.: The inverse satisfiability problem. SIAM J. Comput. 28(1), 152\u2013163 (1998)","journal-title":"SIAM J. Comput."},{"key":"9038_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity","author":"J. K\u00f6bler","year":"1993","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: Its Structural Complexity. Birkh\u00e4user, Basel (1993)"},{"issue":"6","key":"9038_CR22","doi-asserted-by":"crossref","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 J. Comput. 30(6), 1863\u20131920 (2001)","journal-title":"SIAM J. Comput."},{"key":"9038_CR23","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E. Post","year":"1944","unstructured":"Post, E.: Recursively enumerable sets of integers and their decision problems. Bull. AMS 50, 284\u2013316 (1944)","journal-title":"Bull. AMS"},{"key":"9038_CR24","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM Symposium on Theory of Computing, pp.\u00a0216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"1\u20132","key":"9038_CR25","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K. Wagner","year":"1987","unstructured":"Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51(1\u20132), 53\u201380 (1987)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9038-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9038-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9038-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:34Z","timestamp":1558698694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9038-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,14]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["9038"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9038-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,14]]}}}