Date:
Wednesday 5th July 2006 - 09:00 to 10:25
Venue:
INI Seminar Room 1
Abstract:
Games were introduced into complexity theory by Chandra, Kozen, and Stockmeyer (JACM, 198), through the concept of alternation, which generalizes nondeterminism. The standard use of alternation is in complexity-theoretic settings. The focus of this talk is on presenting games and alternation as a powerful algorithmic construct. The driving examples are various automated-verification tasks, where games yield elegant and optimal algorithms.
Related Links
- http://www.cs.rice.edu - Home Page