Solving infinite games on trees with back-edges
| aut.researcher | Liu, Jiamou | |
| dc.contributor.author | Liu, J | |
| dc.contributor.author | Khoussainov, B | |
| dc.contributor.author | Gandhi, A | |
| dc.date.accessioned | 2011-11-27T08:42:52Z | |
| dc.date.available | 2011-11-27T08:42:52Z | |
| dc.date.copyright | 2012-01 | |
| dc.date.issued | 2012-01 | |
| dc.description.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). | |
| dc.identifier.citation | In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 113-122 | |
| dc.identifier.issn | 1445-1336 | |
| dc.identifier.uri | https://hdl.handle.net/10292/2819 | |
| dc.publisher | Australian Computer Society (ACS) | |
| dc.relation.uri | http://crpit.com/abstracts/CRPITV128Gandhi.html | |
| dc.rights | 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. | |
| dc.rights.accessrights | OpenAccess | |
| dc.title | Solving infinite games on trees with back-edges | |
| dc.type | Conference Contribution | |
| pubs.organisational-data | /AUT | |
| pubs.organisational-data | /AUT/Design & Creative Technologies | |
| pubs.organisational-data | /AUT/Design & Creative Technologies/School of Computing & Mathematical Science | |
| pubs.organisational-data | /AUT/PBRF Researchers | |
| pubs.organisational-data | /AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers | |
| pubs.organisational-data | /AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers/DCT C & M Computing |