Publications [#348694] of Benjamin Rossman

Papers Published

1. Rossman, B, Homomorphism preservation theorems, Journal of the Acm, vol. 55 no. 3 (July, 2008) [doi]
   (last updated on 2022/05/19)

   Abstract:
   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 o - 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 of equal quantifier-rank. © 2008 ACM.