TY  - JOUR
A1  - Harwath, Frederik
A1  - Heimberg, Lucas
A1  - Schweikardt, Nicole
T1  - Preservation and decomposition theorems for bounded degree structures
T2  - Logical Methods in Computer Science
N2  - 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
Y1  - 2015
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/30634
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-306349
SN  - 1860-5974
N1  - Creative Commons http://creativecommons.org/licenses/by-nd/2.0/
VL  - 11
IS  - 4:17
SP  - 1
EP  - 44
PB  - Department of Theoretical Computer Science, Technical University of Braunschweig
CY  - Braunschweig
ER  -