Catalog Home Page

Reconstructing a string from its Lyndon arrays

Daykin, J.W., Franěk, F., Holub, J., Islam, A.S.M.S. and Smyth, W.F. (2017) Reconstructing a string from its Lyndon arrays. Theoretical Computer Science, 710 . pp. 44-51.

[img]
PDF - Authors' Version
Embargoed until April 2019.

Link to Published Version: https://doi.org/10.1016/j.tcs.2017.04.008
*Subscription may be required

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=λ.

Publication Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2017 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/37066
Item Control Page Item Control Page