|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 15 of 22 found articles
| Title: |
Repetition-freeness with Cyclic Relations and Chain Relations |
| Author: |
Kärki, Tomi |
| Appeared in: |
Fundamenta informaticae |
| Paging: | Volume 116 (2012) nr. 1-4 pages 157-174 |
| Year: |
2012-05-16 |
| Contents: |
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. |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 15 of 22 found articles
| << previous | next >> |