Datta, Samir and Mukherjee, Anish and Schwentick, Thomas and Vortmeier, Nils and Zeume, Thomas - 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 through

Authors: Datta, Samir and Mukherjee, Anish and Schwentick, Thomas and Vortmeier, Nils and Zeume, Thomas

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.


Source : oai:arXiv.org:1704.07998
Volume: Volume 15, Issue 2
Published on: May 8, 2019
Submitted on: May 18, 2018
Keywords: Computer Science - Logic in Computer Science,F.1.2


Share