Frederik Harwath ; Lucas Heimberg ; Nicole Schweikardt - Preservation and decomposition theorems for bounded degree structures

lmcs:1618 - Logical Methods in Computer Science, December 29, 2015, Volume 11, Issue 4 - https://doi.org/10.2168/LMCS-11(4:17)2015
Preservation and decomposition theorems for bounded degree structures

Authors: Frederik Harwath ; Lucas Heimberg ; Nicole Schweikardt

    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.


    Volume: Volume 11, Issue 4
    Published on: December 29, 2015
    Submitted on: April 19, 2015
    Keywords: Computer Science - Logic in Computer Science

    Linked data

    Source : ScholeXplorer IsCitedBy ARXIV 2007.07879
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.csl.2021.32
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2007.07879
    • 10.48550/arxiv.2007.07879
    • 10.4230/lipics.csl.2021.32
    • 2007.07879
    Preservation Theorems Through the Lens of Topology
    Lopez, Aliaume ;

    Share

    Consultation statistics

    This page has been seen 437 times.
    This article's PDF has been downloaded 377 times.