Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.02757 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916381752033280 |
|---|---|
| author | Daykin, Jacqueline W. Mhaskar, Neerja Smyth, W. F. |
| author_facet | Daykin, Jacqueline W. Mhaskar, Neerja Smyth, W. F. |
| contents | We say that a family $\mathcal{W}$ of strings over $Σ^+$ 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 Σ^+$. $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_02757 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | V-Words, Lyndon Words and Galois Words Daykin, Jacqueline W. Mhaskar, Neerja Smyth, W. F. Data Structures and Algorithms We say that a family $\mathcal{W}$ of strings over $Σ^+$ 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 Σ^+$. $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. |
| title | V-Words, Lyndon Words and Galois Words |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.02757 |