{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T18:37:49Z","timestamp":1648665469258},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,11,27]],"date-time":"2010-11-27T00:00:00Z","timestamp":1290816000000},"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":[[2012,2]]},"DOI":"10.1007\/s00224-010-9302-7","type":"journal-article","created":{"date-parts":[[2010,11,25]],"date-time":"2010-11-25T23:32:05Z","timestamp":1290727925000},"page":"329-353","source":"Crossref","is-referenced-by-count":2,"title":["On the Expression Complexity of Equivalence and\u00a0Isomorphism of\u00a0Primitive Positive Formulas"],"prefix":"10.1007","volume":"50","author":[{"given":"Simone","family":"Bova","sequence":"first","affiliation":[]},{"given":"Hubie","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Matthew","family":"Valeriote","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,11,27]]},"reference":[{"issue":"3","key":"9302_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."},{"key":"9302_CR2","volume-title":"Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS","author":"E. Allender","year":"2005","unstructured":"Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: refining Schaefer\u2019s theorem. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS (2005)"},{"issue":"4","key":"9302_CR3","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.jcss.2008.11.001","volume":"75","author":"E. Allender","year":"2009","unstructured":"Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: refining Schaefer\u2019s theorem. J. Comput. Syst. Sci. 75(4), 245\u2013254 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9302_CR4","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.tcs.2006.11.005","volume":"371","author":"A. Atserias","year":"2007","unstructured":"Atserias, A.: Conjunctive query evaluation by search-tree revisited. Theor. Comput. Sci. 371(3), 155\u2013168 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9302_CR5","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254\u2013276 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9302_CR6","author":"J. Berman","year":"2009","unstructured":"Berman, J., Idziak, P., Markovic, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with few subalgebras of powers. Trans. Am. Math. Soc. (2009). doi: 10.1090\/S0002-9947-09-04874-0","journal-title":"Trans. Am. Math. Soc."},{"key":"9302_CR7","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01070906","volume":"5","author":"V. Bodnarchuk","year":"1969","unstructured":"Bodnarchuk, V., Kaluzhnin, L., Kotov, V., Romov, B.: Galois theory for post algebras. I, II. Cybernetics 5:243\u2013252, 531\u2013539 (1969)","journal-title":"Cybernetics"},{"key":"9302_CR8","volume-title":"Proceedings of the 16th International Workshop on Computer Science Logic, CSL","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 International Workshop on Computer Science Logic, CSL (2002)"},{"key":"9302_CR9","volume-title":"Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS","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 Annual Symposium on Theoretical Aspects of Computer Science, STACS (2004)"},{"issue":"2","key":"9302_CR10","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. Boppana","year":"1987","unstructured":"Boppana, R., Hastad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127\u2013132 (1987)","journal-title":"Inf. Process. Lett."},{"key":"9302_CR11","unstructured":"Bulatov, A., Jeavons, P.: Algebraic structures in combinatorial problems. Technical Report MATH-AL-4-2001, Technische Universitat Dresden (2001)"},{"issue":"3","key":"9302_CR12","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"9302_CR13","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classification of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2001)"},{"key":"9302_CR14","doi-asserted-by":"crossref","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","volume":"27","author":"D. Geiger","year":"1968","unstructured":"Geiger, D.: Closed systems of functions and predicates. Pac. J. Math. 27, 95\u2013100 (1968)","journal-title":"Pac. J. Math."},{"issue":"3","key":"9302_CR15","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 690\u2013728 (1991)","journal-title":"J. ACM"},{"key":"9302_CR16","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC","author":"S. Goldwasser","year":"1986","unstructured":"Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC (1986)"},{"key":"9302_CR17","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/conm\/076","volume-title":"The Structure of Finite Algebras","author":"D. Hobby","year":"1988","unstructured":"Hobby, D., McKenzie, R.: The Structure of Finite Algebras. Contemporary Mathematics, vol.\u00a076. Am. Math. Soc., Providence (1988)"},{"key":"9302_CR18","volume-title":"Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, LICS","author":"P. Idziak","year":"2007","unstructured":"Idziak, P., Markovic, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebras with few subpowers. In: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, LICS (2007)"},{"issue":"1\u20132","key":"9302_CR19","doi-asserted-by":"crossref","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.: Constraints, consistency, and closure. Artif. Intell. 101(1\u20132), 251\u2013265 (1998)","journal-title":"Artif. Intell."},{"key":"9302_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity","author":"J. Kobler","year":"1993","unstructured":"Kobler, J., Sch\u00f6ning, U., Toran, J.: The Graph Isomorphism Problem: Its Structural Complexity. Birkh\u00e4user, Basel (1993)"},{"key":"9302_CR21","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P. Kolaitis","year":"2000","unstructured":"Kolaitis, P., Vardi, M.: Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61, 302\u2013332 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9302_CR22","doi-asserted-by":"crossref","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. J. ACM 22(1), 155\u2013171 (1975)","journal-title":"J. ACM"},{"key":"9302_CR23","author":"B. Larose","year":"2008","unstructured":"Larose, B., Tesson, P.: Universal algebra and hardness results for constraint satisfaction problems. Theor. Comput. Sci. (2008). doi: 10.1016\/j.tcs.2008.12.048","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"9302_CR24","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/j.tcs.2005.07.018","volume":"345","author":"G. Nordh","year":"2005","unstructured":"Nordh, G.: The complexity of equivalence and isomorphism of systems of equations over finite groups. Theor. Comput. Sci. 345(2\u20133), 406\u2013424 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9302_CR25","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1995","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1995)"},{"issue":"3","key":"9302_CR26","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"C. Papadimitriou","year":"1999","unstructured":"Papadimitriou, C., Yannakakis, M.: On the complexity of database queries. J. Comput. Syst. Sci. 58(3), 407\u2013427 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9302_CR27","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC","author":"T. Schaefer","year":"1978","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC (1978)"},{"issue":"3","key":"9302_CR28","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Schoning","year":"1988","unstructured":"Schoning, U.: Graph isomorphism is in the low hierarchy. J. Comput. Syst. Sci. 37(3), 312\u2013323 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9302_CR29","series-title":"Seminaires de Mathematiques Superieures","volume-title":"Clones in Universal Algebra","author":"A. Szendrei","year":"1986","unstructured":"Szendrei, A.: Clones in Universal Algebra. Seminaires de Mathematiques Superieures, vol.\u00a099. University of Montreal, Montreal (1986)"},{"key":"9302_CR30","series-title":"Research and Exposition in Mathematics","first-page":"209","volume-title":"A Survey on Strictly Simple Algebras and Minimal Varieties","author":"A. Szendrei","year":"1992","unstructured":"Szendrei, A.: A Survey on Strictly Simple Algebras and Minimal Varieties. Research and Exposition in Mathematics, vol.\u00a019, pp. 209\u2013239. Heldermann, Berlin (1992)"},{"issue":"5","key":"9302_CR31","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1137\/S009753970241096X","volume":"33","author":"J. Toran","year":"2004","unstructured":"Toran, J.: On the hardness of graph isomorphism. SIAM J. Comput. 33(5), 1093\u20131108 (2004)","journal-title":"SIAM J. Comput."},{"key":"9302_CR32","author":"M. Valeriote","year":"2009","unstructured":"Valeriote, M.: A subalgebra intersection property for congruence distributive varieties. Can. J. Math. (2009). doi: 10.4153\/CJM-2009-023-2","journal-title":"Can. J. Math."},{"key":"9302_CR33","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC","author":"M. Vardi","year":"1982","unstructured":"Vardi, M.: The complexity of relational query languages. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC (1982)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9302-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9302-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9302-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:22Z","timestamp":1558684462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9302-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,27]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["9302"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9302-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,27]]}}}