Combinatorics of unique maximal factorization families (UMFFs)
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 (195...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
IOS Press
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/19951 |
| _version_ | 1848750173963943936 |
|---|---|
| author | Daykin, D. Daykin, J. Smyth, Bill |
| author_facet | Daykin, D. Daykin, J. Smyth, Bill |
| author_sort | Daykin, D. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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 PRAM parallel algorithm was 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. |
| first_indexed | 2025-11-14T07:32:38Z |
| format | Journal Article |
| id | curtin-20.500.11937-19951 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:32:38Z |
| publishDate | 2009 |
| publisher | IOS Press |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-199512017-01-30T12:16:41Z Combinatorics of unique maximal factorization families (UMFFs) Daykin, D. Daykin, J. Smyth, Bill UMFF dictionary factor concatenate total order circ-UMFF Lyndon maximal string word alphabet lexicographic order 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 PRAM parallel algorithm was 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. 2009 Journal Article http://hdl.handle.net/20.500.11937/19951 IOS Press fulltext |
| spellingShingle | UMFF dictionary factor concatenate total order circ-UMFF Lyndon maximal string word alphabet lexicographic order Daykin, D. Daykin, J. Smyth, Bill Combinatorics of unique maximal factorization families (UMFFs) |
| title | Combinatorics of unique maximal factorization families (UMFFs) |
| title_full | Combinatorics of unique maximal factorization families (UMFFs) |
| title_fullStr | Combinatorics of unique maximal factorization families (UMFFs) |
| title_full_unstemmed | Combinatorics of unique maximal factorization families (UMFFs) |
| title_short | Combinatorics of unique maximal factorization families (UMFFs) |
| title_sort | combinatorics of unique maximal factorization families (umffs) |
| topic | UMFF dictionary factor concatenate total order circ-UMFF Lyndon maximal string word alphabet lexicographic order |
| url | http://hdl.handle.net/20.500.11937/19951 |