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 | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

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

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

**Physics Forums | Science Articles, Homework Help, Discussion**