Show simple item record

dc.contributor.authorDaykin, D.
dc.contributor.authorDaykin, J.
dc.contributor.authorSmyth, Bill
dc.date.accessioned2017-01-30T12:16:40Z
dc.date.available2017-01-30T12:16:40Z
dc.date.created2010-03-31T20:02:38Z
dc.date.issued2009
dc.identifier.citationDaykin, David and Daykin, Jacqueline and Smyth, W. F. 2009. Combinatorics of Unique Maximal Factorization Families (UMFFs). Fundamenta Informaticae. 97 (3): pp. 295-309.
dc.identifier.urihttp://hdl.handle.net/20.500.11937/19951
dc.description.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 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.

dc.publisherIOS Press
dc.subjectUMFF
dc.subjectdictionary
dc.subjectfactor
dc.subjectconcatenate
dc.subjecttotal order
dc.subjectcirc-UMFF
dc.subjectLyndon
dc.subjectmaximal
dc.subjectstring
dc.subjectword
dc.subjectalphabet
dc.subjectlexicographic order
dc.titleCombinatorics of unique maximal factorization families (UMFFs)
dc.typeJournal Article
dcterms.source.volume97
dcterms.source.number3
dcterms.source.startPage295
dcterms.source.endPage309
dcterms.source.issn01692968
dcterms.source.titleFundamenta Informaticae
curtin.departmentDigital Ecosystems and Business Intelligence Institute (DEBII)
curtin.accessStatusOpen access
curtin.facultyCurtin Business School
curtin.facultyThe Digital Ecosystems and Business Intelligence Institute (DEBII)


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record