Solving infinite games on trees with back-edges
Files
Date
Authors
Supervisor
Item type
Conference Contribution
Degree name
Journal Title
Journal ISSN
Volume Title
Publisher
Australian Computer Society (ACS)
Abstract
We study the computational complexity of solving the following problem: Given a game G played on a fi- nite directed graph G, output all nodes in G from which a specific player wins the game G. We pro- vide 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,ℓ+m}) where m is the number of edges, ℓ 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(ℓ + m).Description
Keywords
Source
In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 113-122
DOI
Publisher's version
Rights statement
NOTICE: this is the author’s version of a work that was accepted for presentation. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication.