V-Words, Lyndon Words and Galois Words
Jacqueline W. Daykin Neerja Mhaskar W. F. Smyth

 
Daykin et al.

 

Department of Computer Science, Aberystwyth University, Wales

jwd6@aber.ac.uk Department of Computer Science, Stellenbosch University, South Africa Univ Rouen Normandie, INSA Rouen Normandie, Université Le Havre Normandie, Normandie Univ, LITIS UR 4108, F-76000 Rouen, France
Department of Computing and Software, McMaster University, Canada
{pophlin,smyth}@mcmaster.ca

V-Words, Lyndon Words and Galois Words
 
 A preliminary version of this paper was presented at COCOA 2023. The main new contributions in this extended version are 
 
 Section <ref> and 
 
 Section <ref>.
    Jacqueline W. Daykin1,2,3 Neerja Mhaskar4Corresponding author. W. F. Smyth4
    September 9, 2024
===========================================================================================================================================================================================================



§ ABSTRACT 



We say that a family 𝒲 of strings over Σ^+ forms a Unique Maximal Factorization Family (UMFF) if and only if every w∈𝒲 has a unique maximal factorization. Further, an UMFF 𝒲 is called 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 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.



 



§ INTRODUCTION


V-order (Definition <ref>) is a non-lexicographic global order on strings that was introduced more than a quarter-century ago <cit.>. Similar to conventional lexicographical order (lexorder), V-order string comparison can be performed using a simple linear time, constant space algorithm <cit.>, further improved in <cit.>. Much theoretical research has been done on this ordering <cit.>, including efficient construction of the so-called V-BWT or V-transform <cit.>, a variant of the lexicographic Burrows-Wheeler transform (BWT). 

In this paper, we further extend combinatorial research on V-order and circ-UMFFs. We first show that there are infinitely more V-words (Definition <ref>) than Lyndon words (Definition <ref>). Then we study instances of circ-UMFFs having similar properties to V-words and/or Lyndon words. Finally, we propose a generalization of the circ-UMFF (Definition <ref>) called the substring circ-UMFF (Definition <ref>) and show that for a generalized order 𝒯, with order relation ≪, classes of border-free words exist that form 
circ-UMFFs and substring circ-UMFFs, respectively.


A useful tool in this work is a generalization of lexorder, which is based on letter comparisons, to lex-extension order, based on substring comparisons, first introduced in <cit.>. This in turn allows generalizing Lyndon words to Hybrid Lyndon words <cit.>, which we apply here.

Using the framework of UMFFs, we explore new properties of Galois words. These words are defined analogously to Lyndon words except that, rather than lexorder, alternating lexicographic order (alternating lexorder) is applied. Starting with the relation <, the alternating variant processes letter comparisons from left to right alternating between the relations < and >. While Lyndon words are necessarily border-free, the Galois variant defines both border-free and bordered words. Galois words are studied combinatorially in <cit.> and subsequently from an algorithmic perspective including practical applications in <cit.>.

All words in a circ-UMFF are border-free; thus in the general case Galois words do not form a circ-UMFF; indeed, examples show non-unique factorizations of strings into Galois words. Nevertheless, we show that the subset of border-free Galois words forms an UMFF.  Further, we characterize the structure of binary border-free Galois words in terms of a Hybrid Lyndon factorization.   We derive a Galois equivalent of the fundamental Lyndon result that the ordered concatenation of Lyndon words forms a Lyndon word — the Galois version requires the concatenated word to be primitive.


In <cit.> it is established that any binary border-free UMFF can be enlarged to a binary circ-UMFF. In view of this result, we propose here a constructive method in the finite case for generating a binary circ-UMFF from a border-free binary UMFF. We illustrate the algorithm by constructing an example of a circ-UMFF which consists of strings based on more than one method of string ordering — a discovery we believe worthy of further investigation.








§ PRELIMINARIES




A string (or word) is an array of elements drawn from a finite totally ordered set Σ of cardinality σ = |Σ|, called the alphabet. The elements of Σ are referred to as characters (letters).  We refer to strings using mathbold: x, w instead of x,w.  The length of a string w[1..n] is |w|=n. The empty string
of length zero is denoted by ε. The set of all nonempty strings over the alphabet Σ is denoted by Σ^+, with Σ^* = Σ^+ ∪ε. 
If x = uwv for (possibly empty) strings u,w,v∈Σ^∗,
then u is a prefix, w a substring or factor,
and v a suffix of x. A substring u of w is said to be proper if |u| < |w|. 
A string w has a border u if u is both a proper prefix and a proper suffix of w. 
If w has only the empty border ε, then it is said to be border-free. 

For x = x[1..n]
and an integer sequence 0 < i_1 < i_2 < ⋯ < i_k ≤ n,
the string y = x[i_1]x[i_2] ⋯x[i_k] is said to be a
subsequence of x, proper if |y| < n.
If x = u^k (a concatenation of k copies of u)
for some nonempty string u and some integer k > 1,
then x is said to be a repetition;
otherwise, x is primitive. We say x has period p if and only if for every i ∈ 1..n-p,
x[i] = x[i+p]; the shortest period of x is called the period.
A string y=R_i(x) is the i^ conjugate (or rotation) of x=x[1..n] if 
y = x[i+1..n]x[1..i] for some 0 ≤ i < n (so that R_0(x) =x).
The conjugacy class of x is the set R_i(x), 0 ≤ i < n, of all conjugates.

In our examples, we often suppose that Σ = {a,b,c,…,z}, the Roman alphabet in its natural order, or Σ = {1,2,3,…,k}, the bounded natural numbers. The ordering of Σ imposes lexicographic order (lexorder) on Σ^+.
However, in the case that x = u^k, a repetition, lexorder does not provide a unique ordering of the rotations of x: rotations R_k, R_2k,…, R_|x| are all equal. 
To avoid this, we can append to each x a unique least symbol $, so that all the rotations of x$ are distinct and thus ordered, while the ordering of any pair x$, y$ is unaffected.
The rotations of x, sorted in ascending lexicographic order, form the Burrows-Wheeler matrix, so that, for
x = abab$, we get the unique ordering

    [ $ a b a b; a b $ a b; a b a b $; b $ a b a; b a b $ a ]

of which the last column, bb$aa, is the Burrows-Wheeler transform (BWT) of x, from which the original string can be recovered in linear time <cit.>. Observe the transformation of the input in the example, abab$ to b^2 $ a^2, and this data clustering property is often exhibited with the BWT, and hence its use as a preprocessor or booster for the performance of memoryless compressors. While the BWT was originally introduced in the context of lossless text compression, subsequent applications span image compression, shape analysis in computer vision, efficient self-indexed compressed data structures, and its pattern matching properties are invaluable in bioinformatics with its highly repetitive data for tasks such as sequence alignment <cit.>.


We now define another fundamental concept in this paper, the Lyndon word, which has deep connections with the theory of free Lie algebras and combinatorics on words:



A Lyndon word <cit.> is a primitive string
that is minimum in lexorder < over its conjugacy class.

The following Lyndon factorization (LF) theorem is fundamental in stringology
and underpins the wide-ranging applications of Lyndon words,
which include specialized string sorting tasks, digital geometry, musicology, the Burrows-Wheeler transform and data compression techniques:


<cit.> Any nonempty string x can be written uniquely as a product
_x = x = u_1 u_2 ⋯u_k of k ≥ 1 Lyndon words,
with (u_1 ≥u_2 ≥⋯≥u_k).


For further stringological definitions and theory, see <cit.>.



§ V-ORDER


In this section we start by defining V-order and describing some of its important properties used later in the paper.

Let x=x_1x_2⋯ x_n be a
string over Σ. Define h ∈{1,…,n} by h = 1 if x_1 ≤ x_2 ≤⋯≤ x_n; otherwise, by the unique value such that x_h-1>x_h ≤ x_h+1≤ x_h+2≤⋯≤ x_n. Let x^*=x_1x_2⋯
x_h-1x_h+1⋯ x_n, where
the star * indicates deletion of x_h. Write x^s* =
(...(x^*)^*...)^* with s ≥ 0 stars.
Let g = max{x_1,x_2, … ,x_n},
and let k be the number of occurrences of
g in x.
Then the sequence x,x^*,x^2*, ...
ends g^k,...,g^1,g^0=ε.
From all strings x over Σ we form the star tree (see Example <ref>), where each string
x labels a vertex and there is a directed edge upward from x
to x^*, with the empty string ε as the root.



We define V-order ≺ for distinct strings x, y. 
First x≺y if in the star tree x is in the path
y,y^*,y^2*, … ,ε. If x,y are not in a path, there exist
smallest s,t such that x^(s+1)*=y^(t+1)*.  Let s=x^s* and
t=y^t*; then s≠t but |s| = |t| = m say.
Let j ∈ [1..m] be the greatest integer such that s[j] t[j].
If s[j]<t[j] in Σ then x≺y;
otherwise, y≺x.
Clearly ≺ is a total
order on all strings in Σ^∗.




See the star tree path and star tree examples in 
Figures <ref> and <ref>, respectively.



