Linear construction of a left Lyndon tree

Golnaz Badkobeh; Maxime Crochemore

doi:10.1016/j.ic.2022.104884

Linear construction of a left Lyndon tree

Golnaz Badkobeh^*, Maxime Crochemore

^*Corresponding author for this work

Informatics

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	104884
Journal	INFORMATION AND COMPUTATION
Volume	285
Issue number	B
Early online date	3 Jun 2022
DOIs	https://doi.org/10.1016/j.ic.2022.104884
Publication status	E-pub ahead of print - 3 Jun 2022

Keywords

General alphabet
Infinite ordering
Linear algorithm
Lyndon tree
Prefix sorting

Access to Document

10.1016/j.ic.2022.104884

Cite this

@article{2609b5a729ef4d92bc75213080d085b5,

title = "Linear construction of a left Lyndon tree",

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.",

keywords = "General alphabet, Infinite ordering, Linear algorithm, Lyndon tree, Prefix sorting",

author = "Golnaz Badkobeh and Maxime Crochemore",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier Inc.",

year = "2022",

month = jun,

day = "3",

doi = "10.1016/j.ic.2022.104884",

language = "English",

volume = "285",

journal = "INFORMATION AND COMPUTATION",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "B",

}

TY - JOUR

T1 - Linear construction of a left Lyndon tree

AU - Badkobeh, Golnaz

AU - Crochemore, Maxime

PY - 2022/6/3

Y1 - 2022/6/3

N2 - 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.

AB - 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.

KW - General alphabet

KW - Infinite ordering

KW - Linear algorithm

KW - Lyndon tree

KW - Prefix sorting

UR - http://www.scopus.com/inward/record.url?scp=85126514914&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2022.104884

DO - 10.1016/j.ic.2022.104884

M3 - Article

AN - SCOPUS:85126514914

SN - 0890-5401

VL - 285

JO - INFORMATION AND COMPUTATION

JF - INFORMATION AND COMPUTATION

IS - B

M1 - 104884

ER -

Linear construction of a left Lyndon tree

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this