Mathematics – Combinatorics
Scientific paper
2003-04-07
Mathematics
Combinatorics
12 pages
Scientific paper
It is known that the number of overlap-free binary words of length n grows polynomially, while the number of cubefree binary words grows exponentially. We show that the dividing line between polynomial and exponential growth is 7/3. More precisely, there are only polynomially many binary words of length n that avoid 7/3-powers, but there are exponentially many binary words of length n that avoid (7/3+)-powers. This answers an open question of Kobayashi from 1986.
Karhumäki Juhani
Shallit Jeffrey
No associations
LandOfFree
Polynomial versus Exponential Growth in Repetition-Free Binary Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Polynomial versus Exponential Growth in Repetition-Free Binary Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial versus Exponential Growth in Repetition-Free Binary Words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-522243