A Game for Counting Logic Formula Size and an Application to Linear Orders

Gregoire Fournier, György Turán

Ehrenfeucht-Fraïssé (EF) games are a basic tool in finite model theory for proving definability lower bounds, with many applications in complexity theory and related areas. They ha…