We provide elementary algorithms for two preservation theorems for first-order sentences (FO) on the class âd of all finite structures of degree at most d: For each FO-sentence that is preserved under extensions (homomorphisms) on âd, a âd-equivalent existential (existential-positive) FO-sentence can be constructed in 5-fold (4-fold) exponential time. This is complemented by lower bounds showing that a 3-fold exponential blow-up of the computed existential (existential-positive) sentence is unavoidable. Both algorithms can be extended (while maintaining the upper and lower bounds on their time complexity) to input first-order sentences with modulo m counting quantifiers (FO+MODm). Furthermore, we show that for an input FO-formula, a âd-equivalent Feferman-Vaught decomposition can be computed in 3-fold exponential time. We also provide a matching lower bound.

Comment: 42 pages and 3 figures. This is the full version of: Frederik Harwath, Lucas Heimberg, and Nicole Schweikardt. Preservation and decomposition theorems for bounded degree structures. In Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS'14, pages 49:1-49:10. ACM, 2014

• 03C13 - Model theory of finite structures
• 03C40 - Interpolation, preservation, definability
• 03C80 - Logic with extra quantifiers and operators
• 68Q19 - Descriptive complexity and finite models