15
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

A fast average case algorithm for lyndon decomposition

&
Pages 15-31 | Received 26 Sep 1994, Published online: 19 Mar 2007
 

Abstract

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.

C.R. Category:

AMS Subject Classification:

*School of Computing, Curtin University of Technology, Perth WA 6001, Australia.

*School of Computing, Curtin University of Technology, Perth WA 6001, Australia.

*School of Computing, Curtin University of Technology, Perth WA 6001, Australia.

*School of Computing, Curtin University of Technology, Perth WA 6001, Australia.

Notes

*School of Computing, Curtin University of Technology, Perth WA 6001, Australia.

*School of Computing, Curtin University of Technology, Perth WA 6001, Australia.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.