Fall 2016

Composing Strategies in Pebble Games

Thursday, Dec. 8, 2016 4:15 pm4:35 pm PST

Add to Calendar


Calvin Lab Auditorium

Pebble games (based on Ehrenfeucht-Fraïssé games) are an important tool for analyzing the expressive power of logics.  They are also related to efficient algorithms for approximating homomorphism and isomorphism on finite structures.  In this short talk, I look at some questions arising from composing strategies in pebble games and some
algorithmic consequences that may follow.

PDF icon Composing Strategies in Pebble Games169.65 KB