Talk:Lyndon word

This was requested! however all it really entails is a definition...perhaps a redirect? Wikipedia appears to be lacking in general on the broader subject however. Robbjedi 04:45, 18 October 2005 (UTC)

Necklace

I am not merging this into necklace (combinatorics), as Lyndon word is a standalone concept, deserving its own article. Hope nobody minds. Kompas 09:49, 3 August 2006 (UTC)

"A theorem of Radford states...."

needs a reference 173.206.238.69 (talk) 00:26, 21 May 2012 (UTC)

Why periodic strings are omitted?

What's wrong to include the strings "00", "11" etc. in the sequence? --RokerHRO (talk) 15:17, 7 July 2014 (UTC)

They are equal to their rotations, and therefore are not the unique smallest string among their rotations. Also because then the standard factorization wouldn't work. —David Eppstein (talk) 16:02, 7 July 2014 (UTC)

Algorithm dubious?

The algorithm given for computing the standard factorisation looks to be quadratic rather than linear as stated. If the input is 'bbbb...bbba' (n 'b's, 1 'a') then the algorithm takes O(n) time to find the first Lyndon word in the factorisation is 'b', and then it proceeds to factorise 'bbbb...bbba' (with n-1 'b's).

Also, I think the algorithm's finishing condition is faulty, unless it assumes the string ends with a terminating character that's smaller than every other character. As written, 'aa' will factorise as ['aa'] rather than ['a', 'a']. 125.30.89.127 (talk) 08:59, 3 November 2014 (UTC)

Plus one to faulty finishing condition - from what I gathered one should iterate until the string is empty, and treat m reaching the end of the string as also going to step 3.3.

Also (but that could just be me) I could only understand the algorithm as described after I understood the algorithm already, it isn't clear that it starts with the assumption that a single letter initial Lyndon word is the best it can do and tries proving (3.3) or disproving said assumption by looking at further letters, each time learning a new length assumption for the initial Lyndon word when the previous assumption is proven false (3.2), where equality contributes "nothing".

I also agree with the quadratic runtime assessment, which is most likely due to case 3.3 discarding all accumulated knowledge, though I wouldn't yet know how to do better. 193.227.108.10 (talk) 13:11, 12 November 2014 (UTC)

The numbers of binary Lyndon words of each length

(For starters, English is not my primary language..) My first understanding of this was:

Every binary Lyndon word of each length has its own number.

Probably just my fault, but wouldnt the word amounts be a tiny bit more exact? Although it doesnt sound that good. Or could someone think of another way to say it?

Anyway, if anyone else had trouble understanding, the sequence 1, 2, 1, ... means:

• 1 word of length 0 - ε
• 2 words of length 1 - 0,1
• 1 word of length 2 - 01
• ... — Preceding unsigned comment added by 147.32.31.193 (talk) 18:18, 5 November 2014 (UTC)

Actually, "amounts" would be a word you'd use for a continuous quantity (a real number like an amount of water) while number makes more sense for discrete integer values (a number of glasses of water). —David Eppstein (talk) 18:32, 5 November 2014 (UTC)