Preservation and decomposition theorems for bounded degree structures
Preservation and decomposition theorems for bounded degree structures
We provide elementary algorithms for two preservation theorems for first-order sentences with modulo m counting quantifiers (FO+MODm) on the class Cd of all finite structures of degree at most d: For each FO+MODm-sentence that is preserved under extensions (homomorphisms) on Cd, a Cd-equivalent existential (existential-positive) FO-sentence can be constructed in …