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. 

 

---