2026-07-21T20:02:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22763 2025-10-02T11:31:20Z ddc:004 open_access

Equi-Rank Homomorphism Preservation Theorem on Finite Structures Rossman, Benjamin finite model theory preservation theorems quantifier rank The Homomorphism Preservation Theorem (HPT) of classical model theory states that a first-order sentence is preserved under homomorphisms if, and only if, it is equivalent to an existential-positive sentence. This theorem remains valid when restricted to finite structures, as demonstrated by the author in [Rossman, 2008; Rossman, 2017] via distinct model-theoretic and circuit-complexity based proofs. In this paper, we present a third (and significantly simpler) proof of the finitary HPT based on a generalized Cai-Fürer-Immerman construction. This method establishes a tight correspondence between syntactic parameters of a homomorphism-preserved sentence (quantifier rank, variable width, alternation height) and structural parameters of its minimal models (tree-width, tree-depth, decomposition height). Consequently, we prove a conjectured "equi-rank" version of the finitary HPT. In contrast, previous versions of the finitary HPT possess additional properties, but incur blow-ups in the quantifier rank of the equivalent existential-positive sentence. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Rossman 2025 Is Part Of LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2025.6 urn:nbn:de:0030-drops-227634 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.6 eng https://creativecommons.org/licenses/by/4.0/legalcode