Nie jesteś zalogowany | Zaloguj się

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.