Tree Games with Regular Objectives

We study tree games developed recently by Matteo Mio as a game interpretation of the probabilistic μ -calculus. With expressive power comes complexity. It was shown that tree games are able to encode the Blackwell games and, consequently, are not determined under deterministic strategies. First, we will show that tree games with objectives recognisable by so-called game automata are determined under deterministic, finite memory strategies. Then, for the case of arbitrary regular languages of trees, we will present an exponential time algorithm for deciding the determinacy of a finite tree game under deterministic strategies.

Authors

• Marcin Przybyłko Department of Computer Science, Leipzig University, Germany Institute of Informatics, University of Warsaw, Poland

Keywords

No keywords are indexed for this paper.