Math @ Duke

Publications [#348701] of Benjamin Rossman
Papers Published
 Rossman, B, Existential positive types and preservation under homomorphisms,
Proceedings Symposium on Logic in Computer Science
(October, 2005),
pp. 467476
(last updated on 2022/05/21)
Abstract: We prove the Finite Homomorphism Preservation Theorem: a firstorder formula is preserved under homomorphisms on finite structures iff it is equivalent in the finite to an existential positive formula. We also strengthen the classical homomorphism preservation theorem by showing that a formula is preserved under homomorphisms on all structures iff it is equivalent to an existential positive formula of the same quantifier rank. Our method involves analysis of existential positive types and a new notion of existential positive saturation. © 2005 IEEE.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

