Infinite Separation between General and Chromatic Memory

Alexander Kozachinskiy

In this note, we answer a question from [Alexander Kozachinskiy. State Complexity of Chromatic Memory in Infinite-Duration Games, arXiv:2201.09297]. Namely, 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 with respect to $W$, and second, there exists no $k$ such that every finite arena has a strategy with $k$ states of chromatic memory which is optimal with respect to $W$.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment