Infinite Separation between General and Chromatic Memory

Alexander Kozachinskiy

Abstract

In this paper, we construct a winning condition $W$ over a finite set of colors such that, first, every finite arena has a strategy with 2 states of general memory which is optimal w.r.t.~$W$, and second, there exists no $k$ such that every finite arena has a strategy with $k$ states of chromatic memory which is optimal w.r.t.~$W$.
BibTeX
@inproceedings{kozachinskiy2022infinite,
  author = {Alexander Kozachinskiy},
  title = {{Infinite Separation between General and Chromatic Memory}},
  booktitle = {LATIN},
  year = {2022},
  doi = {10.1007/978-3-031-55601-2\_8},
}

Loading related content...

Figure