An Isaac Newton Institute Workshop

Games and Verification (GAMES 2006)

Games as An Algorithmic Construct

Author: Moshe Y. Vardi (Rice University)

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