{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:19:20Z","timestamp":1725560360923},"publisher-location":"Berlin, Heidelberg","reference-count":25,"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_12","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T14:05:47Z","timestamp":1127829947000},"page":"119-130","source":"Crossref","is-referenced-by-count":3,"title":["Isomorphic Implication"],"prefix":"10.1007","author":[{"given":"Michael","family":"Bauland","sequence":"first","affiliation":[]},{"given":"Edith","family":"Hemaspaandra","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"12_CR1","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"},{"issue":"1","key":"12_CR2","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":"12_CR3","unstructured":"Bauland, M., Hemaspaandra, E.: Isomorphic implication. Technical Report cs.CC\/0412062, Computing Research Repository December 2004. Revised (May 2005), http:\/\/www.acm.org\/repository\/"},{"key":"12_CR4","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":"12_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 June 2003. Revised (April 2004), http:\/\/www.acm.org\/repository\/","DOI":"10.1007\/978-3-540-24749-4_15"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-540-24749-4_15","volume-title":"STACS 2004","author":"E. B\u00f6hler","year":"2004","unstructured":"B\u00f6hler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: The complexity of boolean constraint isomorphism. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 164\u2013175. Springer, Heidelberg (2004)"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-45022-X_24","volume-title":"Proceedings of the 27th International Colloquium on Automata, Languages and Programming","author":"A. Bulatov","year":"2000","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: Constraint satisfaction problems and finite algebras. In: Proceedings of the 27th International Colloquium on Automata, Languages and Programming, pp. 272\u2013282. Springer, Heidelberg (2000)"},{"key":"12_CR8","unstructured":"Borchert, B., Ranjan, D.: The ciruit subfunction relations are $\\Sigma_2^p$ -complete. Technical Report MPI-I-93-121, MPI, Saarbr\u00fccken (1993)"},{"issue":"6","key":"12_CR9","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(6), 679\u2013693 (1998)","journal-title":"Theory of Computing Systems"},{"key":"12_CR10","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"},{"key":"12_CR11","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":"12_CR12","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1145\/800157.805047","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 Press, New York (1971)"},{"key":"12_CR13","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":"12_CR14","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. W. H. Freeman and Company, New York (1979)"},{"issue":"2","key":"12_CR15","doi-asserted-by":"publisher","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\u00a028(2), 2\u201313 (1997)","journal-title":"SIGACT News"},{"issue":"4","key":"12_CR16","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"},{"issue":"1-2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science\u00a0200(1-2), 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"key":"12_CR18","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 the generalized unique satisfiability problem. In: Ciobanu, G., P\u0103un, G. (eds.) FCT 1999. LNCS, vol.\u00a01684, pp. 327\u2013337. Springer, Heidelberg (1999)"},{"key":"12_CR19","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)"},{"issue":"1","key":"12_CR20","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 on Computing\u00a028(1), 152\u2013163 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"12_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":"12_CR22","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":"12_CR23","doi-asserted-by":"publisher","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. Bulletin of the AMS\u00a050, 284\u2013316 (1944)","journal-title":"Bulletin of the AMS"},{"key":"12_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. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"1\u20132","key":"12_CR25","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a051(1\u20132), 53\u201380 (1987)","journal-title":"Theoretical Computer Science"}],"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_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:41:09Z","timestamp":1605642069000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11549345_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540287025","9783540318675"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11549345_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}