Combinatorics of Unique Maximal Factorization Families (UMFFs)

David E. Daykin, Jacqueline W. Daykin, William F. Smyth

Research output: Contribution to journalArticlepeer-review

13 Citations (SciVal)

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.
Original languageEnglish
Pages (from-to)295-309
Number of pages15
JournalFundamenta Informaticae
Volume97
Issue number3
DOIs
Publication statusPublished - 31 Dec 2009
Externally publishedYes

Keywords

  • alphabet
  • circ-UMFF
  • concatenate
  • dictionary
  • factor
  • lexicographic order
  • Lyndon
  • maximal
  • string
  • total
  • order
  • UMFF
  • word

Fingerprint

Dive into the research topics of 'Combinatorics of Unique Maximal Factorization Families (UMFFs)'. Together they form a unique fingerprint.

Cite this