Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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]
Preview
PDF - Authors' Version
Download (500kB) | Preview
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=λ.

Item 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

Downloads

Downloads per month over past year