Skip to main content

Homomorphism preservation theorems

Publication ,  Journal Article
Rossman, B
Published in: Journal of the ACM
July 1, 2008

The homomorphism preservation theorem (h.p.t.), a result in classical model theory, states that a first-order formula is preserved under homomorphisms on all structures (finite and infinite) if and only if it is equivalent to an existential-positive formula. Answering a long-standing question in finite model theory, we prove that the h.p.t. remains valid when restricted to finite structures (unlike many other classical preservation theorems, including the o - Tarski theorem and Lyndon's positivity theorem). Applications of this result extend to constraint satisfaction problems and to database theory via a correspondence between existential-positive formulas and unions of conjunctive queries. A further result of this article strengthens the classical h.p.t.: we show that a first-order formula is preserved under homomorphisms on all structures if and only if it is equivalent to an existential-positive formula of equal quantifier-rank. © 2008 ACM.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Journal of the ACM

DOI

EISSN

1557-735X

ISSN

0004-5411

Publication Date

July 1, 2008

Volume

55

Issue

3

Related Subject Headings

  • Computation Theory & Mathematics
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2008). Homomorphism preservation theorems. Journal of the ACM, 55(3). https://doi.org/10.1145/1379759.1379763
Rossman, B. “Homomorphism preservation theorems.” Journal of the ACM 55, no. 3 (July 1, 2008). https://doi.org/10.1145/1379759.1379763.
Rossman B. Homomorphism preservation theorems. Journal of the ACM. 2008 Jul 1;55(3).
Rossman, B. “Homomorphism preservation theorems.” Journal of the ACM, vol. 55, no. 3, July 2008. Scopus, doi:10.1145/1379759.1379763.
Rossman B. Homomorphism preservation theorems. Journal of the ACM. 2008 Jul 1;55(3).

Published In

Journal of the ACM

DOI

EISSN

1557-735X

ISSN

0004-5411

Publication Date

July 1, 2008

Volume

55

Issue

3

Related Subject Headings

  • Computation Theory & Mathematics
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences