moteur de recherche

Séminaire Algo - Vincent Jugé
Séminaire Algo - Vincent Jugé
3-oct.-2017 14:30
Il y a: 15 days

Vincent Jugé

Courcelle's theorem made dynamic

Salle de séminaire (4B05R) - Bâtiment Copernic

Dynamic complexity is concerned with the complexity of updating a solution to a problem when its input changes. A typical example is as follows: given an directed graph G and two pointed vertices s and t, you wish to know whether there exists a path from s to t in G. After your computation is complete, the graph is modified (e.g. by adding or deleting an edge): how should you proceed to update your answer at the least cost? Computing and storing auxiliary data, such as maintaining a covering forest, might be helpful in that regard. In this talk, we will consider a specific class for dynamic complexity, called DynFO. A dynamic problem belongs to this class if updates can be performed by applying first-order formulas. We will show that a dynamic variant of Courcelle's theorem belongs to DynFO (with some mild precomputation step), and we will apply this result to computing optimal strategies in 2-player reachability or parity games. This talk is based on joint a work with Patricia Bouyer-Decitre and Nicolas Markey.

<- retour: