Nie jesteś zalogowany |
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
- 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.
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.
