Reconstructing a string from its Lyndon arrays

J.W. Daykin; F. Franěk; J. Holub; A.S.M.S. Islam; W.F. Smyth

doi:10.1016/j.tcs.2017.04.008

Back

Reconstructing a string from its Lyndon arrays

Journal article

Open access

Peer reviewed

Reconstructing a string from its Lyndon arrays

J.W. Daykin, F. Franěk, J. Holub, A.S.M.S. Islam and W.F. Smyth

Theoretical Computer Science, Vol.710, pp.44-51

2017

DOI: https://doi.org/10.1016/j.tcs.2017.04.008

Files and links (2)

pdf

lyndon arrays.pdfDownload View

Author’s Version Open Access

url

Link to Published Version *Subscription may be requiredView

Abstract

Given a string x=x[1..n]x=x[1..n] on an ordered alphabet Σ of size σ , the Lyndon array λ=λx[1..n]λ=λx[1..n] of x is an array of positive integers such that View the MathML sourceλ[i],1≤i≤n, is the length of the maximal Lyndon word over the ordering of Σ that begins at position i in x . The Lyndon array has recently attracted considerable attention due to its pivotal role in establishing the long-standing conjecture that ρ(n)<nρ(n)<n, where ρ(n)ρ(n) is the maximum number of maximal periodicities (runs) in any string of length n. Here we first describe two linear-time algorithms that, given a valid Lyndon array λ, compute a corresponding string — one for an alphabet of size n, the other for a smaller alphabet. We go on to describe another linear-time algorithm that determines whether or not a given integer array is a Lyndon array of some string. Finally we show how σ Lyndon arrays λΣ={λ1=λ,λ2,…,λσ}λΣ={λ1=λ,λ2,…,λσ} corresponding to σ “rotations” of the alphabet can be used to determine uniquely the string x on Σ such that λx=λλx=λ.

Details

Title: Reconstructing a string from its Lyndon arrays
Authors/Creators: J.W. Daykin (Author/Creator) - Aberystwyth University
F. Franěk (Author/Creator) - McMaster University
J. Holub (Author/Creator) - Czech Technical University in Prague
A.S.M.S. Islam (Author/Creator) - McMaster University
W.F. Smyth (Author/Creator) - McMaster University
Publication Details: Theoretical Computer Science, Vol.710, pp.44-51
Publisher: Elsevier BV
Identifiers: 991005544674307891
Murdoch Affiliation: School of Engineering and Information Technology
Language: English
Resource Type: Journal article

Metrics

76 File views/ downloads

84 Record Views

8 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.1103 Efficient Algorithms
Web Of Science research areas: Computer Science, Theory & Methods
ESI research areas: Computer Science