Linear Construction of a Left Lyndon Tree

Badkobeh, Golnaz and Crochemore, Maxime. 2022. Linear Construction of a Left Lyndon Tree. Information and Computation, 285(B), 104884. ISSN 0890-5401 [Article]

No full text available
[img] Text
LeftLyndonTree-v10.pdf - Accepted Version
Permissions: Administrator Access Only until 25 February 2023.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (338kB)

Abstract or Description

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.

Item Type:


Identification Number (DOI):


Lyndon tree, infinite ordering, prefix sorting, linear algorithm, general alphabet

Departments, Centres and Research Units:



23 February 2022Accepted
3 June 2022Published Online
May 2022Published

Item ID:


Date Deposited:

24 Feb 2022 12:58

Last Modified:

20 Jun 2022 14:03

Peer Reviewed:

Yes, this version has been peer-reviewed.


View statistics for this item...

Edit Record Edit Record (login required)