Relationally Periodic Sequences and Subword Complexity

By the famous theorem of Morse and Hedlund, a word is ultimately periodic if and only if it has bounded subword complexity, i.e., for sufficiently large n, the number of factors of length nis constant. In this paper we consider relational periods and relationally periodic sequences, where the relation is a similarity relation on words induced by a compatibility relation on letters. We investigate what would be a suitable definition for a relational subword complexity function such that it would imply a Morse and Hedlund-like theorem for relationally periodic words. We consider strong and weak relational periods and two candidates for subword complexity functions.