Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Repetition-freeness with Cyclic Relations and Chain Relations

Kärki T.

Fundamenta Informaticae

2012

Vol. 116, nr 1-4

157-174

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.