Combinatorics of unique maximal factorization families (UMFFs)

D.E. Daykin; J.W. Daykin; W.F. Smyth

doi:10.3233/FI-2009-202

Back

Combinatorics of unique maximal factorization families (UMFFs)

Journal article

Open access

Peer reviewed

Combinatorics of unique maximal factorization families (UMFFs)

D.E. Daykin, J.W. Daykin and W.F. Smyth

Fundamenta Informaticae, Vol.97(3), pp.295-309

2009

DOI: https://doi.org/10.3233/FI-2009-202

Files and links (2)

pdf

UMFFs.pdf200.39 kBDownload View

Open Access

url

Link to Published Version *Subscription may be requiredView

Abstract

alphabet

circ-UMFF

concatenate

dictionary

factor

lexicographic order

Lyndon

maximal

string

total order

UMFF

word

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.

Details

Title: Combinatorics of unique maximal factorization families (UMFFs)
Authors/Creators: D.E. Daykin (Author/Creator)
J.W. Daykin (Author/Creator)
W.F. Smyth (Author/Creator)
Publication Details: Fundamenta Informaticae, Vol.97(3), pp.295-309
Publisher: IOS Press
Number of pages: 15
Identifiers: 991005544913807891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Journal article

Metrics

155 File views/ downloads

81 Record Views

10 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.1103 Efficient Algorithms
Web Of Science research areas: Computer Science, Software Engineering; Mathematics, Applied
ESI research areas: Computer Science