[Star tree path] Figure <ref> illustrates the star tree for the case x≺y if in the star tree x is in the path
y,y^*,y^2*, … ,ε.  Consider the
V-order comparison of the strings x = 929 and y = 922911. The subscript h indicates the V letter to be deleted (defined above as x_h-1>x_h ≤ x_h+1≤ x_h+2≤⋯≤ x_n). Since 929 is in the path of star deletions of 922911, therefore 929 ≺ 922911.






[Star tree] Figure <ref> illustrates the star tree for the non-path case using the V-order comparison of the words x = unique and y = equitant. As in the previous example, the subscript h indicates the V letter to be deleted (defined above as x_h-1>x_h ≤ x_h+1≤ x_h+2≤⋯≤ x_n). The circled letters are those compared in alphabetic order (defined above as s[j] t[j]). 

 

We now describe a canonical form of a string known as V-form which partitions a string according to its largest letter.


The V-form of any given string x is 

    V_k(x) = x = x_0gx_1g⋯x_k-1gx_k,


where g is the largest letter in x — thus we suppose that g occurs exactly k times.
Note that any x_i may be the empty string ε.  We write ℒ_x=g,
𝒞_x=k.






<cit.> Suppose we are given distinct strings
x and y with corresponding V-forms

    x    =    x_0 _xx_1 _xx_2 ⋯x_j-1_xx_j, 
    y    =    y_0 _yy_1 _yy_2 ⋯y_k-1_yy_k,

where j = 𝒞_x, k = 𝒞_y.
Let h ∈ 0 .. max(j,k) be the least integer such that x_h
≠y_h. Then  x≺y if and only if one of the
following conditions holds:


  (C1) _x < _y

  (C2) _x = _y and
𝒞_x < 𝒞_y 

  (C3) _x = _y,
𝒞_x = 𝒞_y
and x_h ≺y_h. 
 



<cit.> For given strings x and y,
if y is a proper subsequence of x,
then y≺x. 


For instance, given x=7547223,
Lemma <ref> states that 772 ≺ 7547223. 
Furthermore, another consequence of Lemma <ref>  
is that shorter suffixes are suffixes of longer suffixes; that is, they occur from the shortest to the longest in increasing order. So for x,
the V-order of the suffixes is 
just 3 ≺ 23 ≺ 223 ≺ 7223 ≺ 47223 ≺ 547223 ≺ 7547223.
Thus in V-order suffix sorting is trivial,
in contrast to lexorder, where over the years numerous non-trivial (though linear) algorithms have been proposed <cit.>.

Furthermore, string comparison is fast in V-order: 



<cit.> V-order comparison of given strings x and y requires linear time and constant space.


We now introduce the V-order equivalent of the lexorder Lyndon word:

A string x over an ordered alphabet Σ is a V-word if it is the unique minimum in V-order ≺
over the conjugacy class of
x.

Thus, like a Lyndon word, a V-word is necessarily primitive. 




[≺]
We can apply Definition <ref>, equivalently the methodology of Lemma <ref>, to conclude that 

    6263 ≺ 6362 ≺ 2636 ≺ 3626,

so that 6263 is a V-word,
while on the other hand 2636 is a Lyndon word.
Similarly,
62626263 and 929493 are V-words,
while conjugates 26262636 and 294939 are Lyndon words.







We now define another important ordering:



Suppose u and v are V-words on an ordered alphabet Σ.
If uv is also a V-word, then we write u <_𝒱v;
if not, then 
u≥_𝒱v.

Thus, corresponding to the Lyndon factorization into Lyndon words
using ≥ (Theorem <ref>),
we arrive at a V-order factorization expressed
in terms of V-word order ≥_𝒱:



<cit.>
[V-order Factorization]
Using only linear time and space (see Algorithm VF in <cit.>[
VF is an on-line algorithm as it outputs the V-word factors in order from left to right without any backtracking. However, this fact was not explicitly stated in the reference.]),
a string x can be factored uniquely, using V-word order, into V-words
x = x_1x_2⋯x_m,
where x_1≥_𝒱x_2≥_𝒱⋯≥_𝒱x_m.






For x = 33132421, the Lyndon decomposition (computed using lexorder) is 3 ≥ 3 ≥ 13242 ≥ 1,
while the V-order factorization identifies nonextendible V-words 33132 and 421 with
33132 ≥_𝒱 421.
(Note however that 33132 ≺ 421!
See <cit.> for more background on this phenomenon.)
Similarly, from Example <ref>,
the string

    x = uvw = (6263)(62626263)(929493)

has the unique V-order factorization u≥_𝒱v≥_𝒱w,
even though u≺v≺w.


It will also be useful to order strings x, y
based on a lexicographic approach to their 
factorizations into identified substrings; this will be applied in Section <ref> to handle string factorization based not on letters but substrings.
We call this ordering, denoted 
≺_LEX(F), lex-extension order, expressed here with respect to substring

ordering using ≺ — but note that other substring ordering methodologies could instead be applied. 




Suppose that, according to some factorization F, two strings x, y∈Σ^+ are expressed in terms of nonempty factors: 
    x = x_1x_2⋯x_m, y = y_1y_2⋯y_n.
 Then x≺_LEX(F)y if and only if one of the following holds:


  (1) x is a proper prefix of y (that is, x_i = y_i for 1 ≤ i ≤ m < n); or

  (2)
for some least i ∈ 1..min(m,n),  x_j = y_j for j = 1,2,…,i­ 1, and x_i≺y_i.








We assume throughout that, when using lex-extension order, the factorization F is given in V-form (Definition 
<ref>). That is, if the V-form of x is 
    x  =  x'_0_xx'_1_xx'_2⋯x'_k-1_xx'_k,
 
then the corresponding 
lex-extension order factors are:

    x_1 = x'_0, x_2 = _xx'_1, ⋯, 
    x_k+1 = _xx'_k.
 
Depending on the context, it could be that x'_0 = ε, in which case x_1  =  _xx'_1, x_2  =  _xx_2, and so on.



Thus, in order to V-order two strings with identical  values, 

we first compute the 
V-form factorization of each string, then treat each of the resulting factors as a single entry (a “letter”), and so determine the “lexicographic” order of the given strings by comparing the factors from left to right using ≺ (Lemma <ref> (C3) defines comparison of 

strings that are conjugates).






§ UMFF AND CIRC-UMFF THEORY


Motivated by classical Lyndon words, investigations into combinatorial aspects of the factoring and concatenation of strings led to the concepts of UMFF and circ-UMFF <cit.>,
whose properties we overview here and apply in Sections <ref>, <ref> and <ref>.


For given x = x[1..n] ∈Σ^+, if x = w_1w_2⋯ w_k, 1 ≤ k ≤ n,
then w_1w_2⋯ w_k
is said to be a factorization of x;
moreover, if every factor w_j, 1 ≤ j ≤ k, belongs to a specified
set 𝒲,
then w_1w_2⋯ w_k
is said to be a factorization
of x over 𝒲, denoted by F_𝒲(x).


A subset 𝒲⊆Σ^+ is a
factorization family (FF) of Σ if 

for every nonempty string
x on Σ there exists a factorization F_𝒲(x). If for every j = 1,2,...,k, every factor w_j is of maximum length, then the factorization F_𝒲(x) is unique and said to be maximal.


To show that not every factorization is necessarily maximal, consider the FF 
𝒲 = {a,b,c,d,ab,cd,bcd}.
Then, for x = abcd, we get three possible factorizations, (a)(b)(c)(d) and (ab)(cd),  and also (a)(bcd), depending on whether we process x in a forward or backward direction.  But therefore, in each case, not every factor can be of maximum length and so FF is not maximal.


Observe that every FF must contain every element of Σ; moreover,
any subset of Σ^+ containing every element of Σ is necessarily an FF.



Let 𝒲 be an FF on an alphabet Σ.
Then 𝒲 is a unique maximal factorization family (UMFF)
if and only if there exists a 
maximal factorization F_𝒲(x)
for every string x∈Σ^+.



The following characterization of UMFFs shows that there can be no overlapping factors in a unique maximal factorization of a string:






(The 𝐱𝐲𝐳 Lemma <cit.>)
An FF 𝒲 is an UMFF if and only if
whenever xy,yz∈𝒲 for some nonempty y,
then xyz∈𝒲.



Note that, although the Fibonacci words b,a,ab,aba,abaab,abaababa⋯ are clearly an example of an FF, nevertheless they do not by Lemma <ref> constitute an UMFF: x = abaab, y = aba, z = ab are all 

Fibonacci words,
as are xy and yz, but xyz is not. 


We next show that an FF that contains no overlapping factors — such as the string y in Lemma <ref> — necessarily forms an UMFF.



Let 𝒲 be an FF on Σ.  If for every distinct u,v∈𝒲 with |u|, |v|>1, uv is border-free,
then 𝒲 is an UMFF.


By definition of FF, 𝒲 must contain all the letters in Σ, which clearly do not overlap.  
Consider factoring some string x = x_1 x_2 … x_n, n>1, maximally over 𝒲, so that x = f_1f_2⋯f_m, where 
no factor f_i, 1 ≤ i ≤ m, can be extended either left or right. Specifically,
if f_i = x_p … x_q, 1 ≤ p ≤ q ≤ n, then x_p-j… x_q+k∉𝒲 for any positive j < p, k < n+1-q. 


The non-extendability of all factors ensures maximality and thus uniqueness of the factorization f_1f_2⋯f_m, and so we conclude that 𝒲 forms an UMFF.  





