Skip to main content

Games with bound guess actions

Thomas Colcombet ( IRIF, Université Paris 7 )

We introduce *games with (bound) guess actions*. These are games in which the players may be asked along the  play to provide numbers that need to satisfy some bounding constraints.  These are natural extensions of domination games occurring in the regular cost function theory. In this talk we consider more specifically the case where the constraints to be bounded are regular cost functions, and the long term goal is an omega-regular winning condition. We show that such games are decidable on finite arenas.

Such models allows us to model properties such as "in a printer spooler interacting with users, is it possible to bound the printing time as a function of the number of pages of the files". One of the players declares an upper bound on the number of pages of the file, and the other answers with printing-time guarantee.

This is a collaboration with Stefan Göller.

Share this: