A4 Refereed article in a conference publication

On Robot Games of Degree Two




AuthorsVesa Halava, Reino Niskanen, Igor Potapov

Conference nameInternational Conference on Language and Automata Theory and Applications

PublisherSpringer, Cham

Publication year2015

Book title Language and Automata Theory and Applications - 9th International Conference, {LATA} 2015, Nice, France, March 2-6, 2015, Proceedings

Series titleLecture Notes in Computer Science

Volume8977

First page 224

Last page236

ISBN978-952-12-3014-1

ISSN0302-9743

DOIhttps://doi.org/10.1007/978-3-319-15579-1_17

Web address http://dx.doi.org/10.1007/978-3-319-15579-1_17


Abstract

Robot Game is a two player vector addition game played

in integer lattice Zn. In a degree k case both players have k vectors

and in each turn the vector chosen by a player is added to the current

configuration vector of the game. One of the players, called Attacker,

tries to play the game from the initial configuration to the origin while

the other player, Defender, tries to avoid origin. The decision problem is

to decide whether or not Attacker has a winning strategy. We prove that

the problem is decidable in polynomial time for the degree two games in

any dimension n.




Last updated on 2024-26-11 at 14:13