V-Words, Lyndon Words and Substring circ-UMFFs

Jacqueline W. Daykin, Neerja Mhaskar*, W. F. Smyth

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)


We say that a family W of strings over Σ+ forms a Unique Maximal Factorization Family if and only if for every w∈ W, w has a unique maximal factorization. Then an UMFF W is a circ-UMFF whenever it contains exactly one rotation of every primitive string x∈ Σ+. V-order is a non-lexicographical total ordering on strings that determines a circ-UMFF. In this paper we propose a generalization of circ-UMFF called the substring circ-UMFF and extend the combinatorial research on V-order by investigating connections to Lyndon words. Then we extend concepts to considering any total order. Applications of this research arise in efficient text indexing, compression, and search tasks.

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 16th International Conference, COCOA 2023, Proceedings
EditorsWeili Wu, Jianxiong Guo
PublisherSpringer Nature
Number of pages14
ISBN (Print)9783031496103
Publication statusPublished - 2024
Event16th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2023 - Hawai, United States of America
Duration: 15 Dec 202317 Dec 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14461 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2023
Country/TerritoryUnited States of America
Period15 Dec 202317 Dec 2023


  • circ-UMFF
  • Combinatorics
  • Factorization
  • Lyndon word
  • Substring circ-UMFF
  • Total order
  • UMFF
  • V-order
  • V-word


Dive into the research topics of 'V-Words, Lyndon Words and Substring circ-UMFFs'. Together they form a unique fingerprint.

Cite this