We study zero-sum games played on graphs and present contributions toward the following question: given an objective, how much memory is required to play optimally? This question has been well-studied since the 1980s, with complete answers for large classes of omega-regular objectives. Nevertheless, there is still no precise general answer for arbitrary omega-regular objectives, despite their significance in various fields. Toward this goal, we study a simple subclass of the omega-regular objectives that we call the regular objectives. In such games, the goal of one of the two players is that, eventually, the sequence of colors along the play belongs to some regular language of finite words. We obtain different characterizations of the memory requirements for such objectives for both players, from which we derive complexity-theoretic statements: deciding whether there exist small memory structures sufficient to play optimally is NP-complete for both players. Some of our characterization results apply to a more general class of objectives: topologically closed and topologically open sets.
These results are based on joint work with Patricia Bouyer, Nathanaël Fijalkow, and Mickael Randour.