Home
Scholarly Works
V-Words, Lyndon Words and Substring circ-UMFFs
Conference

V-Words, Lyndon Words and Substring circ-UMFFs

Abstract

We say that a family W$$\mathcal {W}$$ of strings over Σ+$$\varSigma ^+$$ forms a Unique Maximal Factorization Family if and only if for every w∈W$${\boldsymbol{w}} \in \mathcal {W}$$, w$${\boldsymbol{w}}$$ has a unique maximal factorization. Then an UMFF W$$\mathcal {W}$$ is a circ-UMFF whenever it contains exactly one rotation of every primitive string x∈Σ+$${\boldsymbol{x}} \in \varSigma ^+$$. 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.

Authors

Daykin JW; Mhaskar N; Smyth WF

Series

Lecture Notes in Computer Science

Volume

14461

Pagination

pp. 471-484

Publisher

Springer Nature

Publication Date

January 1, 2024

DOI

10.1007/978-3-031-49611-0_34

Conference proceedings

Lecture Notes in Computer Science

ISSN

0302-9743

Labels

View published work (Non-McMaster Users)

Contact the Experts team