Combining Ehrenfeucht-Fraïssé Games
Benjamin Rossman · 2009
Ehrenfeucht-Fraisse games are a useful technique for proving inexpressibility results in first-order logic. Strategies for a few basic games (on long paths, set-powerset structures and random graphs, to name a few) can be used as building blocks for strategies in more complicated games. In this talk, the author discusses a few general methods for combining strategies. Applications include results on the expressive power of successor-invariant logic and k-variable logic.