City Research Online

Linear construction of a left Lyndon tree

Badkobeh, G. ORCID: 0000-0001-5550-7149 & Crochemore, M. (2022). Linear construction of a left Lyndon tree. Information and Computation, 285(Part B), article number 104884. doi: 10.1016/j.ic.2022.104884


We extend the left-to-right Lyndon factorisation of a word to the left Lyndon tree construction of a Lyndon word. It yields an algorithm to sort the prefixes of a Lyndon word according to the infinite ordering defined by Dolce et al. (2019). A straightforward variant computes the left Lyndon forest of a word. All algorithms run in linear time on a general alphabet, that is, in the letter-comparison model.

Publication Type: Article
Additional Information: © 2022. This manuscript version is made available under the CC-BY-NC-ND 4.0 license in new tab/window)
Publisher Keywords: Lyndon tree, Infinite ordering, Prefix sorting, Linear algorithm, General alphabet
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science
[thumbnail of linear construction of a left.pdf]
Text - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (352kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login