Bachelor's thesis
Awards: Dean's Award for an Outstanding Final Thesis

Complexity of Consumption Games

David Klaška, UČO 374303
Abstract

Práce se zabývá tzv. consumption games, hrami dvou hráčů, které modelují interaktivní systémy s několika typy zdrojů, jež jsou průběžně spotřebovávány a doplňovány nezávisle na sobě. Konkrétně řešíme problémy prázdnosti, příslušnosti a minimálních vektorů. U každého z těchto tří problémů klasifikujeme podtřídy consumption games, pro něž jsou řešitelné v polynomiálním čase. Dále ukazujeme, že vně těchto tříd jsou řešené problémy výpočetně těžké.

Abstract

We study consumption games, a model for interactive systems with several resource types which are consumed and reloaded independently. Several naturally arising problems about consumption games have been studied, namely the emptiness problem, the membership problem, and the minimal-resource problem. For each of these problems, we classify subclasses of consumption games for which it is solvable in …more

Keywords
consumption games binary encoding polynomially solvable emptiness problem membership problem minimal-resource problem one-player games one-dimensional consumption games decreasing consumption games single-reloading consumption games
Thesis description
The goal is to investigate computational complexity of solving so called consumption games, a special form of two-player, turn-based games with counters. First, the thesis should briefly survey existing results. Second, the thesis should identify subclasses of consumption games that can be efficiently solved.
Administrative information
The thesis has been checked:
20/1/2014 09:25, doc. RNDr. Tomáš Brázdil, Ph.D., MBA, UČO 4074
Full text of thesis
285,5 KB / file PDF
Language used
English English
Defence date
7/2/2014
The thesis was defended successfully

Supervisor

doc. RNDr. Tomáš Brázdil, Ph.D., MBA, UČO 4074
ITI FI MU

Reader

prof. RNDr. Mojmír Křetínský, CSc., UČO 631
KTP FI MU

Literature

  • BRÁZDIL, Tomáš; Krishnendu CHATTERJEE; Antonín KUČERA and Petr NOVOTNÝ. Efficient Controller Synthesis for Consumption Games with Multiple Resource Types. In Computer Aided Verification - 24th International Conference, CAV 2012. Berlin: Springer, 2012, p. 23-38. ISBN 978-3-642-31423-0. Available from: https://doi.org/10.1007/978-3-642-31424-7_8.
Cite this text
Masaryk University Faculty of Informatics
Programme
Informatics
Field of Study

Theses on a related topic

List of theses with an identical keyword.

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.