Reachability is in DynFO

Prelegent(ci)

Thomas Zeume

Afiliacja

Uniwersytet Warszawski

Termin

8 marca 2017 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

In the talk I will gently introduce the dynamic descriptive
complexity framework by Patnaik and Immerman. In their formalisation,
the result of a database query is updated by logical formulas after the
insertion or deletion of a tuple. The formulas may use additional
auxiliary relations that need to be updated as well. As an example I
will outline how the Reachability query can be maintained by first-order
formulas.

---