Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twentieth Annual IEEE Symposium on

Logic in Computer Science (LICS 2005)

Paper: Existential Positive Types and Preservation under Homomorphisisms (at LICS 2005)

Winner of the Kleene Award in 2005
Authors: Benjamin Rossman

Abstract

We prove the Finite Homomorphism Preservation Theorem: a first-order 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.

BibTeX

  @InProceedings{Rossman-ExistentialPositive,
    author = 	 {Benjamin Rossman},
    title = 	 {Existential Positive Types and Preservation under Homomorphisisms},
    booktitle =  {Proceedings of the Twentieth Annual IEEE Symposium on Logic in Computer Science (LICS 2005)},
    year =	 {2005},
    month =	 {June}, 
    pages =      {467--476},
    location =   {Chicago, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2016-01-1416:21
Andrzej Murawski