Branching games with regular winning sets

Prelegent(ci)

Marcin Przybyłko

Afiliacja

Uniwersytet Warszawski, University of New Caledonia

Termin

20 kwietnia 2016 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Michał Skrzypczak

Seminarium

Seminarium „Teoria automatów”

---

A branching game is a game that produces trees instead of paths. This is achieved by introducing new type of positions -- branching positions -- that split the game into two independent sub-games. M.Mio defined such games and used them in conjunction with parity winning conditions, so called stochastic meta-parity games, to give game semantics to a variant of probabilistic $\mu$-calculus.

In our work, we consider a natural extension of stochastic meta-parity games in which the winning condition is not defined as a parity condition but as the membership to a regular language of trees. We call such games branching games with regular conditions and are interested in their determinacy and computional properties.

In this talk, I will recall the definition of a Branching Game, focus the attention to winning sets that can be represented as regular languages of trees, and discuss both the determinacy and computational complexity of deciding game values.

---