Home
Scholarly Works
V-Words, Lyndon Words and Galois Words
Preprint

V-Words, Lyndon Words and Galois Words

Abstract

We say that a family $\mathcal{W}$ of strings over $\Sigma^+$ forms a Unique Maximal Factorization Family (UMFF) if and only if every $w \in \mathcal{W}$ has a unique maximal factorization. Further, an UMFF $\mathcal{W}$ is called a circ-UMFF whenever it contains exactly one rotation of every primitive string $x \in \Sigma^+$. $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 combinatorial research on $V$-order by investigating connections to Lyndon words. Then we extend these concepts to any total order. Applications of this research arise in efficient text indexing, compression, and search problems.

Authors

Daykin JW; Mhaskar N; Smyth WF

Publication date

September 4, 2024

DOI

10.48550/arxiv.2409.02757

Preprint server

arXiv
View published work (Non-McMaster Users)

Contact the Experts team