You are not logged in | Log in

Differential games for FO logic

Speaker(s)
Jakub Gajarsky
Affiliation
Uniwersytet Warszawski
Date
June 17, 2020, 2:15 p.m.
Room
room 5050
Seminar
Seminar Automata Theory

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.