Paper: Homomorphism Closed vs. Existential Positive (at LICS 2003)

Authors: Tomás Feder Moshe Y. Vardi

Abstract

Preservations theorems, which establish connection between syntactic and semantic properties of formulas, are a major topic of investigation in model theory. In the context of finite-model theory, most, but not all, preservation theorems are known to fail. It is not known, however, whether the £os-Tarski-Lyndon Theorem, which asserts that a 1st-order sentence is preserved under homomorphisms iff it is equivalent to an existential positive sentence, holds with respect to finite structures. Resolving this is an important open question in finite-model theory. In this paper we study the relationship between closure under homomorphism and positive syntax for several non-1st-order existential logics that are of interest in computer science. We prove that the £os-Tarski-Lyndon Theorem holds for these logics. The logics we consider are variable-confined existential infinitary logic, Datalog, and various fragments of second-order logic.

BibTeX

  @InProceedings{FederVardi-HomomorphismClosedv,
    author = 	 {Tomás Feder and Moshe Y. Vardi},
    title = 	 {Homomorphism Closed vs. Existential Positive},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003)},
    year =	 {2003},
    month =	 {June}, 
    pages =      {311--320},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }