Affiliations: Department of Mathematics University of Reading,
UK | Department of Computer Science Royal Holloway &
King's College, University of London, UK. E-mail: [email protected],
[email protected] | Algorithms Research Group, Department of Computing
& Software, McMaster University, Hamilton ON L8S 4K1, Canada and Digital
Ecosystems and Business Intelligence Institute Curtin University, GPO Box
U1987, Perth WA 6845, Australia. E-mail: [email protected]
Abstract: Suppose a set W of strings contains exactly one rotation (cyclic
shift) of every primitive string on some alphabet Σ. Then W is a circ-UMFF if
and only if every word in Σ^+ has a unique maximal factorization over W. The
classic circ-UMFF is the set of Lyndon words based on lexicographic ordering
(1958). Duval (1983) designed a linear sequential Lyndon factorization
algorithm; a corresponding PRAMparallel algorithmwas described by J. Daykin,
Iliopoulos and Smyth (1994). Daykin and Daykin defined new circ-UMFFs based on
various methods for totally ordering sets of strings (2003), and further
described the structure of all circ-UMFFs (2008). Here we prove new
combinatorial results for circ-UMFFs, and in particular for the case of Lyndon
words. We introduce Acrobat and Flight Deck circ-UMFFs, and describe some of
our results in terms of dictionaries. Applications of circ-UMFFs pertain to
structured methods for concatenating and factoring strings over ordered
alphabets, and those of Lyndon words are wide ranging and multidisciplinary.
Keywords: alphabet, circ-UMFF, concatenate, dictionary, factor, lexicographic order, Lyndon, maximal, string, total order, UMFF, word
