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
Abstract
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 https://creativecommons.org/licenses/by-nc-nd/4.0/(opens 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 |
Preview
Available under License Creative Commons Attribution Non-commercial No Derivatives.
Download (352kB) | Preview
Export
Downloads
Downloads per month over past year
Metadata
Metadata
MetadataAltmetric
CORE (COnnecting REpositories)
Actions (login required)
Actions (login required)
Admin Login