Combinatorics of unique maximal factorization families (UMFFs)
Daykin, D.E., Daykin, J.W. and Smyth, W.F. (2009) Combinatorics of unique maximal factorization families (UMFFs). Fundamenta Informaticae, 97 (3). pp. 295-309.
*Subscription may be required
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.
Item Type: | Journal Article |
---|---|
Publisher: | IOS Press |
URI: | http://researchrepository.murdoch.edu.au/id/eprint/27950 |
![]() |
Item Control Page |
Downloads
Downloads per month over past year