FAST AVERAGE-CASE ALGORITHM FOR LYNDON DECOMPOSITION

A simple algorithm, called LD, is described for computing the Lyndon d ecomposition of a word of length n. Although LD requires time O(n log n) in the worst case, it is shown to require only Theta(n) worst-case time for words which are ''1-decomposable'', and Theta(n) average-case time for words whose length is small with respect to alphabet size. T he main interest in LD resides in its application to the problem of co mputing 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 ap plied to arbitrary words, LD on average outperforms the other known ca nonization algorithms in terms of two measures: number of tests on let ters and execution time.