AUT LibraryAUT
View Item 
  •   Open Research
  • AUT Faculties
  • Faculty of Design and Creative Technologies (Te Ara Auaha)
  • School of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, Pāngarau
  • View Item
  •   Open Research
  • AUT Faculties
  • Faculty of Design and Creative Technologies (Te Ara Auaha)
  • School of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, Pāngarau
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Solving infinite games on trees with back-edges

Liu, J; Khoussainov, B; Gandhi, A
Thumbnail
View/Open
full.pdf (387.7Kb)
Permanent link
http://hdl.handle.net/10292/2819
Metadata
Show full metadata
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).
Date
January 2012
Source
In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 113-122
Item Type
Conference Contribution
Publisher
Australian Computer Society (ACS)
Publisher's Version
http://crpit.com/abstracts/CRPITV128Gandhi.html
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.

Contact Us
  • Admin

Hosted by Tuwhera, an initiative of the Auckland University of Technology Library

 

 

Browse

Open ResearchTitlesAuthorsDateSchool of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, PāngarauTitlesAuthorsDate

Alternative metrics

 

Statistics

For this itemFor all Open Research

Share

 
Follow @AUT_SC

Contact Us
  • Admin

Hosted by Tuwhera, an initiative of the Auckland University of Technology Library