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.

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.

Publication Type:	Journal Article
Publisher:	IOS Press
URI:	http://researchrepository.murdoch.edu.au/id/eprint/27950

Item Control Page

Downloads