Journal article
A fast average case algorithm for lyndon decomposition
International Journal of Computer Mathematics, Vol.57(1-2), pp.15-31
1995
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.
Details
- Title
- A fast average case algorithm for lyndon decomposition
- Authors/Creators
- C.S. Iliopoulos (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- International Journal of Computer Mathematics, Vol.57(1-2), pp.15-31
- Publisher
- Taylor & Francis
- Identifiers
- 991005545510307891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
246 File views/ downloads
66 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Mathematics, Applied
- ESI research areas
- Engineering