Reachability is in DynFO

A dynamic program, as introduced by Dong, Su Topor (1993) and Pat- naik and Immerman (1994), maintains a fixed query for an input database which is subject to tuple insertions and deletions. It can use an auxiliary database whose relations are updated via first-order formulas upon modi- fications of the input database. In this talk I will present how Reachability in directed graphs can be maintained in this fashion. This result confirms a two decade old conjecture of Patnaik and Immerman (1997). The talk is based on joint work with Samir Datta, Raghav Kulkarni, Anish Mukherjee and Thomas Schwentick.

Authors

• Thomas Zeume

Keywords

No keywords are indexed for this paper.