Properties and Construction of Unique Maximal Factorization Families for Strings

David E. Daykin, Jacqueline W. Daykin

Research output: Contribution to journalArticlepeer-review

13 Citations (SciVal)

Abstract

We say a family of strings over an alphabet is an UMFF if every string has a unique maximal factorization over . Foundational work by Chen, Fox and Lyndon established properties of the Lyndon circ-UMFF, which is based on lexicographic ordering. Commencing with the circ-UMFF related to V-order, we then proved analogous factorization families for a further 32 Block-like binary orders. Here we distinguish between UMFFs and circ-UMFFs, and then study the structural properties of circ-UMFFs. These properties give rise to the complete construction of any circ-UMFF. We prove that any circ-UMFF is a totally ordered set and a factorization over it must be monotonic. We define atom words and initiate a study of u, v-atoms. Applications of circ-UMFFs arise in string algorithmics.
Original languageEnglish
Pages (from-to)1073-1084
Number of pages12
JournalInternational Journal of Foundations of Computer Science
Volume19
Issue number4
DOIs
Publication statusPublished - 01 Aug 2008
Externally publishedYes

Keywords

  • alphabet
  • atom
  • border
  • circ-UMFF
  • factorization
  • lexicographic
  • Lyndon circ-UMFF
  • maximal
  • non-periodic
  • properties
  • UMFF (unique maximal factorization family)
  • string
  • word

Fingerprint

Dive into the research topics of 'Properties and Construction of Unique Maximal Factorization Families for Strings'. Together they form a unique fingerprint.

Cite this