Dynamic Complexity of Formal Languages

Prelegent(ci)

Wouter Gelade

Afiliacja

Hasselt

Termin

7 października 2009 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

We will discuss the dynamic complexity of formal languages. As opposed to static complexity theory, which investigates the complexity of problems over fixed structures, dynamic complexity theory concerns the complexity necessary to maintain the answer to a problem on an ever changing structure. In terms of formal languages, this amounts to maintaining whether a changing word is in a given language. We will show that the regular languages are exactly those languages maintainable using quantifier-free first order updates, and consider some related questions.

---