Talks
Fall 2016

Composing Strategies in Pebble Games

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

Add to Calendar

Location: 

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.

AttachmentSize
PDF icon Composing Strategies in Pebble Games169.65 KB