Paper Info
Title
Combining Ehrenfeucht-Fraïssé Games
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.
Year
DOI
Venue
2009
10.1109/LICS.2009.50
Los Angeles, CA
Keywords
Field
DocType
k-variable logic,complicated game,ehrenfeucht-fraisse game,inexpressibility result,building block,successor-invariant logic,expressive power,combining ehrenfeucht-fra,first-order logic,general method,basic game,game theory,games,formal logic,computer science,data mining,random graph,first order logic
Random graph,Computer science,Theoretical computer science,First-order logic,Game theory,Expressive power,Ehrenfeucht–Fraïssé game
Conference
ISSN
ISBN
Citations 
1043-6871
978-0-7695-3746-7
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Benjamin Rossman129820.00