Infinite Games on Finite Graphs

ResearchSpace/Manakin Repository

Show simple item record

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


Full text options

This item appears in the following Collection(s)

Show simple item record

http://creativecommons.org/licenses/by-nc-sa/3.0/nz/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc-sa/3.0/nz/

Share

Search ResearchSpace


Advanced Search

Browse