Hi everyone,(adsbygoogle = window.adsbygoogle || []).push({});

Duval' algorithm computes all the k-ary Lyndon words up to any length, say n. See here for a brief introduction to Lyndon words and note the section Generation.

http://en.wikipedia.org/wiki/Lyndon_word

The article claims that

"the sequence of all Lyndon words of length at most n can be generated in time proportional to the length of the sequence" and cites this paper:

http://www-igm.univ-mlv.fr/~berstel/Articles/1994AverageCostDuval.pdf

Now, I have implemented Duval's algorithm for the binary case (see below) in C++ and noted that the computation time increases by a factor of almost 2 whenever the length of the sequence increases by 1. This starts becoming especially noticeable by about length 25. This I think would seem to suggest that the time complexity is actually exponential, which contradicts the claim of the linear complexity of the algorithm. As I'm not an expert in C++, I'm wondering if I'm implementing this incorrectly, or inefficiently. What do you think? Here's the algorithm.

In the binary case, i.e., k=2, Duval's algorithm simplifies to the following.

w[1] ← 0

i ← 1

repeat:

for j = 1 to n–i do

w[i+j] ← w[j]

/* at this point, w[1...i] is a Lyndon word */

i ← n

while i > 0 and w= 1

do i ← i–1

if i > 0 then w← 1

until i = 0

end

You may find the algorithm in page 2 of this link as well:

http://ehess.modelisationsavoirs.fr/marc/publi/softcomputing/5000387periodicity.pdf

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Lyndon words: Duval's algorithm and its time complexity

Loading...

Similar Threads - Lyndon words Duval's | Date |
---|---|

C++ prog. to reverse each word in sentence | Nov 7, 2015 |

Colored Words or Numbers in VB6 | Oct 7, 2015 |

Eigenword embeddings and spectral learning; I'm a beginner... | Jun 12, 2015 |

Programming a cyborg just by typing words? | Feb 19, 2015 |

**Physics Forums - The Fusion of Science and Community**