JavaScript is disabled for your browser. Some features of this site may not work without it.
| dc.contributor.advisor | Khoussainov, B | en |
| dc.contributor.author | Walls, Samuel | en |
| dc.date.accessioned | 2017-06-19T03:12:34Z | en |
| dc.date.issued | 2017 | en |
| dc.identifier.uri | http://hdl.handle.net/2292/33600 | en |
| dc.description | Full text is available to authenticated members of The University of Auckland only. | en |
| dc.description.abstract | In this thesis, we give an exposition of the theory of infinite games on finite graphs as developed byMcNaughton. Following Hunter, we discuss several representations of such games, and prove a number of results regarding their equivalence. We discuss the important determinacy results of Martin and Buchi-Landweber, and give Zielonka’s recursive algorithm to solve parity games. We then discuss the work of Dinneen and Khoussainov on update games, and the important result of Horn regarding the polynomial-time solvability of explicit Muller games. We then give the algorithm of McNaughton to solve win-set games in exponential time, and discuss some results regarding coloured Muller games. | en |
| dc.publisher | ResearchSpace@Auckland | en |
| dc.relation.ispartof | Masters Thesis - University of Auckland | en |
| dc.relation.isreferencedby | UoA99265050407702091 | en |
| dc.rights | Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. | en |
| dc.rights | Restricted Item. Available to authenticated members of The University of Auckland. | en |
| dc.rights.uri | https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm | en |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-sa/3.0/nz/ | en |
| dc.title | Infinite Games on Finite Graphs | en |
| dc.type | Thesis | en |
| thesis.degree.discipline | Mathematics | en |
| thesis.degree.grantor | The University of Auckland | en |
| thesis.degree.level | Masters | en |
| dc.rights.holder | Copyright: The author | en |
| pubs.elements-id | 631239 | en |
| pubs.record-created-at-source-date | 2017-06-19 | en |
| dc.identifier.wikidata | Q112935194 |
Files in this item
This item appears in the following Collection(s)
Share
