## 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 Symp. on Logic in Computer Science, {LICS} 2003}, year = 2003, editor = {Phokion G. Kolaitis}, month = {June}, pages = {311--320}, location = {Ottawa, Canada}, publisher = {IEEE Computer Society Press} }