Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.ICALP.2017.98 | international colloquium on automata languages and programming |
DocType | Volume | Citations |
Conference | abs/1704.07998 | 1 |
PageRank | References | Authors |
0.35 | 1 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samir Datta | 1 | 200 | 19.82 |
| Anish Mukherjee | 2 | 13 | 3.98 |
| Thomas Schwentick | 3 | 2373 | 155.10 |
| nils vortmeier | 4 | 6 | 2.85 |
| Thomas Zeume | 5 | 62 | 8.83 |