Title :
Combining Ehrenfeucht-Fraïssé Games
Author :
Rossman, Benjamin
Author_Institution :
MIT Comput. Sci. & Artificial Intell. Lab., Cambridge, MA, USA
Abstract :
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.
Keywords :
formal logic; game theory; Ehrenfeucht-Fraisse game; first-order logic; k-variable logic; successor-invariant logic; Artificial intelligence; Computer science; Laboratories; Logic; USA Councils;
Conference_Titel :
Logic In Computer Science, 2009. LICS '09. 24th Annual IEEE Symposium on
Conference_Location :
Los Angeles, CA
Print_ISBN :
978-0-7695-3746-7
DOI :
10.1109/LICS.2009.50
