My presentation is about effective characterisations: given a representation of a regular language, decide if the language is “simple” in some specific sense. A classical example of such a characterisation is the result by Schutzenberger, McNaughton, and Papert, saying that it is decidable if a given regular language of finite words can be defined in first-order logic. Over the years, such characterisations were provided for many other natural classes of languages, especially in the case of finite and infinite words. It is often assumed that a “golden standard” for such a characterisation is to provide equations that must be satisfied in a respective algebra representing the language.

The aim of my talk is to survey a number of examples in which it is not possible to provide algebraic representation of the considered languages; but instead characterisations can be obtained by a well-designed game of infinite duration. Using these examples, I will try to argue that game-based approach is the natural replacement for algebraic framework in the cases where algebraic representations are not available.