Preservation and decomposition theorems for bounded degree structures

DOI10.1145/2603088.2603130MaRDI QIDQ4635634zbMATH OpenOpenAlexFDO

Authors Frederik Harwath, Lucas Heimberg, Nicole Schweikardt

Publication date 23 April 2018

Published in Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.05888

zbMATH Keywords

computational logicelementary algorithmsexistential preservationFeferman-Vaughtfirst-order logicHanf localityhomomorphism preservationmodulo counting quantifierspreservation theoremsstructures of bounded degreeŁoś-Tarski

Mathematics Subject Classification ID

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

Abstract: We provide elementary algorithms for two preservation theorems for first-order sentences (FO) on the class ^ad of all finite structures of degree at most d: For each FO-sentence that is preserved under extensions (homomorphisms) on ^ad, a ^ad-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 ^ad-equivalent Feferman-Vaught decomposition can be computed in 3-fold exponential time. We also provide a matching lower bound.

Recommendations

• Preservation and decomposition theorems for bounded degree structures
• A note on preservers of decomposability
• A preservation theorem for ec-structures with applications
• Decidability and Invariant Classes for Degree Structures
• Preservation under substructures modulo bounded cores
• Extension preservation theorems on classes of acyclic finite structures
• Bounds for the decomposition dimension of some class of graphs
• Preservation under Extensions on Well-Behaved Finite Structures
• Automata, Languages and Programming
• A generalization of the Łoś-Tarski preservation theorem over classes of finite structures

Cited in

(4)

• Preservation and decomposition theorems for bounded degree structures
• Model Theory Makes Formulas Large
• Preservation theorems through the Lens of topology
• A generalization of the Łoś-Tarski preservation theorem

This page was built for publication: Preservation and decomposition theorems for bounded degree structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635634)