{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T14:57:02Z","timestamp":1743087422399,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220111"},{"type":"electronic","value":"9783642220128"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22012-8_27","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T03:29:39Z","timestamp":1308367779000},"page":"344-355","source":"Crossref","is-referenced-by-count":2,"title":["Generic Expression Hardness Results for Primitive Positive Formula Comparison"],"prefix":"10.1007","author":[{"given":"Simone","family":"Bova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hubie","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Valeriote","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"27_CR1","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0371(3), 155\u2013168 (2007)","journal-title":"Theoretical Computer Science"},{"key":"27_CR2","unstructured":"Barto, L.: CD implies NU (2010) (manuscript)"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 595\u2013603 (2009)","DOI":"10.1109\/FOCS.2009.32"},{"issue":"3","key":"27_CR4","doi-asserted-by":"publisher","first-page":"1445","DOI":"10.1090\/S0002-9947-09-04874-0","volume":"362","author":"J. Berman","year":"2010","unstructured":"Berman, J., Idziak, P., Markovi\u0107, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with Few Subalgebras of Powers. Transactions of the American Mathematical Society\u00a0362(3), 1445\u20131473 (2010)","journal-title":"Transactions of the American Mathematical Society"},{"key":"27_CR5","doi-asserted-by":"publisher","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\u00a05, 243\u2013252, 531\u2013539 (1969)","journal-title":"Cybernetics"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Bova, S., Chen, H., Valeriote, M.: On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas. Theory of Computing Systems,, doi:10.1007\/s00224-010-9302-7","DOI":"10.1007\/s00224-010-9302-7"},{"issue":"3","key":"27_CR7","doi-asserted-by":"publisher","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 Journal on Computing\u00a034(3), 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Tractable Conservative Constraint Satisfaction Problems. In: Proceedings of 18th IEEE Symposium on Logic in Computer Science (LICS 2003), pp. 321\u2013330 (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A Dichotomy Theorem for Constraint Satisfaction Problems on a 3-element Set. Journal of the ACM\u00a053 (2006)","DOI":"10.1145\/1120582.1120584"},{"key":"27_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-540-92800-3_4","volume-title":"Complexity of Constraints","author":"A. Bulatov","year":"2008","unstructured":"Bulatov, A., Valeriote, M.: Recent Results on the Algebraic Approach to the CSP. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints. LNCS, vol.\u00a05250, pp. 68\u201392. Springer, Heidelberg (2008)"},{"key":"27_CR11","series-title":"London Mathematical Society Lecture Note Series","volume-title":"Commutator Theory for Congruence Modular Varieties","author":"R. Freese","year":"1987","unstructured":"Freese, R., McKenzie, R.: Commutator Theory for Congruence Modular Varieties. London Mathematical Society Lecture Note Series, vol.\u00a0125. Cambridge University Press, Cambridge (1987)"},{"key":"27_CR12","doi-asserted-by":"publisher","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. Pacific Journal of Mathematics\u00a027, 95\u2013100 (1968)","journal-title":"Pacific Journal of Mathematics"},{"key":"27_CR13","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. American Mathematical Society, Providence (1988); Revised edition: 1996"},{"key":"27_CR14","doi-asserted-by":"crossref","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)","DOI":"10.1109\/LICS.2007.50"},{"issue":"1","key":"27_CR15","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1137\/0216011","volume":"16","author":"H.B. Hunt III","year":"1987","unstructured":"Hunt III, H.B., Rosenkrantz, D.J., Bloniarz, P.A.: On the Computational Complexity of Algebra on Lattices. SIAM Journal on Computing\u00a016(1), 129\u2013148 (1987)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"27_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0002-9947-98-01594-3","volume":"350","author":"K. Kearnes","year":"1998","unstructured":"Kearnes, K., Kiss, E., Valeriote, M.: Minimal Sets and Varieties. Transactions of the American Mathematical Society\u00a0350(1), 1\u201341 (1998)","journal-title":"Transactions of the American Mathematical Society"},{"key":"27_CR17","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a061, 302\u2013332 (2000)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"27_CR18","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a058(3), 407\u2013427 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Vardi, M.: The Complexity of Relational Query Languages. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC (1982)","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22012-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:06:38Z","timestamp":1560283598000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22012-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220111","9783642220128"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22012-8_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}