For example, with Σ = {0,1}, Lemma <ref> tells us that 𝒲={0,1,010} must be an UMFF.  On the other hand, the example FF
𝒲 = {0,1,010,01010,0101010, …} from <cit.>, with an infinity of bordered uv, is also an UMFF, showing that the converse of Lemma <ref> certainly does not hold.





































Indeed, observe from the following example that neither primitiveness nor the border-free property guarantees that a set of words forms an UMFF:



Suppose that 𝒲 is an UMFF over Σ = {a,b,c} such that
 {a,b,c, ab, abc, cab }⊆𝒲. Then consider applying the xyz Lemma <ref> twice to words in 𝒲 as follows:


  (i) For x = z = ab and y = c,  we find the bordered word xyz = abcab ∈𝒲.
    
  (ii) For x = abc, z = c and y = ab, we find the repetition xyz =(abc)^2 is also in 𝒲.
  











Interestingly, known UMFFs in the literature, such as Lyndon words and V-words, are specified as being necessarily primitive and they also satisfy the border-free property.


An important class of UMFFs can now be specified:


An UMFF 𝒲 over Σ^+ is a circ-UMFF if and only if
it contains exactly one rotation of every primitive string x∈Σ^+.



Observe that the definition of UMFF does not require that Σ be ordered.  Nor does the circ-UMFF 𝒲, but it does require that the ordering of any two distinct strings in 𝒲 depends only on their concatenation (that may or may not occur).




Thus a circ-UMFF 𝒲 may be said to specifiy a “concatenation order”:



(<cit.>)
If a circ-UMFF 𝒲 contains strings  u,v and uv, we write u <_𝒲v (called 𝒲-order).


Observe that V-word order (Definition <ref>), also defined in terms of concatenation, is formally equivalent to
𝒲-order.

Structural properties of circ-UMFFs are summarized as follows:

 
(<cit.>) Let 𝒲 be a circ-UMFF.
 

(1) If u∈𝒲 then u is
border-free.

(2) If u,v∈𝒲 and u≠v then uv is primitive.
 
(3) If u,v∈𝒲 and u≠v then uv∈𝒲 or vu∈𝒲 (but not both).

(4) If u,v, uv∈𝒲 

then u <_𝒲v, 

and <_𝒲 is a
total order on 𝒲.
 
(5) If w∈𝒲 and |w| ≥ 2 then there 

exist u,v∈𝒲 with w=uv. 


The first known circ-UMFF is believed to be the set of Lyndon words, 
whose specific 𝒲-order is lexorder; that is, the usual ordering of the strings of Σ^+ is used to obtain Lyndon words.


Formally, the Lyndon circ-UMFF applies the same lexicographic ordering as both Σ^+ and 𝒲-order:

 
(<cit.>) Let ℒ be the set of Lyndon words, and suppose u, v∈ℒ. Then uv∈ℒ if and only if u precedes v in lexorder.


Note that, from Definition <ref>, V-order factorization determines an UMFF, which, by Definitions <ref> and <ref>, is a circ-UMFF.






§ V-WORDS, LYNDON WORDS AND CIRC-UMFFS











In this section we investigate further the relationship and differences between Lyndon and V-words and introduce generalized words over any total order.


We begin with an observation made 


in <cit.>, that follows immediately from Duval's fundamental Theorem <ref> <cit.>:





Let Σ^*_lex denote the lexicographic total ordering of Σ^*. Then the lexordered set ℒ of Lyndon words is a 

suborder of Σ^*_lex.

However, observe that there is no corresponding architecture for V-words.  In V-ordered Σ^*, for x = 21, y = 31, we have x≺y by Lemma <ref> (C1), while in the class of V-words we have 
x≥_𝒱y by Definition <ref> of V-word order. For further details on the distinction between ≺ and ≥_𝒱 see Lemma 3.16 in <cit.>.

Lyndon words and V-words are generally distinct <cit.>. For instance, the integer string 1236465123111 factors into Lyndon words (12316465)(123)(1)(1)(1) and into V-words (1)(2)(3)(6465123111) — no correspondence whatsoever. Nevertheless,

when substrings are restricted to a single letter, a rather remarkable result holds, which is a newly observed special case of Theorem 4.1 in <cit.> and leads to the concept of V-Lyndons:

[V-Lyndons]


Suppose x has a V-form x  =  _xx_1 _xx_2 ⋯x_j-1_xx_j, 

where x_0 = ε and 
|x_l| = 1 for 1 ≤ l ≤ j.
Let 
x' = x_1 x_2 ⋯x_j-1x_j.  Then
x is a V-word if and only if x'  is a Lyndon word.






To see that the requirement 
|x_l|=1 is necessary,
consider x = 321312 with
_x = 3, 
|x_1| = |x_2|= 2.

Certainly 
x' = x_1x_2 = 2112 is 
not a Lyndon word, but since x≺ 312321,

x is a V-word.  Thus Lemma <ref> does not generalize to V-form substrings with 

|x_l| > 1.

Nonetheless, there does exist a kind of reciprocity between infinite classes of Lyndon words and V-words:


 For any Lyndon word x[1 .. n], n ≥ 2, on ordered alphabet Σ:




  (1) If 
