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

Preview

Text LeftLyndonTree-v10.pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (338kB) | Preview

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:	Article
Identification Number (DOI):	https://doi.org/10.1016/j.ic.2022.104884
Keywords:	Lyndon tree, infinite ordering, prefix sorting, linear algorithm, general alphabet
Departments, Centres and Research Units:	Computing
Dates:	Date Event 23 February 2022 Accepted 3 June 2022 Published Online May 2022 Published
Item ID:	31519
Date Deposited:	24 Feb 2022 12:58
Last Modified:	25 Feb 2023 02:26
Peer Reviewed:	Yes, this version has been peer-reviewed.
URI:	https://research.gold.ac.uk/id/eprint/31519

View statistics for this item...

Edit Record (login required)