Name
Abstract | ||
|---|---|---|
We prove the Finite Homomorphism Preservation Theorem: a first-order formula is preserved underhomomorphisms 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/LICS.2005.16 | LICS |
Keywords | Field | DocType |
existential positive types,classical homomorphism preservation theorem,quantifier rank,finite homomorphism preservation theorem,existential positive formula,existential positive saturation,new notion,first-order formula,finite structure,existential positive type,first order,computer science,formal logic,logic,databases,theorem proving | Discrete mathematics,Existentialism,Automated theorem proving,First-order logic,Homomorphism,Model theory,Skolem normal form,Mathematics | Conference |
ISSN | ISBN | Citations |
1043-6871 | 0-7695-2266-1 | 32 |
PageRank | References | Authors |
1.53 | 0 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Benjamin Rossman | 1 | 298 | 20.00 |