Trading Bounds for Memory in Games with Counters

June 8, 2015

Nathanaël Fijalkow (LIAFA - Université Paris Diderot)

We study two-player games with counters played on graphs. We investigate a conjecture by Colcombet and Löding which states the existence of a trade-off between the size of the memory and the bound achieved on the counters. They proved that this conjecture implies the decidability of cost monadic second-order logic over infinite trees, as well as the decidability of the Rabin-Mostowski parity index.

We show that unfortunately the conjecture does not hold: there is no trade-off between bounds and memory, even for finite arenas. On the positive side, we prove the existence of a trade-off for the special case of thin tree arenas. This allows to extend the theory of regular cost functions over thin trees, and obtain as a corollary the decidability of cost monadic second-order logic over thin trees.

This is a joint work with Florian Horn, Denis Kuperberg and Michał Skrzypczak, which will be presented at ICALP’2015. The talk will be in French if everyone in the audience speaks French.