Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

A Strategy for Dynamic Programs: Start over and Muddle through

Samir Datta ; Anish Mukherjee ; 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&nbsp;[&hellip;]
Published on May 8, 2019
Volume 15, Issue 2

Dynamic Complexity of Parity Exists Queries

Nils Vortmeier ; Thomas Zeume.
Given a graph whose nodes may be coloured red, the parity of the number of red nodes can easily be maintained with first-order update rules in the dynamic complexity framework DynFO of Patnaik and Immerman. Can this be generalised to other or even all queries that are definable in first-order logic&nbsp;[&hellip;]
Published on November 16, 2021
Volume 17, Issue 4
  • < Previous
  • 1
  • Next >