On the complexity functions of Sturmian words

The key issue of the paper is combinatorial complexity functions of infinite words, especially factor complexity and its modifications. First of all, we present an overview of the available results for the class of words with the minimal factor complexity - Sturmian words. Special attention is paid to the arithmetical complexity of infinite words, the study of which was initiated by Van der Waarden Theorem on one-color arithmetic progressions. Arithmetical complexity is presented in a sense a modification of factor complexity. An overview of current results and exact values of arithmetic complexity for Sturmian words is presented. We present polynomial Van der Waerden Theorem, which gives rise to the study of a more generalized modification of the factor complexity function - the polynomial complexity of infinite words. In conclusion, we present open problems for further research.