Timeline for Subwords of cube-free binary words
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2012 at 0:31 | vote | accept | JRN | ||
| Sep 21, 2012 at 0:30 | comment | added | JRN | There are currently four answers, and I've upvoted all of them. I'm accepting Douglas Zare's answer. Thanks to all for the help. | |
| Sep 20, 2012 at 15:19 | answer | added | Douglas Zare | timeline score: 4 | |
| Sep 20, 2012 at 10:02 | answer | added | Zack Wolske | timeline score: 3 | |
| Sep 20, 2012 at 3:17 | answer | added | ARupinski | timeline score: 1 | |
| Sep 20, 2012 at 0:13 | comment | added | JRN | In addition, on page 606 they provide an example of a cube-free infinite binary word with letter frequencies of $11/27$ and $16/27$. | |
| Sep 20, 2012 at 0:07 | comment | added | JRN | Note that cube-free binary words do not necessarily have equal letter frequencies (although some, like the (infinite) Thue-Morse word, do). See, for example, section 6.1 of a paper by Grimm and Heuer (mdpi.com/1099-4300/10/4/590), where they empirically found that the frequency of a letter in a binary cube-free word (of up to length 80) is between 0.4 and 0.6. | |
| Sep 19, 2012 at 23:01 | comment | added | Gerhard Paseman | Here is a pseudo-elegant suggestion. Suppose you look at cube free words that avoid 010. Then all blocks after the initial block will be 0, 00, or 11. Cube-free words will then have a suffix having mostly 11's. But there are only finitely many ways to avoid cubes with this restriction. Argue similarly for the other five subwords. Gerhard "I'll Take Working Over Elegant" Paseman, 2012.09.19 | |
| Sep 19, 2012 at 22:35 | history | rollback | JRN |
Rollback to Revision 1
|
|
| Sep 19, 2012 at 22:30 | history | edited | JRN | CC BY-SA 3.0 |
Clarified the question
|
| Sep 19, 2012 at 19:09 | answer | added | Gerhard Paseman | timeline score: 1 | |
| Sep 19, 2012 at 17:04 | comment | added | Gerhard Paseman | Just computing by hand, I get less than 30 words of length 8 which begin with 0. All of these have at least 3 of the subwords of length 3, and most have 4,5, or all 6 of them. I bet by the time you get to length 12, there will be very few prefixes to check. Gerhard "I Almost Did It Myself" Paseman, 2012.09.19 | |
| Sep 19, 2012 at 14:37 | comment | added | Gerhard Paseman | In fact, the number of cube free binary words of lrngth n is O(F_n), or about twice or four times the nth Fibonacci number. With judicious pruning, you can compute the words not containing the set by hand. Gerhard "I Might Try It Myself" Paseman, 2012.09.19 | |
| Sep 19, 2012 at 14:16 | comment | added | Gerhard Paseman | It should be resolvable through brute force. Have you done a computer enumeration? Gerhard "Ask Me About System Design" Paseman, 2012.09.18 | |
| Sep 19, 2012 at 13:45 | history | asked | JRN | CC BY-SA 3.0 |