Catalog Home Page

A fast average case algorithm for lyndon decomposition

Iliopoulos, C.S. and Smyth, W.F. (1995) A fast average case algorithm for lyndon decomposition. International Journal of Computer Mathematics, 57 (1-2). pp. 15-31.

PDF - Authors' Version
Download (228kB)
Link to Published Version:
*Subscription may be required


A simple algorithm, called LD, is described for computing the Lyndon decomposition of a word of length. Although LD requires time 0(n log n) in the worst case, it is shown to require only ®(rc) worst-case time for words which are “1-decomposable”, and ⊝(n) average-case time for words whose length is small with respect to alphabet size. The main interest in LD resides in its application to the problem of computing the canonical form of a circular word. For this problem, LD is shown to execute significantly faster than other known algorithms on important classes of words. Further, experiment suggests that, when applied to arbitrary words, LD on average outperforms the other known canonization algorithms in terms of two measures: number of tests on letters and execution time.

Publication Type: Journal Article
Publisher: Taylor & Francis
Item Control Page Item Control Page


Downloads per month over past year