2026-08-16T14:56:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7447 2024-03-06T10:40:28Z ddc:004 open_access

A Strategy for Dynamic Programs: Start over and Muddle Through Datta, Samir Mukherjee, Anish Schwentick, Thomas Vortmeier, Nils Zeume, Thomas dynamic complexity treewidth monadic second order logic A strategy for constructing dynamic programs is introduced that utilises periodic computation of auxiliary data from scratch and the ability to maintain a query for a limited number of change steps. It is established 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) and guarded second-order logic (GSO) formulas are in DynFO, if only change sequences that produce graphs of bounded treewidth are allowed. To establish this result, Feferman-Vaught-type composition theorems for MSO and GSO are established that might be useful in their own right. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samir Datta and Anish Mukherjee and Thomas Schwentick and Nils Vortmeier and Thomas Zeume 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.98 urn:nbn:de:0030-drops-74470 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.98 eng https://creativecommons.org/licenses/by/3.0/legalcode