Samir Datta ; Anish Mukherjee ; Thomas Schwentick ; Nils Vortmeier ; Thomas Zeume - A Strategy for Dynamic Programs: Start over and Muddle through

lmcs:4515 - Logical Methods in Computer Science, May 8, 2019, Volume 15, Issue 2 -
A Strategy for Dynamic Programs: Start over and Muddle throughArticle

Authors: Samir Datta ORCID; Anish Mukherjee ORCID; Thomas Schwentick ; Nils Vortmeier ; Thomas Zeume

    In the setting of DynFO, dynamic programs update the stored result of a query whenever the underlying data changes. This update is expressed in terms of first-order logic. We introduce a strategy for constructing dynamic programs that utilises periodic computation of auxiliary data from scratch and the ability to maintain a query for a limited number of change steps. We show that if some program can maintain a query for log n change steps after an AC$^1$-computable initialisation, it can be maintained by a first-order dynamic program as well, i.e., in DynFO. As an application, it is shown that decision and optimisation problems defined by monadic second-order (MSO) formulas are in DynFO, if only change sequences that produce graphs of bounded treewidth are allowed. To establish this result, a Feferman-Vaught-type composition theorem for MSO is established that might be useful in its own right.

    Volume: Volume 15, Issue 2
    Published on: May 8, 2019
    Accepted on: May 2, 2019
    Submitted on: May 18, 2018
    Keywords: Computer Science - Logic in Computer Science,F.1.2

    1 Document citing this article

    Consultation statistics

    This page has been seen 1440 times.
    This article's PDF has been downloaded 348 times.