Differential games for FO logic

Prelegent(ci)

Jakub Gajarsky

Afiliacja

Uniwersytet Warszawski

Termin

17 czerwca 2020 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

I will introduce differential games for FO logic of graphs, a new variant of
Ehrenfeucht-Fraisse games. These games are an attempt to extend
currently used locality-based techniques for FO logic in a way which
works naturally on non-sparse graphs. The hope is that the underlying
idea can lead to new techniques for designing efficient algorithms for the
FO model checking problem and for obtaining a finer understanding of
FO logic on certain restricted classes of graphs. 

 

---