A Strategy for Dynamic Programs: Start over and Muddle through

摘要

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