Solving infinite games on trees with back-edges

Gandhi, A., Khoussainov, B. and Liu, J.

We study the computational complexity of solving the following problem: Given a game G played on a finite directed graph G, output all nodes in G from which a specific player wins the game G. We provide algorithms for solving the above problem when the games have B�chi and parity winning conditions and the graph G is a tree with back-edges. The running time of the algorithm for B�chi games is O(min{r ・m, l+m}) where m is the number of edges, l is the sum of the distances from the root to all leaves and the parameter r is bounded by the height of the tree. The algorithm for parity has a running time of O(l + m).

Cite as: Gandhi, A., Khoussainov, B. and Liu, J. (2012). Solving infinite games on trees with back-edges. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 113-122

(from crpit.com) (local if available)