Repetition-freeness with Cyclic Relations and Chain Relations

Issue title: Words, Graphs, Automata, and Languages; Special Issue Honoring the 60th Birthday of Professor Tero Harju

Article type: Research Article

Authors: Kärki, Tomi^;

Affiliations: Department of Teacher Education, University of Turku, PO Box 175, 26101 Rauma, Finland | Department of Mathematics, University of Turku, 20014 Turku, Finland, topeka@utu.fi

Note: [] Address for correspondence: Department of Teacher Education, University of Turku, PO Box 175, 26101 Rauma, Finland

Abstract: A similarity relation R is a relation on words of equal length induced by a symmetric and reflexive relation on letters. Such a relation is called cyclic if the graph of the relation on letters is a cycle. A chain relation is obtained from a cyclic relation by removing one symmetric relation from the cycle. A word uv is an R-square if u and v are in relation R. The avoidability index of R-squares is the size of the minimal alphabet such that there exists an R-square-free infinite word having infinitely many occurrences of each letter of the alphabet. We prove that the avoidability index of R-squares is 7 in the case of cyclic relations and 6 in the case of chain relations. We also consider R-overlaps and show that they are 5-avoidable with cyclic relations and 4-avoidable with chain relations.

DOI: 10.3233/FI-2012-676

Journal: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 157-174, 2012