Extracting winning strategies in update games
| aut.researcher | Liu, Jiamou | |
| dc.contributor.author | Liu, J | |
| dc.contributor.author | Khaliq, I | |
| dc.contributor.author | Khoussainov, B | |
| dc.contributor.editor | Löwe, BL | |
| dc.contributor.editor | Norman, DN | |
| dc.contributor.editor | Soskov, IS | |
| dc.contributor.editor | Soskova, AS | |
| dc.date.accessioned | 2011-11-27T03:00:38Z | |
| dc.date.available | 2011-11-27T03:00:38Z | |
| dc.date.copyright | 2011-06-27 | |
| dc.date.issued | 2011-06-27 | |
| dc.description.abstract | This paper investigates algorithms for extracting winning strategies in two-player games played on nite graphs. We focus on a special class of games called update games. We present a procedure for extracting winning strategies in update games by constructing strategies explicitly. This is based on an algorithm that solves update games in quadratic time. We also show that solving update games with a bounded number of nondeterministic nodes takes linear time. | |
| dc.identifier.citation | Computer Science: models of Computation in Context: proceedings from the 7th Conference on Computability in Europe (CiE'11), Sofia, Bulgaria, vol.6735, pp. 142 - 151 | |
| dc.identifier.doi | 10.1007/978-3-642-21875-0_15 | |
| dc.identifier.isbn | 978-3-642-21874-3 | |
| dc.identifier.issn | 0302-9743 (Print) 1611-3349 (Online) | |
| dc.identifier.uri | https://hdl.handle.net/10292/2807 | |
| dc.publisher | Springer Berlin / Heidelberg | |
| dc.relation.uri | http://dx.doi.org/10.1007/978-3-642-21875-0_15 | |
| dc.rights | An author may self-archive an author-created version of his/her article on his/her own website and or in his/her institutional repository. He/she may also deposit this version on his/her funder’s or funder’s designated repository at the funder’s request or as a result of a legal obligation, provided it is not made publicly available until 12 months after official publication. He/ she may not use the publisher's PDF version, which is posted on www.springerlink.com, for the purpose of self-archiving or deposit. Furthermore, the author may only post his/her version provided acknowledgement is given to the original source of publication and a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at www.springerlink.com”. (Please also see Publisher’s Version and Citation) | |
| dc.rights.accessrights | OpenAccess | |
| dc.subject | Games | |
| dc.subject | Update networks | |
| dc.subject | Finite state strategies | |
| dc.title | Extracting winning strategies in update games | |
| 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 |