The Complexity of Robot Games on the Integer Line

Arjun Arul
Julien Reichert

In robot games on Z, two players add integers to a counter. Each player has a finite set from which he picks the integer to add, and the objective of the first player is to let the counter reach 0. We present an exponential-time algorithm for deciding the winner of a robot game given the initial counter value, and prove a matching lower bound.

In Luca Bortolussi and Herbert Wiklicky: Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2013), Rome, 23rd-24th March 2013, Electronic Proceedings in Theoretical Computer Science 117, pp. 132–148.
Published: 11th June 2013.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: