Playing structure rewriting games with formulas on states

Speaker

Dr. Lukasz Kaiser, Research Group Computer Science 7
Title Playing structure rewriting games with formulas on states
When 03.12.2008, 15.00 Uhr
Where Lecture Room Informatik 11
Abstract In structure rewriting games, each state of the play is represented by a finite relational structure and to move the player chooses a rewriting rule and applies it to the structure. We consider two-player zero-sum games of this kind where the first player wins if she can reach a state in which a given formula holds.

Our objective is to construct good strategies for the players in an efficient way. To this end, it is necessary to evaluate formulas on structures multiple times. We review the requirements a solver must satisfy to handle this efficiently and present an interesting method to play such games.
Slides download