Similarity Relations and Repetition-Freeness

摘要

A similarity relation is a relation on words of equal length induced by a symmetric and reflexive relation on letters. The aim of this article is to give an overview of the results concerning repetitionfreeness in connection with similarity relations. We consider so called chain relations, cyclic relations and partial words, which can be seen as a special case of similarity relations. As a new result, we prove that local 3~+-repetitions can be avoided in binary partial words and the local avoidability index of R-cubes is five, where R is a relation such that the graph of the relation is a cycle.