Finite-Repetition threshold for infinite ternary words
The exponent of a word is the ratio of its length over its smallest period. The repetitive threshold r(a) of an a-letter alphabet is the smallest rational number for which there exists an infinite word whose finite factors have exponent at most r(a). This notion was introduced in 1972 by Dejean who...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2011-08-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1108.3619v1 |
| _version_ | 1828951029531541504 |
|---|---|
| author | Golnaz Badkobeh Maxime Crochemore |
| author_facet | Golnaz Badkobeh Maxime Crochemore |
| author_sort | Golnaz Badkobeh |
| collection | DOAJ |
| description | The exponent of a word is the ratio of its length over its smallest period. The repetitive threshold r(a) of an a-letter alphabet is the smallest rational number for which there exists an infinite word whose finite factors have exponent at most r(a). This notion was introduced in 1972 by Dejean who gave the exact values of r(a) for every alphabet size a as it has been eventually proved in 2009. The finite-repetition threshold for an a-letter alphabet refines the above notion. It is the smallest rational number FRt(a) for which there exists an infinite word whose finite factors have exponent at most FRt(a) and that contains a finite number of factors with exponent r(a). It is known from Shallit (2008) that FRt(2)=7/3. With each finite-repetition threshold is associated the smallest number of r(a)-exponent factors that can be found in the corresponding infinite word. It has been proved by Badkobeh and Crochemore (2010) that this number is 12 for infinite binary words whose maximal exponent is 7/3. We show that FRt(3)=r(3)=7/4 and that the bound is achieved with an infinite word containing only two 7/4-exponent words, the smallest number. Based on deep experiments we conjecture that FRt(4)=r(4)=7/5. The question remains open for alphabets with more than four letters. Keywords: combinatorics on words, repetition, repeat, word powers, word exponent, repetition threshold, pattern avoidability, word morphisms. |
| first_indexed | 2024-12-14T06:31:55Z |
| format | Article |
| id | doaj.art-2bec3ff67b2e4ebaac74bc05f5fef4f4 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-14T06:31:55Z |
| publishDate | 2011-08-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-2bec3ff67b2e4ebaac74bc05f5fef4f42022-12-21T23:13:30ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802011-08-0163Proc. WORDS 2011374310.4204/EPTCS.63.7Finite-Repetition threshold for infinite ternary wordsGolnaz BadkobehMaxime CrochemoreThe exponent of a word is the ratio of its length over its smallest period. The repetitive threshold r(a) of an a-letter alphabet is the smallest rational number for which there exists an infinite word whose finite factors have exponent at most r(a). This notion was introduced in 1972 by Dejean who gave the exact values of r(a) for every alphabet size a as it has been eventually proved in 2009. The finite-repetition threshold for an a-letter alphabet refines the above notion. It is the smallest rational number FRt(a) for which there exists an infinite word whose finite factors have exponent at most FRt(a) and that contains a finite number of factors with exponent r(a). It is known from Shallit (2008) that FRt(2)=7/3. With each finite-repetition threshold is associated the smallest number of r(a)-exponent factors that can be found in the corresponding infinite word. It has been proved by Badkobeh and Crochemore (2010) that this number is 12 for infinite binary words whose maximal exponent is 7/3. We show that FRt(3)=r(3)=7/4 and that the bound is achieved with an infinite word containing only two 7/4-exponent words, the smallest number. Based on deep experiments we conjecture that FRt(4)=r(4)=7/5. The question remains open for alphabets with more than four letters. Keywords: combinatorics on words, repetition, repeat, word powers, word exponent, repetition threshold, pattern avoidability, word morphisms.http://arxiv.org/pdf/1108.3619v1 |
| spellingShingle | Golnaz Badkobeh Maxime Crochemore Finite-Repetition threshold for infinite ternary words Electronic Proceedings in Theoretical Computer Science |
| title | Finite-Repetition threshold for infinite ternary words |
| title_full | Finite-Repetition threshold for infinite ternary words |
| title_fullStr | Finite-Repetition threshold for infinite ternary words |
| title_full_unstemmed | Finite-Repetition threshold for infinite ternary words |
| title_short | Finite-Repetition threshold for infinite ternary words |
| title_sort | finite repetition threshold for infinite ternary words |
| url | http://arxiv.org/pdf/1108.3619v1 |
| work_keys_str_mv | AT golnazbadkobeh finiterepetitionthresholdforinfiniteternarywords AT maximecrochemore finiterepetitionthresholdforinfiniteternarywords |