Preservation and decomposition theorems for bounded degree structures
Preservation and decomposition theorems for bounded degree structures
复制标题
有界度结构的守恒与分解定理
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Nicole Schweikardt
中科院分区：
文献类型：
--
作者：
Frederik Harwath;Lucas Heimberg;Nicole Schweikardt
我们为两种保存定理提供了基本算法，用于在所有有限度的d级的cd上使用Modulo M计数量词（fo+modm）的一阶句子（fo+modm）。同构）在CD上，可以在6倍（4倍）中构建CD等效的存在（存在阳性）fo-sentence。指数时间。对于fo-sentences，该算法具有5倍（4倍）指数的时间复杂性。这是通过下限的补充，表明对于fo-sentences而言，不可避免的是，计算出的存在（存在阳性）句子的3倍指数爆炸是不可避免的。此外，我们表明，对于输入FO形式，可以在3倍指数时间内计算CD等效的Feferman-Feferman-gubight分解。我们还提供匹配的下限。
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 6-fold (4-fold) exponential time. For FO-sentences, the algorithm has 5-fold (4-fold) exponential time complexity. This is complemented by lower bounds showing that for FO-sentences a 3-fold exponential blow-up of the computed existential (existential-positive) sentence is unavoidable. Furthermore, we show that for an input FO-formula, a Cd-equivalent Feferman-Vaught decomposition can be computed in 3-fold exponential time. We also provide a matching lower bound.