_x is the largest letter in x, then (')^kx is a V-word for ' > _x and every integer k > 0.

  (2) If  
ℓ_𝓍 is the smallest 
letter in x,

then (ℓ_x)^kx is a Lyndon word for every integer k > 0.















Building on Lemma <ref> and Observation <ref>(1), we can show that there are infinitely more V-words 
than there are Lyndon words: 


Suppose that ℓ[1 .. n] is a Lyndon word over an ordered alphabet Σ and further that there exists _ℓ∈Σ such that _ℓ > ℓ[i] for every i ∈ 1 .. n. 
Then we can construct infinitely many V-words from ℓ over Σ.




For the first V-word v_1, applying  
Lemma <ref>,
we rewrite ℓ as v_1 [1 .. 2n] where for i ∈ 1 .. 2n, if i is odd, v_1[i] = _ℓ, while if i is even, v_1[i] = ℓ[i/2]; that is, v_1 = _ℓℓ[1] _ℓℓ[2] .. _ℓℓ[n].

For V-words v_h, h > 1, rewrite ℓ as v_h = _ℓℓ[1]^h _ℓℓ[2]^h .. _ℓℓ[n]^h. Lemma <ref> (C1) shows that if a ≺ b for letters a,b (that is, a<b in Σ), then a^h ≺ b^h and hence the Lyndon property (Lemma <ref>) of ℓ is preserved for v_h using Definition <ref> for lex-extension order of strings.


It might then be natural to suppose that V-words exhibit the same structural properties as Lyndon words and support equivalent string operations. For instance, a defining property of Lyndon words is that they are strictly less in lexorder than any of their proper suffixes; that is, for a Lyndon word ℓ = p_ℓs_ℓ, with p_ℓ,s_ℓ≠ϵ, we have 

    ℓ < s_ℓ < s_ℓp_ℓ.

This central Lyndon property relates to two important operations on strings: ordering and concatenation.  For Lyndon words, these operations

are consistent with respect to lexorder: that is,  for every proper suffix s_ℓ of ℓ, by virtue of the ordering ℓ < s_ℓ,

we can construct a Lyndon word  ℓs_ℓ^h by concatenation for every h ≥ 1.  


In contrast, for V-order, these operations are not necessarily consistent.  First, by Lemma <ref>, a proper suffix u of a string x

is less than x in V-order; thus, 
for example, given the V-word
v = 43214123, even though substrings 23 ≺v and 4123 ≺v, on the other hand, by definition of a V-word, v≺ 41234321. 
So for a V-word v = p_vs_v, with p_v,s_v≠ϵ, 
we have 
    s_v≺v≺s_vp_v.


Nevertheless, like a Lyndon word, a V-word can be concatenated with any of its proper suffixes (although they are less in V-order) to form a larger V-word (Lemma 3.21 in <cit.>). 


Hence we are interested in those combinatorial properties related to operations like concatenation and indexing in conjugacy classes which hold both for Lyndon words and V-words. Examples include border-freeness, existence of uv and vu in the conjugacy class where u and v are Lyndon words, and the FM-index Last First mapping property <cit.>. 


More generally, it is intriguing to explore similarities and differences between instances of circ-UMFFs, as discussed below. 















































We begin by introducing a general form of order, 𝒯:


(𝒯-order)
Let 𝒯 be any total ordering of Σ^* with order relation ≪ so that given distinct strings x, y they can be ordered deterministically with the relation ≪: either x≪y or y≪x. 

So for Lyndon words (V-words) the ordering 𝒯 is lexorder (V-order) and the corresponding order relation ≪ is < (≺).  Using the general order 𝒯, we can extend Definitions <ref>/<ref> from Lyndon words/V-words to 𝒯_≪-words:



(𝒯_≪-word)
A string x over an ordered alphabet Σ is said to be a 𝒯_≪-word if it is the unique minimum in 𝒯-order ≪
in the conjugacy class of x.



Similarly, Definition <ref> (lex-extension order) can be generalized by replacing the order ≺ by 𝒯-order ≪:
















 

For a factorization F, let x, y∈Σ^+ be two strings expressed in terms of nonempty factors: 
    x = x_1x_2⋯x_m, y = y_1y_2⋯y_n.
 Then x≪_LEX(F)y if and only if:


  (1) x is a proper prefix of y or

  (2)
for some least i ∈ 1..min(m,n),  x_j = y_j for j = 1,2,…,i­ 1, and x_i≪y_i.










Applications of circ-UMFFs in the literature arise in linear-time variants of the Burrows-Wheeler transform: the V-order based transform V-BWT <cit.>; the binary Rouen transform B-BWT derived from binary block order which generated twin transforms <cit.>; the degenerate transform D-BWT for indeterminate strings implemented with lex-extension order <cit.> which supports backward search <cit.>. These instances stimulate the quest for new circ-UMFFs and we pave the way for this by next introducing a generalization of circ-UMFFs.



§ SUBSTRING CIRC-UMFF: GENERALIZATION OF CIRC-UMFF


Definitions <ref> and <ref> encourage considering conjugacy classes for substrings 

rather than individual letters;

that is, each 

conjugate is defined by a rotation with prefix _xx_i, 

as follows:

















Suppose that a string x = x[1..n]
over an ordered alphabet Σ, with maximal letter _x,
is expressed

in V-form as
_xx_1 _xx_2 ⋯x_j-1_xx_j,
with x_0 = ε. 
Then for every 
1 ≤ t ≤ j,

    y = ℛ_t(x) = _xx_t+1_xx_t+2⋯x_j-1_xx_j(_xx_1 ⋯_xx_t)
 is the t^th substring conjugate (or substring rotation) of x 
(so ℛ_j(x) = x).





























Since Lemma <ref> holds for unrestricted strings xy and yz (given y is nonempty) then it certainly holds for specified types of substrings, so in the context of substring conjugates we get:



Lemma <ref> holds for substrings expressed in V-form.    




Thus a natural generalization of circ-UMFF is the substring circ-UMFF, where a conjugate is selected from the conjugacy class of substrings of a string rather than the usual rotation of letters. 



An UMFF 𝒲 over Σ^+ is a substring circ-UMFF if and only if
it contains exactly one substring rotation of every primitive string x∈Σ^+ expressed in V-form.





A string x  =  

_xx_1 _xx_2 ⋯x_j-1_xx_j in V-form 

over an ordered alphabet Σ, with maximal letter _x, is said to be a 
𝒯_lex-word


if it is the unique minimum in 𝒯_lex-order 

in its conjugacy class. 








To clarify, consider the primitive integer string 431412 where, with reference to V-form, = 4, and letting ≪ denote co-lexorder (lexorder of reversed strings), then the conjugate 412431 is least in co-lexorder for the letter-based conjugates, while the substring conjugate 431412 is least in Lex-Ext co-lexorder in the comparison of 431412 and 412431. That is, 412431 is a 𝒯_≪-word, while 431412 is a 𝒯_lex-word.    



We have then the following important result:


Suppose ≪ is a 𝒯-order over Σ^*.
(i) The class of border-free

𝒯_≪-words forms a circ-UMFF 𝒯

over the conjugacy class of letters.
(ii) The class of border-free

𝒯_lex-words

forms a substring circ-UMFF 

over the conjugacy class of substrings.


By Definition <ref>, ≪ is a total order.
Here we make use of two fundamental results: the xyz lemma (Lemma <ref> from <cit.>) and the circ-UMFF theorem (Theorem <ref> from <cit.>).


Part (i). Let 𝒯 denote the set of border-free 𝒯_≪-words (Definition <ref>) over Σ.



First, by the definition of 𝒯, every letter in Σ is in 𝒯, so we may confine our consideration to strings of non-unit length.



Suppose then that xy and yz, with x,y,z nonempty, are both border-free 𝒯_≪-words in 𝒯, therefore primitive.


Consider the string xyz and suppose that it is a repetition u^k, k>1. 

But if u is a proper prefix of xy then xy is bordered, whereas if xy is a prefix of u then yz is bordered.  Thus we conclude that xyz is also primitive, and so 

must have at least one border-free conjugate — 
for instance, the conjugate

that is a Lyndon word is border-free and therefore might be 
in 𝒯. So we next
consider which border-free conjugate c_𝒯 of xyz is in 𝒯.

So suppose that xyz is not itself minimal in 𝒯-order in its conjugacy class.

Let x = x_1 x_2 … x_r, y = y_1 y_2 … y_s and z = z_1 z_2 … z_t, r,s,t ≥ 1.  First assume that a conjugate c=x_c+1… x_r yz x_1 … x_c, 

1 ≤ c ≤ r,
is minimal, thus border-free and in 𝒯. But then applying Lemma <ref> to c and xy implies that the bordered word x_c+1… x_r yzxy is in 𝒯, an impossibility. So assume that a conjugate c'=y_d+1… y_s zx y_1 … y_d, 

1 ≤ d ≤ s is minimal and belongs to 𝒯. Again applying Lemma <ref> to yz and c' 

implies that the bordered word 

yzxy_1 … y_d is in 𝒯, again impossible. Finally, for 
c”=z_e+1… z_t xy z_1 … z_e, e+1 ≥ 1, 
a similar argument for c” and yz implies that the bordered word z_e+1… z_t xyz is in 𝒯.   








Hence the primitive conjugate xyz must itself be border-free and so must be the one, c_𝒯, in 𝒯, 
that is least in 𝒯-order ≪ in its conjugacy class. Applying the sufficiency in Lemma <ref>, since xy, yz and xyz with nonempty y all belong to 𝒯, we can conclude that 𝒯 is 
an UMFF. 





Thus, from each conjugacy class of a primitive string, we have shown how to select a border-free word for 𝒯, therefore satisfying Definition <ref>.
Since moreover circ-UMFFs are necessarily border-free 

(Theorem <ref> Part (1)), we can conclude that 𝒯 is a circ-UMFF.


Part (ii). The proof here is similar to that of Part (i), substituting Definition <ref> of 𝒯_lex-words for
Definition <ref> of 𝒯_≪-words, and applying Observation <ref> for substrings.









Here we let 𝒯^𝓈 denote the set of border-free 𝒯_lex-words over Σ^*.


Then by the definition of 𝒯^𝓈, the substrings of unit length (“letters") are in 𝒯^𝓈, where

these strings of length one have the form ℒw_i where w_i∈Σ^* (so if w_i is the empty string we get the 

substring ℒ). Then a non-unit length string w of length ℓ will have ℓ occurrences of ℒ in the form _ww_1_ww_2⋯w_ℓ-1_ww_ℓ. 

Suppose then that xy and yz, with x,y,z nonempty, are both border-free 𝒯_lex-words in 𝒯^𝓈, therefore primitive, and as above we deduce that xyz is also primitive.
In the analysis of 𝒯^𝓈, for the existence of at least one border-free substring conjugate, 

we observe that the V-order 

circ-UMFF can be considered in the form of Definition <ref>. Then there exists a border-free 

V-word in the substring conjugacy class. As above, we suppose that xyz is not minimal in 𝒯_lex-order and proceed to 
consider which border-free conjugate c_𝒯^𝓈 of primitive xyz is in 𝒯^𝓈. Let x = _xx_1 _xx_2 ⋯x_r-1_xx_r, y = _yy_1 _yy_2 ⋯y_s-1_yy_s, z = _zz_1 _zz_2 ⋯z_t-1_zz_t, r,s,t ≥ 1. First assume that a conjugate 

c = _xx_c+1…_xx_ryz_xx_1…_xx_c, 

1 ≤ c ≤ r,
is minimal, thus border-free and in 𝒯^𝓈. But then applying
Observation <ref>

to 

c and xy implies that the bordered word _xx_c+1…_xx_ryzxy is in 𝒯^𝓈, an impossibility. 
The rest of the argument follows as in Part (i), first showing that xyz is the conjugate c_𝒯^𝓈 in 𝒯^𝓈, and finally establishing that 𝒯^𝓈 is a substring circ-UMFF.




Observe that Theorem <ref> shows that if a circ-UMFF or a substring circ-UMFF is defined using a total order (which is not necessary), then every element of the (substring) circ-UMFF is obtained using the same total order and no other ordering technique. Observe further that the proof does not depend on any particular method of totally ordering Σ^*; however, the method must be total for border-free (hence primitive) strings in Σ^*. 




























We illustrate concepts from Theorem <ref> with the following:


Consider the border-free integer string x = 3177412. Then the (unordered) conjugacy class of x is given by

    

     
    3     1     7     7     4     1     2 
    
    	2     3     1     7     7     4     1 
    
    	1     2     3     1     7     7     4 
    
    	4     1     2     3     1     7     7 
    
    	7     4     1     2     3     1     7 
    
    	7     7     4     1     2     3     1 
    
    	1     7     7     4     1     2     3

	

	The third conjugate, 1231774, is the Lyndon word as it is least in lexorder. The sixth conjugate, 7741231, is the V-word as it is least in V-order; it is also a co-lexorder word as it is least in co-lexorder; furthermore, it is least in relex order (reverse lexorder). The fifth conjugate, 7412317, is the second largest in lexorder but is a bordered word. And the seventh conjugate, 1774123,  is least in alternating lexorder (indexing strings from 1, odd indexed letters are compared with < and even with >).











We illustrate Definition <ref> for Lex-Ext co-lexorder where we intertwine lexorder 

with ordering substrings in co-lexorder:


This example establishes the Lex-Ext co-lexorder substring circ-UMFF. Given a string x∈Σ^*  in V-form, x  =  x_0 _xx_1 _xx_2 ⋯x_j-1_xx_j, 
with x_0 = ε, 
the substring conjugates of x are compared using lex-extension where the x_i substrings will be compared in co-lexorder. 
Since both lexorder and by isomorphism co-lexorder are total orders of Σ^*, any pair of distinct strings x, y∈Σ^* can be compared deterministically in Lex-Ext co-lexorder. So given a border-free, hence primitive, string x, we can uniquely choose a conjugate from the substring conjugacy class which is minimal in Lex-Ext co-lexorder (cf. Definition <ref>).  Theorem 
<ref> Part (ii) then applies where in this case the class of border-free  
𝒯_lex-words is the set of Lex-Ext co-lexorder words. 
For example, the integer string 
9211912197194395119119111912 factors uniquely as (921191219719439511)(9119111912),


while into Lex-Ext lexorder words as (9211)(921951)(9119111912).

Clearly we can replace co-lexorder in this context with any method for totally ordering Σ^*, for instance relex order or 

alternating lexicographic order. Note that, as shown for V-order <cit.>, co-lexorder string 

concatenation and ordering are not necessarily the same — this phenomenon of circ-UMFFs is explored in <cit.>. For example, 321 is less than 54 in co-lexorder, while 54 is less than 321 in circ-UMFF order, because the concatenation 54321 is a co-lexorder word.





Naturally, we can modify the results of this section by defining other canonical forms of a string.  For instance, rather than partitioning a string according to the maximal letter  as in V-form, the partition could depend on the minimal letter, or indeed any well-defined substring pattern — such as a short palindromic motif in DNA sequences.


Implementing the FM-Index in V-order was considered in <cit.>, leading to V-order substring pattern matching using backward search — whereby computing only on the k conjugates starting with the greatest letter, essentially a substring circ-UMFF, reduced the BWT matrix to O(nk) space. Note, however, that to fully implement BWT-type pattern matching in V-order so as to handle all letters — rather than just V-letters which have only one maximal letter which occurs at the start of the substring — 

remains an open problem <cit.>.
 Hence, the substring circ-UMFF concept promises future optimization opportunities — in particular, related to indexing and pattern matching applications.





§ GALOIS WORDS




This final section applies many of the concepts 

developed in Sections <ref>–<ref> to show that although — in contrast to circ-UMFF words and in particular to classic Lyndon words — a given string does not necessarily factor uniquely and maximally into Galois words, nevertheless Galois words may still belong to a set of words which does form a circ-UMFF. 
Additionally, the continuing necessity of the border-free requirement, as in Theorem <ref>, is demonstrated. We first 
describe Galois words as

introduced in <cit.>, based on a variant of lexorder, namely alternating lexicographic order, denoted ≺_alt — in which,

informally, positions within two given strings are compared in alternating < and > order. More precisely:

 

[Alternating lexorder ≺_alt (modified from <cit.>)]
Given distinct strings x = x_1 x_2 … x_s and y = y_1 … y_t, 
1 ≤ s ≤ t:
 

(1) (x not a proper prefix of y) If i is the smallest index such that x_i ≠ y_i, 
then x≺_alty iff 
(a) i is odd and x_i < y_i or
(b) i is even and y_i < x_i. 
Otherwise, y≺_altx.


(2) (x a proper prefix of y)
x≺_alty iff |x| is even.
Otherwise, y≺_altx.



An immediate consequence of Definition <ref>(2) is the following:


    For any string  x, if |x| is even then 
    (1) ∀y∈Σ^+, x≺_altxy; in particular,
    (2) x^k ≺_altx^k+r, for k ≥ 1, r ≥ 1.

We first establish that alternating lexorder ≺_alt forms a total order over Σ^*, thus enabling the selection of a unique conjugate (such as the least) for Definition <ref> and as also required for Theorem 
<ref>. 







Alternating lexorder ≺_alt is a total order over Σ^*.

 

Consider distinct x, y, z∈Σ^+ with x = x_1x_2 … x_e, y = y_1y_2 … y_f, z = z_1z_2 … z_g. 
Assume that x≺_alty≺_altz, but that z≺_altx.

Case 1. z is a proper prefix of x.
Since 

z≺_altx, by Definition <ref>(2) |z| is even.

Subcase 1a. x is a proper prefix of y. 


Thus z must be a proper prefix of y, and since |z| is even,
again by Definition <ref>(2)
z≺_alty, a contradiction.

Subcase 1b. x is not a proper prefix of y. Then there is a smallest index i such that x_i ≠ y_i. If i > |z|, then z is a proper prefix of y and the contradiction of Subcase 1a applies to z and y. So suppose i ≤ |z| and consider a corresponding relation R, 
< or > for odd or even index i, respectively — then since z_i = x_i, so that x_i R  y_i implies z_i R  y_i, it follows that z≺_alty, a contradiction.

Case 2. z is not a proper prefix of x. 

Subcase 2a. If x is a proper prefix of y, then z≺_alty, a contradiction.
 
Subcase 2b. If x is not a proper prefix of y, then there is a smallest index j such that x_j ≠ y_j and x_j  R  y_j (where R is as above based on odd/even index).  Let i be the smallest index such that z_i ≠ x_i.  If j<i, then z_j = x_j and x_j  R  y_j,

so that z≺_alty, a contradiction. If j>i, then 

z_i  R  x_i = y_i
and z≺_alty, also a contradiction. If j=i, then 

z_j  R  x_j  R  y_j and z≺_alty, again a contradiction. 
 

We conclude that x≺_alty≺_altz 
requires x≺_altz; 

that is, the transitivity establishes that ≺_alt is a total order over Σ^+.
As usual, ε is the unique least string, and so ≺_alt forms a total order over Σ^*.





 

















 



Since ≺_alt is a total order, it is a candidate for constructing a 𝒯_≪-word (Definition <ref>) for a new circ-UMFF, making use of Theorem <ref>.
We therefore consider a concept analogous to Lyndon and V-words based on alternating lexorder:  





 <cit.>


A Galois word is a nonempty primitive string that is minimum in alternating lexorder over its conjugacy class.




We observe that every element of Σ is a Galois word. Thus the set of Galois words forms an FF — see Section <ref>.
Since the rotations of primitive strings are distinct, therefore the Galois word of each conjugacy class is uniquely defined. 
Examples of Galois words are: ab, aba, abb, abba, ababa, ababaa, ababba. Observe that these words are not necessarily border-free and can even be palindromic. Furthermore, unlike Lyndon words and V-words, Galois words don't exhibit the ordered shuffle property <cit.> where interleaving characters/V-letters generates a string in the given circ-UMFF; for example, interleaving the Galois words aba and abb, where aba ≺_alt abb,  yields aabbab, which is not a Galois word — instead the conjugate abaabb is Galois. If we try to apply Lemma <ref> to the Galois words xy = ababa and yz = ab with y = a, we get xyz = ababab, a repetition, while Galois words are by definition primitive. Hence 

Galois words do not form an UMFF, nor therefore a circ-UMFF.
Since Galois words can be bordered, this observation is consistent with Theorem <ref>, which allows a circ-UMFF only for classes of border-free words. 


A related 

observation in <cit.> shows that, although Theorem <ref> implies that the unique maximal Lyndon factorization
of a word has a least number of nonincreasing Lyndon factors, this is not necessarily the case for Galois words:


 [Example 44 in <cit.>]

Let w be the repetition ababab, hence not a Galois word. Then w = (ab)(ab)(ab) is a nonincreasing factorization into Galois words. However, w also admits a shorter (and increasing) factorization into Galois words, namely w = (ababa)(b).

In this example, for w = (ababa)(b) we have ababa ≺_alt b, although, since ababab ∉𝒲, ababa is not less than b in 𝒲-order 

(Definition <ref>) — that is, ababab is not a Galois word. 

Note also that w = (ab)(ab)(ab) is the unique Lyndon factorization of w.


Still, Galois words have applications. The Alternating Burrows-Wheeler Transform (ABWT) is analogous to the BWT and applies alternating lexorder <cit.>. An algorithmic perspective on the ABWT is given in <cit.>, where a linear time and space algorithm, , determines for each primitive string its unique cyclic rotation that is a Galois
word, which in turn supports computing the ABWT in linear time. Furthermore, practical uses of the ABWT in settings such as data compression and
compressed data structures are demonstrated.

Clearly, like lexorder string comparison, alternating lexorder comparison of two strings can be achieved in linear time and space. It follows that efficient suffix array construction methods based on lexorder, such as <cit.>, can be readily modified to apply alternating lexorder. In the alternating lexorder suffix array of a Galois word with border b, given that a border of a Galois word must have odd length 
<cit.>, then by Definition <ref>(2), a suffix starting with the prefix b will precede
the suffix b.

We now go on to explore new combinatorial properties of Galois words, starting with the Galois equivalent of the fundamental Lyndon result, Theorem <ref> — albeit with the caveat of possible repetitions, previously shown by the example ababa ≺_alt b.  We let 𝒢 denote the set of Galois words on a given alphabet. 

(<cit.>)
A Galois word w∈𝒢 is smaller than any of its proper suffixes with respect to ≺_alt order.




Let u,v∈𝒢, where u is not a proper prefix of v. Then, u≺_altv if and only if

    (1) u≺_altvx, ∀x∈Σ^+; 

     (2) ux≺_altv, ∀x∈Σ^+; 

    (3) ux≺_altvx, ∀x∈Σ^+; 

    (4) u^k+1≺_altu^kv, for k ≥ 0.

 
NECESSITY. Suppose u≺_altv. Since u is not a proper prefix of v, therefore ∀x∈Σ^*,  u is not a proper prefix of vx, and ux is not a proper prefix of v and vx — and u^k+1 is not a prefix of u^kv. Moreover, since u≺_altv and u is not a proper prefix of v, there is a smallest index i such that u_i ≠ v_i. Consider a corresponding relation R (< or > for odd or even index i, respectively) — then since u_i ≠ v_i, it follows that u_i R v_i implies (u)_i R (vx)_i, (ux)_i R (v)_i, (ux)_i R (vx)_i and (u^k+1)_i R     (u^kv)_i. Therefore, by Definition <ref>(1) cases (1)–(4) hold. 

SUFFICIENCY. Suppose cases (1)–(4) hold. Since u is not a proper prefix of v, by the same reasoning as above, we get (u)_i R (vx)_i, (ux)_i R (v)_i, (ux)_i R (vx)_i and (u^k+1)_i R (u^kv)_i which implies that u_i R v_i. Therefore, by Definition <ref>(1), u≺_altv. 




Let u,v∈𝒢. If u≺_altv and u is a proper prefix of v, then

    (1) ∀x∈Σ^+, u≺_altvx; 

    (2) ∀ k ≥ 0, u^k+1≺_altu^kv.
     


Suppose u≺_altv and u is a proper prefix of v. By Definition <ref>(2), |u| must be even. We write v = u^rv', such that r≥ 1 and v' is the largest suffix of v that does not contain u as its prefix. Then, u^kv = u^k+rv'. Clearly, u is a prefix of vx and u^kv. By hypothesis |u| is even. Hence, by Definition <ref>(2), cases (1) and (2) hold.

 



Suppose u, v∈
𝒢. If uv is primitive,  then u≺_altv if and only if uv∈𝒢.


NECESSITY. Suppose that u≺_altv. Since uv is primitive, there exists a rotation of uv that is least in alternating lexorder (≺_alt). Let u = u_pu_s and v=v_pv_s, where u_p, u_s, v_p, v_s ≠ε. Then, we need to show

    
  (1) uv≺_altu_svu_p;
    
  (2) uv≺_altvu;
    
  (3) uv≺_altv_suv_p.

(A) Suppose u is not a proper prefix of v. By Lemma <ref>, we have u≺_altu_s, and by Lemma <ref>(3) and (1), we have uv≺_altu_sv and uv≺_altu_svu_p, respectively. Therefore case (1) holds. From the hypothesis and by Lemma <ref> we have u≺_altv_s. By Lemma <ref>(2) and (1), we have uv≺_altv_s and uv≺_altv_suv_p, respectively, and so case (3) holds. Finally, from the hypothesis we have u≺_altv. By the application of Lemma <ref>(1) and (2), we have u≺_altvu and uv≺_altvu, respectively. Thus case (2) holds. 

(B) Suppose u≺_altv, and u is a proper prefix of v. 
By Lemma <ref>, we have u≺_altu_s. By Lemma <ref>(1) and (2) we get u≺_altu_svu_p and uv≺_altu_svu_p, respectively. Thus case (1) holds.  
By hypothesis and Lemma <ref>, we get u≺_altv_s, and by Lemma <ref>(1) and (2) we get u≺_altv_suv_p and uv≺_altv_suv_p, respectively. Hence case (2) holds.  
We write v = u^rv', such that r≥ 1 and v' is the largest suffix of v that does not contain u as its prefix. Since uv and vu are of the same length, neither can be a proper prefix of the other. By the hypothesis and Lemma <ref> u≺_altv' and u is not a proper prefix of v'.  Then uv = u^k+1v' and vu = u^kv'u. By Lemma <ref>(4), we get u^k+1≺_altu^kv'. By further application of Lemma <ref>(1) and (2), we get u^k+1≺_altu^kv'u and u^k+1v' ≺_altu^kv'u, respectively. Thus uv≺_altvu and case (3) holds. 

SUFFICIENCY. Suppose that primitive uv∈𝒢. Then u≠v, and uv is strictly least in its conjugacy class in ≺_alt order. Suppose v≺_altu. Then, by the proof of Necessity, we find that vu is a Galois word — a contradiction. Since u≠v and v⊀_altu, Theorem <ref> implies that u≺_altv.

Thus the theorem is proved.














































































































































We formalize the notion of concatenation order 𝒲 (Definition <ref>) “aligning” with   
𝒯-order 

(Definition <ref>):




Given a circ-UMFF 𝒲, a concatenation order <_𝒲  
and a 𝒯-order

with order relation ≪,



we say that 𝒲 is 𝒯-order aligned

if, for given strings u, v∈Σ^*, u <_𝒲v and u≪v.


The classic example is the lexorder alignment of Lyndon words, as expressed in Theorem <ref>. On the other hand, this alignment doesn't hold for co-Lyndon words (the co-lexorder analog of Lyndon words where co-lexorder is lexorder of reversed strings): 

ba is less than ca in co-lexorder, while baca is not a co-Lyndon word — instead, it is 
the conjugate caba. A further example of non-alignment arises with V-order — see Lemma 3.16 in <cit.>. We have seen that Galois words do not form a circ-UMFF and, furthermore, Theorem <ref> shows that alternating lexorder ≺_alt is not in general aligned with Galois concatenation.





We now show that the set of border-free Galois words over any alphabet, denoted 𝒢^bf, yields a unique maximal factorization: 


𝒢^bf forms an UMFF.


We will show that

the 𝒢^bf satisfies the 𝐱𝐲𝐳 Lemma <ref>. 
Thus we suppose that xy,yz∈𝒢^bf for some nonempty y; it is then required to show that xyz∈𝒢^bf. We may assume also that both x and z are nonempty, for otherwise by Lemma <ref> the claim holds trivially.

We start by showing that xyz is least in ≺_alt order amongst its conjugates. 
Write xyz = x_1 … x_r y_1 … y_s  z_1 … z_t, r,s,t ≥ 1, and consider ordering the conjugates of xyz in ≺_alt order (Definition <ref>). Let 𝒞^≺_alt denote the conjugacy class of xyz, where the conjugates are ordered according to ≺_alt.
Since a Galois word is less than any of its proper suffixes in ≺_alt order 
<cit.>, this property therefore holds for xy and yz. For the ordering of 𝒞^≺_alt, consider a conjugate c of xyz starting with a nonempty suffix s of x_2 … x_r y_1 … y_s. Since xy is assumed to be border-free, xy[1..|s|] ≠s and thus the comparison between xyz and c is determined based on Definition <ref>(1). Therefore
the conjugate of xyz starting with prefix xy, namely xyz, comes before any conjugate in 𝒞^≺_alt starting with a suffix of x_2 … x_r y_1 … y_s

and in particular starting with y. 

That is, if xy= ps for nonempty p, s, then xy≺_alts implies that xyz≺_alts≺_altszp.
Likewise, the conjugate of xyz starting with prefix yz, namely yzx, comes before any conjugate in 𝒞^≺_alt starting with a suffix of  y_2 … y_s z_1 … z_t, and as before we can assume this is determined using Definition <ref>(1).  
We conclude that xyz precedes all its conjugates in 𝒞^≺_alt, as required.



Suppose now that xyz is bordered with border b so that xyz = bub for u∈Σ^*. Then b is both a prefix of xy and a suffix of yz. Since distinct xy, yz∈𝒢^bf, both are border-free, and so xy cannot have suffix b nor can yz have prefix b. We can then write xyz= bub = b_1b_2 … b_r   u_1u_2 … u_s   b_1b_2 … b_r, r,s ≥ 1. If we suppose that |xy| > r+s, then xy is bordered; similarly, if |yz| > s+r, then yz is bordered. 



So y = u_i … u_j, 1 ≤ i, j ≤ s. 
The smallest and first conjugate in 𝒞^≺_alt is xyz = x u_i … u_j z = b u_1 … u_s b, and since the ordering of 𝒞^≺_alt applies 

(Definition <ref>(1)), common prefixes occur concurrently in 𝒞^≺_alt; in particular, if there are n_b occurrences of b in xyz, they will occur as prefixes of the first n_b conjugates in 𝒞^≺_alt. 



One of the conjugates in 𝒞^≺_alt is yzx, where yzx = u_i … u_s bx and xyz≺_altyzx. However, since b is a prefix of the first conjugate xyz, this contradicts that yz = u_i … u_s b is less than its proper suffix b in ≺_alt order. We conclude that xyz is border-free, and therefore primitive, which completes the proof.








We illustrate Lemma <ref>:


 Let xy, yz∈𝒢^bf, where xy= abababbb and yz= ababbbbb and y= ababbb then, applying Lemma <ref>, xyz = abababbbbb with xyz∈𝒢^bf.





 §.§ Binary Border-free Galois words

We next consider the structure of binary border-free Galois words, denoted 𝒢^bbf, where we assume that 
Σ = {a, b} with a<b. The first few such words are a, b, ab, abb.





Suppose w∈𝒢^bbf over Σ = {a, b}, where a < b, with n = |w| ≥ 3. Then w has prefix ab and suffix bb.





By definition w 
is primitive and so contains 

both letters in Σ.
Also by definition, w is minimum over its rotations,


and so starts with a; since it is border-free, it must therefore end with b. 
The claim clearly holds for w = ab^k, k ≥ 2, 
as all non-trivial rotations of w start with b making w least in ≺_alt order. 
So suppose that w = avb where v∈Σ^+:  




  * If w[n-1] = a, then the suffix is ab. Let u denote the conjugate of w such that 
u = w[n-1]w[n]w[1..n-2]. Since w is least in ≺_alt order, and the comparison of w[2] and u[2] is based on the relation ≥, therefore w[2] cannot be a, thus

yielding prefix ab and so a bordered word.  Hence w[n-1] = b and the suffix is bb, as required.

  * Since w≠ ab^k, k ≥ 3, therefore v 
contains an a. Let a_i be the a in v with largest i, so that 1< i <n-1, and since the string w must end with bb we know that the (i+1)^ th letter is b. Let 
u' = w[i]w[i+1]..w[n]w[1 .. i-1]. Since  w is least in ≺_alt order, therefore as above w[2] cannot be a, 

thus yielding prefix ab.  

We conclude that w has prefix ab and suffix bb, as required.






We next consider the general form of a binary border-free Galois word w, |w| >3. By Lemma <ref>,  if w∈𝒢^bbf, w begins with ab. Trivially if  w = ab^h, h>1, then w∈𝒢^bbf. So suppose that w≠ ab^h, thus containing at least two a's — since any conjugate of w starting with b is consistent with w∈𝒢^bbf, we restrict analysis to conjugates starting with a.  

Consider a run in w of the form a^k, k>1. Then since w has prefix ab, any conjugate of w starting with a^j, 2 ≤ j ≤ k, is consistent with w∈𝒢^bbf. So we consider conjugates c_ab of w starting with ab and note the index d of the first difference between w and c_ab — since w is primitive, w and c_ab are distinct.






We say a substring u of w is an ab-Galois word if u has prefix ab and contains no other occurrence of ab. Therefore u has the form a b^e a^f, e ≥ 1, f ≥ 0. Then u is a Galois word (not necessarily border-free): clearly u is primitive, and it is less in alternating lexorder ≺_alt than any conjugate of u starting with b and likewise less than any conjugate starting with aa, if such exists.
 



Given a primitive binary string
w,  
let ℱ be the factorization of w into ab-Galois words u_1,u_2⋯u_t, such that ℱ = (u_1) (u_2) ⋯ (u_t), t ≥ 1. 

If |u_1| = |u_2| = ⋯ = |u_t|, and w is a Lyndon word under 𝒯_lex-order (Definition <ref>) with  ≺_alt order, then ℱ∈𝒢^bbf.










Trivially this holds for any conjugates starting with aa or b. For conjugates starting with ab, we first observe that Theorem  <ref> shows that alternating lexorder ≺_alt is a candidate for 𝒯-order (Definition <ref>). Then the result is an immediate consequence of maintaining Lyndon properties for conjugates starting with ab-Galois words when generalising lexorder to lex-extension order. In particular, w is border-free.




For the next more general result, we require a refinement of Definition <ref>(2). We define modified alternating lexorder ≺_modalt as follows: 










 
Let x, y∈Σ^+ be distinct nonempty strings, where x is a proper prefix of y. Let S be the largest set of strings in Σ^+ such that for every z∈ S, xz≺_alty, and neither xz is a prefix of y nor is y a prefix of xz. Then, if S ≠∅, x≺_modalty; otherwise, y≺_modaltx. 




   Modified alternating lexorder ≺_modalt 

   is a total order over Σ^*.


 
Consider distinct strings x, y, t∈Σ^+. Assume that x≺_modalty and y≺_modaltt. We need to show that x≺_modaltt.

By assumption and Definition <ref>, x is a nonempty proper prefix of y and y is a nonempty proper prefix of t. Hence we write y=xy', where y' ≠ε, and t = yt', where t' ≠ε. Then, by substitution, we get t= xy't'. Also, by assumption and Definition <ref>, we may suppose S, S' ⊂Σ^+ are nonempty sets satisfying the following conditions:

    
  * xz≺_alty, where for every z∈ S, neither xz is a prefix of y nor is y a prefix of xz.
    
  * yz' ≺_altt, where for every z' ∈ S', neither yz' is a prefix of t nor is t a prefix of yz'.


Since xz is not a proper prefix of y, by Lemma <ref>(1) and (2), we get xz≺_altyz' and xzz”≺_altyz', where z' ∈ S', z”∈Σ^+, respectively. Then, by Theorem <ref>, we get xzz”≺_altt. Since xz is not a prefix of y nor y a prefix of xz, and since y is a prefix of t, we conclude that xz and t are not prefixes of each other, nor are xzz” and t prefixes of each other. Let S” denote the set containing all strings of the form zz”. Clearly, S”≠∅.  Therefore, by Definition <ref>, we conclude that x≺_modaltt.
This completes the proof.

We will also apply the concept of a Hybrid Lyndon word, whereby a string x in V-form with x_0 = ε is a Hybrid Lyndon if and only if it is Lyndon under lexicographic extension <cit.>. 




Given a primitive binary string w, with |w| > 3, let ℱ be the factorization of w into ab-Galois words u_1,u_2⋯u_t, such that ℱ = (u_1) (u_2) ⋯ (u_t), t ≥ 1. 
Then w∈𝒢^bbf if and only if ℱ forms a Hybrid Lyndon word using 𝒯_lex-order (Definition <ref>) with ≺_modalt order.




NECESSITY. Suppose w∈𝒢^bbf with |w| > 3. From Claim <ref>, w starts with ab, namely an ab-Galois word, which is consistent with w being less in ≺_alt order than any conjugate c of w starting aa or b.
 

Hence we restrict our analysis to conjugates starting with ab, that is ab-Galois words (factors of ℱ). Consider the comparison of w = (u_1) (u_2) ⋯ (u_t) = w[1..t] and the i^th substring conjugate

c_i of w where both have prefix ab, so that  c_i = (u_i+1) (u_t) (u_1) ⋯ (u_i) = c_i[1..t]. Since w is primitive, w and c_i are distinct, and as w∈𝒢^bbf then w≺_altc_i which is decided according to Definition <ref>. Let d be the index of the first distinct ab-Galois words  between w and c_i, that is 



w[1..d-1] = c_i[1..d-1], and let h = min {|w[d]|, |c_i[d]|}.


Then according to Definition <ref>, there are two cases to consider:


Definition <ref>(1). In this case the two factors differ at an index q ≤ h, that is w[g+q] ≠c_i[g+q], where g = ∑_j=1^d-1|u_j|. Since w≺_altc_i, we have w[g+q]  R c_i[g+q], where R = < if g+q is odd and R = > if g+q is even. This holds for any conjugate satisfying Definition <ref>(1) and thus this case is consistent with ℱ forming a Hybrid Lyndon word using 𝒯_lex-order (Definition <ref>) with ≺_modalt order (which is in fact regular ≺_alt order here).


Definition <ref>(2) (Notation as in part (1).) In this case, with w[d] ≠c_i[d], one factor is a proper prefix of the other factor. Since w∈𝒢^bbf and w≺_altc_i, if w[d] is a proper prefix of c_i[d], then |u_d| = h < |c_i[d]|, whereby d<t. Then applying ≺_modalt order, 

w[d+1] has prefix ab while, by definition of an ab-Galois word, 

c_i[d] has only one occurance of ab which occurs at its prefix. So the comparison which determines w≺_altc_i is between w[d+1] and c_i[d], in particular between an a and b or between ab and aa with the appropriate relations (< / >). Similarly, if c_i[d] is a proper prefix of w[d], then ≺_modalt order applies as appropriate to ensure w≺_altc_i.

This ordering holds for any conjugate satisfying Definition <ref>(2) and thus this case is consistent with ℱ forming a Hybrid Lyndon word using 𝒯_lex-order (Definition <ref>) with ≺_modalt order.
 

SUFFICIENCY. Suppose the Hybrid Lyndon condition in the statement holds for a primitive binary string w. Clearly, w is less than any conjugate c of w starting aa or b with respect to ≺_alt order. So consider any conjugate c starting with an  ab-Galois word. Accordingly, the Hybrid Lyndon constructed from 𝒯_lex-order (Definition <ref>) with ≺_modalt order guarantees that w≺_altc for all conjugates starting with an ab-Galois word.  Hence all forms of conjugates are considered. Furthermore, from Lyndon properties, w is border-free. Thus, w∈𝒢^bbf.



    
Let w = abbbabbabbbbb be a binary primitive string, so that ℱ = (abbb) (abb) (abbbbb) with t = 3. Then, for instance, w = (abbb) (abb) (abbbbb) ≺_modalt (abb) (abbbbb) (abbb) since (abbb) ≺_modalt (abb) (abbbbb), 
and since   (abbb)(abb) ≺_modalt (abbbbb), w = (abbb) (abb) (abbbbb) ≺_modalt (abbbbb) (abbb) (abb).



In considering whether the set 𝒢^bbf forms an UMFF, as in Lemma <ref>, let u = abbbbb and v = ababbb, where u,v∈𝒢^bbf. But observe that uv is bordered with border abbb, indicating that 𝒢^bbf may not form an UMFF. On the other hand, applying Lemma <ref> with xy = v and yz = u, where y = abbb, yields xyz = ababbbbb, which does belong to 𝒢^bbf indicating 𝒢^bbf may form an UMFF.   








§ UMFF TO CIRC-UMFF CONSTRUCTION



In this final section we propose a method for circ-UMFF construction that is based on 

Theorem 4.1 in <cit.> — which states that any binary border-free UMFF can be enlarged to a binary circ-UMFF. 

Our algorithm takes as input 

a binary border-free UMFF 𝒲 of size n, where the words are given in increasing length, and outputs an enlargement of 𝒲 to a finite circ-UMFF which is necessarily border-free. We assume |𝒲| > 2; otherwise, the UMFF would contain only the alphabet.  Thus we may choose a known circ-UMFF such as binary Lyndon words or binary V-words. The algorithm is in 3 stages:


  * input the UMFF and record where word lengths change; 
  * generate all strings in Σ^* up to length 2^|w_n|+1 - 2, where |w_n| is the length of the longest word in 𝒲; 

  * generate the primitive border-free circ-UMFF words using w_3=[w_1 … w_m]; that is, [w_m w_1] is added to the circ-UMFF (assumed necessarily).
The subset of Σ^* is computed in  (Algorithm <ref>) and all variables are assumed to be global.








Algorithm  <ref> correctly computes a finite circ-UMFF from a finite binary border-free UMFF.



This follows from the method of the proof of Theorem 4.1 in <cit.> which states that any border-free binary UMFF can be enlarged to a binary circ-UMFF. All words in Kleene star up to a specified length are considered for the new circ-UMFF and each candidate word is checked to be primitive — all as required by Definition <ref>.





The rationale of Algorithm <ref> is as follows.  
 Given, for instance, the border-free UMFF 𝒢^bf over Σ{a,b}, we consider extending a subset of 𝒢^bf to a new circ-UMFF which is necessarily border-free. 
 For example, suppose abababbb ∈𝒢^bf, and consider the primitive string w = ababba, where w∈{𝒢∖𝒢^bf}; that is, w is a bordered Galois word.  According to Definition <ref>, we need to choose one border-free conjugate from the conjugacy class of w — Lyndon words show that a border-free conjugate of a primitive string always exists, so there will be at least one border-free conjugate to choose from. For example, applying Theorem <ref>(5), we select the border-free conjugate aababb of w, where a, ababb ∈𝒢^bf, and note that the bordered word ababba is the Galois conjugate of w while aababb happens to be the Lyndon conjugate of w. Note further that, with reference to Lemma <ref>, abababbb and aababb are mutually border-free and so we cannot generate another word for the new circ-UMFF from them by applying Lemma <ref>.




Algorithm <ref> generates a finite circ-UMFF but can be easily modified to construct an infinite circ-UMFF.

We illustrate the algorithm by extending the border-free UMFF in Lemma <ref> to a circ-UMFF: 

 Given an UMFF 𝒱 over Σ = {a,b} consisting of a subset of border-free Galois words, we enlarge 𝒱 to the circ-UMFF 𝒲 for words up to length 5; 𝒱 and 𝒲 are specified below where the Galois words in 𝒲 are underlined:


  * 𝒱 = {a, b, abb, ababb}

  * 𝒲 = {a, b, ab, aab, abb, aaab, aabb, abbb, aaaab, aaabb,aabab, aabbb, ababb,

abbbb}

For instance, string x = b b ababb aaabb a  b  aabbb a a factors uniquely and maximally:  
  

  * over 𝒱, x =(b) (b) (ababb) (a) (a) (abb) (a)  (b)  (a) (abb) (b) (a) (a) 

  * over 𝒲, x = (b) (b) (ababb) (aaabb) (ab) (aabbb) (a) (a)

  * but not necessarily uniquely over 𝒢, x = (b) (b) (ababb aaabb abaabbba a)




We believe this is the first example of a unique factorization family which is based on more than one type of ordering methodology.





Regarding factoring strings over circ-UMFFs which are derived from mixed methods, such as 𝒲 in Example <ref>, this can be achieved efficiently using the generic algorithmic framework given in <cit.>.



§ CONCLUDING COMMENTS






The concept of circ-UMFFs for uniquely factoring strings is a generalization of Lyndon words, which are known to be border-free string conjugates. The literature includes instances  of circ-UMFFs for both regular and indeterminate (degenerate) strings. In this paper we have extended current knowledge on circ-UMFF theory including a further generalization to substring circ-UMFFs. Known instances of circ-UMFFs have been defined using a total order over Σ^*, such as V-order for arbitrary alphabets generating V-words, binary B-order generating B-words, and lex-extension order generating indeterminate Lyndon words.
 

We establish here that given any total ordering methodology 𝒯 over Σ^*, and a subset of Σ^* consisting of border-free conjugates minimal in 𝒯-order, the subset defines a circ-UMFF. An analogous result is established for substring circ-UMFFs. The border-free requirement is illustrated using Galois words by showing that they do not necessarily yield unique maximal string factorization — Galois words are thus worthy of deeper investigation in this context.
 

We have also delved further into the relationship between Lyndon and V-words, in particular showing that
there are infinitely more V-words than Lyndon words. Other novel concepts are illustrated throughout.

1cm



 §.§ Open Problems




    
  * 
Non-unique factorization of a string is not necessarily a bad thing, since having multiple factorizations of a given string x, such as with Example 44 in <cit.>, opens avenues for choice. Accordingly, we propose future UMFF-based research into optimization type problems for string factoring over a fixed alphabet Σ, such as finding the factorization of x with the least/greatest number of factors. Related research on controlling Lyndon factors and influencing the run number of the Burrows-Wheeler transform by manipulating the order of Σ has been investigated in <cit.>.


  * Generalize Algorithm <ref> for enlarging a border-free UMFF to a circ-UMFF from binary to general alphabet. 

Observe that Example <ref> on a ternary alphabet shows that two conjugates from the same conjugacy class — namely abc and cab — can belong to an UMFF 𝒲. So this 𝒲 cannot be extended to a circ-UMFF, which by Definition <ref> must contain exactly one conjugate from each conjugacy class. However, as the example shows, 𝒲 is not border-free. 



  * Application of distinct string ordering methods over Σ^* and associated circ-UMFFs has been studieded in the context of the Burrows-Wheeler transform and indexing techniques <cit.>. There is much scope for discovery of new UMFFs and circ-UMFFs, and subsequent exploration of new instances, both combinatorially and algorithmically, over a variety of alphabets. 
 


  * The novel entity of circ-UMFFs defined using mixed methods identified in this work is worthy of thorough investigation. For instance, with reference to Example <ref>, where 𝒲 is the union of Galois and Lyndon words, the following question arises:
given UMFFs 𝒳, 𝒴, both over Σ, and defined using ordering method Ω_𝒳, Ω_𝒴, respectively, where 𝒳 generates both bordered and border-free words, then for each primitive bordered word b in 𝒳, choose a border-free conjugate of b from 𝒴 for the new circ-UMFF. Since in Example <ref> Ω_𝒳 is alternating lexorder and Ω_𝒴 is lexorder, can Ω_𝒴 always be lexorder — since every conjugacy class of a primitive word contains a border-free Lyndon word?  





 

 §.§ Acknowledgements


Funding: The second and third authors were funded by the Natural Sciences & Engineering Research Council of Canada [Grant Numbers: RGPIN-2024-06915 and RGPIN-2024-05921, respectively].

Australasian J. Combinatorics 
Australasian Workshop on Combinatorial Algs.
Annual Symp. Combinatorial Pattern Matching
Annual International Computing & Combinatorics Conference
IEEE Symp. Found. Computer Science
Annual European Symp. on Algs.
Internat. Conf. on Language & Automata Theory & Applications
Internat. Workshop on Combinatorial Algs.
Australasian Workshop on Combinatorial Algs.
Internat. Symp. Theoretical Aspects of Computer Science
Internat. Colloq. Automata, Languages & Programming
Internat. J. Foundations of Computer Science 
Internat. Symp. Algs. & Computation
String Processing & Inform. Retrieval Symp.
Scandinavian Workshop on Alg. Theory
Prague Stringology Conf.
International Workshop on Algorithms & Computation
Algorithmica 
ACM Computing Surveys 
Fundamenta Informaticae 
Inform. Process. Lett. 
Inform. Sciences 
J. Assoc. Comput. Mach. 
Commun. Assoc. Comput. Mach. 
Math. in Computer Science 
Nordic J. Comput. 
SIAM J. Computing 
SIAM J. Discrete Math. 
J. Computational Biology 
J. Algorithms 
J. Combinatorial Maths. & Combinatorial Comput. 
J. Discrete Algorithms 
J. Automata, Languages & Combinatorics 
ACM-SIAM Symp. Discrete Algs. 
Software, Practice & Experience 
The Computer Journal 
Theoret. Comput. Sci. 


splncs04

