{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:41:58Z","timestamp":1774946518687,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,7]]},"abstract":"<jats:p>\n            The homomorphism preservation theorem (h.p.t.), a result in classical model theory, states that a first-order formula is preserved under homomorphisms on all structures (finite and infinite) if and only if it is equivalent to an existential-positive formula. Answering a long-standing question in finite model theory, we prove that the h.p.t. remains valid when restricted to finite structures (unlike many other classical preservation theorems, including the \u0141o\u015b--Tarski theorem and Lyndon's positivity theorem). Applications of this result extend to constraint satisfaction problems and to database theory via a correspondence between existential-positive formulas and unions of conjunctive queries. A further result of this article strengthens the classical h.p.t.: we show that a first-order formula is preserved under homomorphisms on all structures if and only if it is equivalent to an existential-positive formula\n            <jats:italic>of equal quantifier-rank<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/1379759.1379763","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T13:35:10Z","timestamp":1217943310000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":80,"title":["Homomorphism preservation theorems"],"prefix":"10.1145","volume":"55","author":[{"given":"Benjamin","family":"Rossman","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31852"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80071-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Alechina N. and Gurevich Y. 1997. Syntax vs. semantics on finite structures. In Structures in Logic and Computer Science J. Mychielski G. Rozenberg and A. Salomaa Eds. Springer-Verlag New York 14--33.   Alechina N. and Gurevich Y. 1997. Syntax vs. semantics on finite structures. In Structures in Logic and Computer Science J. Mychielski G. Rozenberg and A. Salomaa Eds. Springer-Verlag New York 14--33.","DOI":"10.1007\/3-540-63246-8_2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.31"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131344"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/8.5.605"},{"key":"e_1_2_1_8_1","first-page":"166","article-title":"Explicit graphs with extension properties","volume":"86","author":"Blass A.","year":"2005","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science","volume":"775","author":"Deogun J."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Ebbinghaus H. and Flum J. 1996. Finite Model Theory. Springer-Verlag New York.  Ebbinghaus H. and Flum J. 1996. Finite Model Theory. Springer-Verlag New York.","DOI":"10.1007\/3-540-28788-4"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 18th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Feder T."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-47-1-57-103"},{"key":"e_1_2_1_15_1","unstructured":"Gr\u00e4del E. Kolaitis P. Libkin L. Marx M. Spencer J. Vardi M. Venema Y. and Weinstein S. 2007. Finite Model Theory and Its Applications. Springer-Verlag New York.  Gr\u00e4del E. Kolaitis P. Libkin L. Marx M. Spencer J. Vardi M. Venema Y. and Weinstein S. 2007. Finite Model Theory and Its Applications. Springer-Verlag New York."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19990450304"},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Mathematics","volume-title":"Computation and Proof Theory","author":"Gurevich Y."},{"key":"e_1_2_1_18_1","unstructured":"Gurevich Y. 1988. Logic and the challenge of computer science. In Current Trends in Theoretical Computer Science E. Boerger Ed. 1--57.  Gurevich Y. 1988. Logic and the challenge of computer science. In Current Trends in Theoretical Computer Science E. Boerger Ed. 1--57."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Gurevich Y. 1990. On finite model theory (extended abstract). In Feasible Mathematics S. R. Buss and P. J. Scott Eds. Birkh\u00e4user 211--219.  Gurevich Y. 1990. On finite model theory (extended abstract). In Feasible Mathematics S. R. Buss and P. J. Scott Eds. Birkh\u00e4user 211--219.","DOI":"10.1007\/978-1-4612-3466-1_12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford University Press.  Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_22_1","unstructured":"Hodges W. 1993. Model Theory. Cambridge University Press Cambridge MA.  Hodges W. 1993. Model Theory. Cambridge University Press Cambridge MA."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 8th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Kolaitis P. G.","year":"1993"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Libkin L. 2004. Elements of Finite Model Theory. Springer-Verlag New York.   Libkin L. 2004. Elements of Finite Model Theory. Springer-Verlag New York.","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1959.9.129"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(03)00064-7"},{"key":"e_1_2_1_30_1","unstructured":"Rosen E. 1995. Finite model theory and finite variable logic. Ph.D. dissertation University of Pennsylvania.   Rosen E. 1995. Finite model theory and finite variable logic. Ph.D. dissertation University of Pennsylvania."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1182353894"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Rosen E. and Weinstein S. 1995. Preservation theorems in finite model theory. In Logic and Computational Complexity D. Leivant Ed. Springer-Verlag New York 480--502.   Rosen E. and Weinstein S. 1995. Preservation theorems in finite model theory. In Logic and Computational Complexity D. Leivant Ed. Springer-Verlag New York 480--502.","DOI":"10.1007\/3-540-60178-3_99"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.16"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 10th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Stolboushkin A.","year":"1995"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/2964569"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1379759.1379763","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1379759.1379763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:45Z","timestamp":1750255065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1379759.1379763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["10.1145\/1379759.1379763"],"URL":"https:\/\/doi.org\/10.1145\/1379759.1379763","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7]]},"assertion":[{"value":"2007-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}