Dynamic Complexity of Formal Languages

Speaker(s)

Wouter Gelade

Affiliation

Hasselt

Date

Oct. 7, 2009, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---