Infinite Games on Finite Graphs

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.advisor Khoussainov, B en Walls, Samuel en 2017-06-19T03:12:34Z en 2017 en
dc.identifier.uri 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 en
dc.rights.uri en
dc.title Infinite Games on Finite Graphs en
dc.type Thesis en Mathematics en The University of Auckland en 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 Except where otherwise noted, this item's license is described as


Search ResearchSpace

Advanced Search