- #1
burritoloco
- 83
- 0
Hi everyone,
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
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
Last edited: