The Burrows-Wheeler Transform (BWT) is a powerful transform widely used in string compression and string processing. It produces a reversible permutation of the characters of the input string, often allowing for easier compression of the string, while also enabling fast pattern matching. While the BWT is defined for every word, not every word is the BWT of some word. A characterization of BWT images was given in [Likhomanov and Shur, CSR, 2011], based on the standard permutation of the string. Often an end-of-file character $ is added to mark the end of a string. Given a string , it is an interesting combinatorial question where a $ can be inserted to make the BWT of some string $. This question was answered in [Giuliani et al. Theor. Comput. Sci. 2021], where an eficient algorithm was presented for computing all such positions (called nice positions), and a characterization of nice positions was given, based on pseudo-cycles in the standard permutation of . In this paper, we give a stronger characterization of nice positions: We show that these can be characterized using only essential pseudo-cycles, which constitute a small subset of all possible pseudocycles. We present an algorithm to compute all essential pseudo-cycles of a word . In the second part of the paper, we study nice positions of fully clustered words: these are words whose number of runs equals the number of distinct characters occurring in . Fully clustered words are of particular interest due to their extreme compressibility, and words whose BWT is fully clustered have been studied extensively. We are interested in the number of nice positions of fully clustered words, as well as in the number of fully clustered words with nice positions, for fixed and word length.
The Burrows-Wheeler Transform (BWT) [
The BWT has also been studied intensively from a combinatorics on words point of view,
with [
In this paper, we continue the study of the following combinatorial problem, introduced in [22]: Given a word , where, if at all, can a sentinel character $ be inserted into to make it the BWT of some word ending with $? We call such positions nice positions. The question is motivated by the fact that in the application context, often such a sentinel character $ is appended to mark the end of the input string.
In [22], an ( log )-time algorithm for computing all nice positions was given, as well as a characterization using so-called pseudo-cycles. In this paper, we give a stronger characterization of nice positions, restricting the set of pseudo-cycles to a subset which can be exponentially smaller than the complete set. We also present an (2)-time algorithm that computes nice positions via this restricted set of pseudo-cycles. Although the new algorithm is slower than the previous one in the worst case, it gives more information in output, thus opening up new possibilities of insights into the problem.
We then apply this algorithm to the study of nice positions in fully clustered words. These are words whose number of equal-letter-runs equals the number of distinct characters, such as = bbbbcaa. Words whose BWT is fully clustered are of special interest because of their high compressibility via the BWT; e.g. such a word is abbacbb, with BWT . Over a binary alphabet, it is known that a word has fully clustered BWT if and only if it is conjugate of a standard word or of a power of a standard word [20]. Over a ternary alphabet, there exists a characterization via morphisms, of words whose BWT has the form cb a (there called Type I) [23], while a combinatorial property (circular palindromic richness) was shown to be a necessary but not suficient condition for such words [
24, 25]. This result extends to larger alphabets, i.e. words whose BWT has the form − − 11 . . . 11 , with alphabet Σ = {1, 2, . . . , } and 1 < 2 < . . . < . Finally, a characterization of words with fully clustered BWT, over arbitrary alphabets, was given in terms of discrete interval exchanges in [26].
We present both theoretical and experimental results on nice positions in fully clustered words, as well as on the number of words with nice positions, for fixed . We studied binary and ternary alphabets. Due to space restrictions, we present only the results on the binary alphabet, as well as having to omit some proofs. Both will be included in the full version.
Overview of paper: In Section 2, we introduce the necessary notation and basic facts. In Section 3, we give the new stronger characterization of nice positions, and in Section 3.1, we describe the algorithm exploiting the new characterization. In Section 4, we present some properties and conjectures related to nice positions for fully clustered words for the unary and binary alphabets. We close with a brief outline of future work in Section 5.
Strings and permutations. Given a finite ordered alphabet Σ, a string (or word) over Σ is a ifnite sequence = 0 · · · − 1 of characters from Σ. We denote by the size of Σ, by || = the length of a word 0 . . . − 1, and by the empty word, the only string of length 0. Note that we index strings from 0. We denote by alph() = { | there exists 1 ≤ ≤ | | : = } the set of characters occurring in . For two words , , denotes their concatenation, given by = 0 · · · ||− 10 · · · ||− 1. If = , then is called a prefix , a substring, and a sufix of . Given a word and a positive integer , = · · · denotes the -fold concatenation of . A word is called a power if it can be written as = for some > 1, otherwise it is called primitive. Often a sentinel character, denoted $, is appended to mark the end of a string, where $ does not occur elsewhere in the string, and is assumed to be smaller than all ∈ Σ. Clearly, every word of the form $ is primitive.
Two words , ′ are called conjugates (or rotations) if there exist , , possibly empty, such that = and ′ = . Given a word = 0 · · · − 1, the ’th rotation of , for 0 ≤ ≤ − 1, is · · · − 10 · · · − 1. A word of length is primitive if and only if it has distinct conjugates. The set of all words over Σ is totally ordered by the lexicographic order: Let , ∈ Σ* , then ≤ if is a prefix of , or there exists an index s.t. for all < , = , and < according to the order on Σ.
A run in a word is a maximal substring consisting of the same character. A fully clustered word is a word with |alph()| runs. Given a word = 00 11 · · · −− 11 with runs, we define its pattern as pat() = 01 · · · − 1. For example, the fully clustered word = bbccccca has pattern pat() = bca.
Let be a positive integer. A permutation of is a bijection from the set {0, . . . , − 1} to itself. A common way to represent permutations is the two-line notation: = (︀ (00) (11) ...... (−− 11) )︀ . (Note that we index permutations from 0.) A cycle of is a minimal subset of the elements of the permutation such that () = . A cycle of length 1 is called a fixpoint , one of length 2 is called a transposition. It is a basic result on permutations that every permutation can be uniquely decomposed into disjoint cycles, giving rise to another common representation of permutations, the cycle representation. For example, = (︀ 0 1 2 3 4 5 )︀ has cycle representation 2 3 0 5 4 1 (0 2)(1 3 5)(4), where (0 2) is a transposition, (1 3 5) is a cycle of length 3, and (4) is a fixpoint. A permutation that consists of one cycle only is called cyclic. For more details on permutations, see [27]. Given a word , the standard permutation of , denoted , is the permutation defined by: () < () if and only if either < , or = and < . For example, the standard permutation of banana is (︀ 0 1 2 3 4 5 )︀ = (0 3 1)(2 4 5).
3 0 4 1 5 2
Burrows-Wheeler-Transform. Given a word of length , the Burrows-Wheeler-Transform
(BWT) [
While the BWT is defined for every word, not every word is the BWT of some word. Likhomanov and Shur have shown that a word is the BWT of some word if and only if the number of cycles of its standard permutation equals the greatest common divisor of the runlengths of [21] (see also [20, 23] for earlier, more restricted versions of this statement). For example, the standard permutation of nnbaaa is (︀ 0 1 2 3 4 5 )︀ = (0 4 1 5 2 3). It has one 4 5 3 0 1 2 cycle and this equals gcd(2, 1, 3); indeed, nnbaaa is the BWT of the word banana. Conversely, banana’s standard permutation has two cycles, but the gcd of its runlengths is 1, and therefore, it is not the BWT of any word.
Nice positions and pseudo-cycles. When is a word the BWT of some word of the form $, where $ is the sentinel character? It is clear that such a word must have exactly one occurrence of $. Thus, it follows from the result of Likhomanov and Shur that its standard permutation must be cyclic.
The following question was studied in [22]: Given a word , where can $ be inserted into such that the resulting word is the BWT of some $? Such positions are called nice, formally: Given = 0 · · · − 1, a position is nice, 0 ≤ ≤ , if the ( + 1)-length word ′ is the BWT of some word of the form $, where ′ = for < , ′ = $, and ′ = − 1 for ≥ . For example, the word nnbaaa has two nice positions, 1 and 3: n$nbaaa = bwt(abanan$) and nnb$aaa = bwt(anaban$), while banana has none: nowhere can a $ be inserted to make it the BWT of some word.
Let be a permutation of . A non-empty subset ⊆ { 0, 1, . . . , − 1} is called a pseudo-cycle if it can be partitioned into two sets left and right, where left < right (elementwise), such that () = { − 1 | ∈ left} ∪ right. The critical interval of pseudo-cycle is = [ + 1, ], where = max left and = min right. If left is empty, we set = − 1, and if right is empty, we set = . An example of a pseudo-cycle is given in Fig. 1. When $ is inserted in the critical interval, becomes a cycle, hence the resulting standard permutation is not cyclic. The following characterization of nice positions was given in [22]: Theorem 1 (Thm. 6 in [22]). Let be a word of length over Σ, and 0 ≤ ≤ . Then is nice if and only if there is no pseudo-cycle w.r.t. the standard permutation whose critical interval contains .
We will denote by the critical set of , the union of the critical intervals of all pseudocycles. By Thm. 1 then is nice if and only if ̸∈ . We will further say that pseudo-cycle blocks position if ∈ . We will need one more result from [22]. Recall that here we index permutations from 0, while in [22], they are indexed from 1.
Then is a nice position. 0 c a 0 7 a c 7
In this section we will give a stricter characterization of nice positions via a subset of all possible pseudo-cycles. We need some new definitions.
Definition 1. Let be a pseudo-cycle, = left ∪ right. If left = ∅ then is called right-only,
if right = ∅ then is called left-only. If left ̸= ∅, then we refer to = max left as the boundary
of . A right-only pseudo-cycle is called minimal if no proper subset is a cycle.
Example 1. Consider the word cbccabaa. The pseudo-cycle = {1, 2, 3, 6, 7}, with () =
{1, 2, 3, 6, 7} is a right-only pseudo-cycle with critical interval = [
with boundary .
Proof. If ⊆ ′ or ′ ⊆ , then the statement is trivial. Else, we have to show that (1) ∈ ∩ ′, and (2) if ∈ ∩ ′ then − 1 ∈ ( ∩ ′) if ≤ , and ∈ ( ∩ ′) if > . (1) follows from the fact that both and ′ have boundary . Ad (2): Let ∈ ∩ ′, ≤ . Since is a pseudo-cycle with boundary , it follows that − 1( − 1) ∈ . Similarly, since ′ is a pseudo-cycle with boundary , − 1( − 1) ∈ ′, thus − 1( − 1) ∈ ∩ ′. Now let ∈ ∩ ′, > . Then it follows that − 1() ∈ and − 1() ∈ ′, thus − 1() ∈ ∩ ′.
Note that not every is the boundary of some pseudo-cycle. But with Lemma 2, we can now define a unique pseudo-cycle for each which is.
Definition 2. Let 0 ≤ ≤ − 1. A pseudo-cycle = left ∪ right, with left ̸= ∅ is called -essential if is the boundary of and every pseudo-cycle ′ with boundary is a superset of . A pseudo-cycle is called essential if it is -essential for some .
Clearly, for every , there exists at most one -essential pseudo-cycle. This implies that altogether there are at most − 2 essential pseudo-cycles.
Example 2. Consider again the word cbccabaa. = {3, 7}, with () = {2, 7} is the
3essential pseudo-cycle with critical interval = [
Proposition 1. Given an -essential pseudo-cycle , its critical interval is maximal w.r.t. the boundary . In other words, if ′ is a pseudo-cycle with the same boundary , then ′ ⊆ . Proof. Follows immediately from Lemma 2.
Corollary 1. Let be a word. Then equals the union of critical intervals of those pseudo-cycles which are either minimal right-only or essential. 3.1. Algorithm In this section we will describe an alternative algorithm for finding all nice positions of a given word . Even though this algorithm is slower than the one in [22], it is of interest due to its greater informativeness w.r.t. pseudo-cycles. The algorithm takes advantage of Corollary 1. This is useful from a computational point of view, as can be deduced from the next lemma. Lemma 3. The set of essential pseudo-cycles can be exponentially smaller than the complete set of pseudo-cycles.
Proof. Let = b⌈/2⌉a⌊/2⌋, thus || = . The total number of pseudo-cycles is 2|| = 2⌊/2⌋, since every subset of the index set of containing at least one a and excluding the first b is a pseudo-cycle with left and right not empty. On the other hand, there are only ⌊/2⌋ essential pseudo-cycles, namely sets of the form = {, ⌊/2⌋ + } for ∈ {1, 2, 3, . . . , ⌊/2⌋}.
From Cor. 1 we know that it sufices to compute right-only pseudo-cycles and essential pseudo-cycles to identify nice positions of a word. However, our experiments show that on 98% of words with 0 nice positions, all positions are blocked by left-only and right-only pseudo-cycles (data not shown). Based on experimental evidence from [22] we know that a large fraction of words have 0 nice positions: e.g. for binary words of length = 20, around 65% of words have 0 nice positions, while over a ternary alphabet, 61% of words of length 20 have 0 nice positions. Since right-only and left-only pseudo-cycles can be computed in linear time, our algorithm does this as a first step (Phase 1 and Phase 2). Only if at this point there are still positions which have not been blocked does it proceed to computing essential pseudo-cycles (Phase 3).
We next give a description of the three phases of the algorithm.
Phase 1 consists in computing the cycle decomposition of , since the cycles of the permutation are exactly the minimal right-only pseudo-cycles.
Phase 2 starts with a filtering step: It removes from the index set all indices which cannot be part of any left-only pseudo-cycle. The idea is that 0 cannot be part of a left-only pseudo-cycle because, since then − 1 would be in the image of the pseudo-cycle. This cannot happen because both the pseudo-cycle and its image must be a subset of the set of indices {0, 1, . . . , − 1}. By using on 0 we have the information that (0) + 1 must not be in the pseudo-cycle itself, because otherwise it would imply also the previous statement. If we continue to apply iteratively we can block every index connected to 0, avoiding them in the following operations.
Algorithm 1: Pseudo-cycles finder
Input: Word
Output: Set of right-only, left-only, and essential pseudo-cycles 1 ← | | 2 ← () 3 − 1 ← ( ) 4 setRight ← ℎ ( ) // cycle decomposition 5 setLeft ← (, − 1) // compute left-only pseudo-cycles 6 if || = + 1 then // if contains all indices, exit 7 return setRight ∪ setLeft 8 setEss ← (, − 1) // compute -essential pseudo-cycles 9 return setRight ∪ setLeft ∪ setEss With the remaining set of indices the left-only pseudo-cycles are built. We use a procedure resembling the cycle decomposition of the standard permutation. Starting from position , we traverse the permutation and we insert () + 1 in . From this index we continue until we loop back to the starting index , namely we build a “shifted” cycle. This procedure is repeated until no indices are left to create disjoint left-only pseudo-cycles.
Phase 3 computes -essential pseudo-cycles which have a non-empty right part, since essential pseudo-cycles which are left-only have already been computed in Phase 2. Let be the set of indices for which such a pseudo-cycle has already been computed. For each > 0, ̸∈ , the algorithm computes the unique -essential pseudo-cycle, if it exists. During this step, the algorithm traverses the permutation iteratively starting from = − 1( − 1) and using this trajectory: ← ⎧⎪abort ⎪ ⎪ ⎪⎨ − 1( − 1) if = 0 if < i ⎪ − 1() if > i ⎪ ⎪ ⎪⎩stop - ps.-c. closed if = i
The algorithm inserts the indices that it touches either in left (if the index is on the left of the boundary) or in right (if the index is on the right of the boundary). It stops either because it returns to the starting point (boundary) during the traversal of the permutation or because it fails the construction of such pseudo-cycle, ending up in position 0 (which cannot be part of left, otherwise we would have -1 in ()). An example of the construction of -essential pseudo-cycles can be seen in Figure 2.
Proposition 2. Algorithm 1 outputs exactly the essential pseudo-cycles and the minimal right-only pseudo-cycles of the input word. Therefore, the algorithm computes all pseudo-cycles which are necessary to identify all nice positions.
Proposition 3. Algorithm 1 runs in (2) time.
The following example shows that this bound is tight: In fact, there is an infinite number of words on which the algorithm takes Θ(2) time. The reason is that the running time of Phase (1) 0 b 3 is proportional to the sum of the lengths of the essential pseudo-cycles of the input word. E.g. for = 2 and = 20, consider = bbaaaaaaaaabbbbbbbba: the sum of the sizes of the essential pseudo-cycles of is 302. We can produce such example words for every even length by adding an a and a b, respectively, to the first run of a’s and to the second run of b’s.
In this section, we present properties of nice positions in fully clustered words. Recall that a fully clustered word is one which has one run per character, such as cccabb. We will study these questions for diferent alphabets, where we restrict our attention to words s.t. alph() = Σ, i.e. words in which every character appears at least once. We are interested in the number ℎ() of nice positions of a word , and in the number of words () which have nice positions, for given length .
As an example, for = 2, there are 10 fully clustered words of length 6, 6 of which have 1 nice position, 2 have 2 nice positions, and 2 have 3 (see Table 1). Of the 60 fully clustered words for = 3, 5 have 0 nice positions, 26 have 1, 16 have 2, and 13 have 3 (data not shown).
First we gather some useful properties using pseudo-cycles: Lemma 4. Let be any word and its standard permutation. The following hold: 1. If − 1 is a fixpoint, then no < is nice.
word abbbbb aabbbb aaabbb aaaabb aaaaab
2. If (1) = 0, then no > 1 is nice. 3. is nice if and only if has no left-only pseudo-cycle.
4. 0 is not nice.
Proof. 1. If ( − 1) is a fixpoint, then { − 1} is a right-only pseudo-cycle, so it blocks all elements from 0 to − 1. 2. If (1) = 0, then {1} is a left-only pseudo-cycle, blocking any > 1. 3. If is nice, then it cannot be in the critical interval of any pseudo-cycle. But the pseudo-cycles whose critical interval contains are exactly the left-only pseudo-cycles, since if there is a non-empty right part, then its minimum must be smaller than . 4. The entire set {0, . . . , − 1} is a right-only pseudo-cycle, so its minimum 0 blocks all ≤ 0. Lemma 5. Let be any word, || = . If is the identity permutation, then ℎ() = 1. In particular, is the only nice position.
Proof. = (0)(1) · · · ( − 1) (in cycle representation), consisting of fixpoints. Since − 1 is a fixpoint, by Lemma 4, no < can be nice. Clearly, has no left-only pseudo-cycles, so again by Lemma 4, is nice.
Since the standard permutation of any word over a unary alphabet is the identity permutation, these words have exactly one nice position: Corollary 2. If is a word over an alphabet of size = 1, then ℎ() = 1. 4.1. Number of Nice Positions over Alphabet Size 2 Our first result says that every fully clustered word over a binary alphabet has at least one nice position.
Proposition 4. If begins with an a, then ℎ() = 1. If begins with a b then ℎ() ≥ 1. Proof. First, let = ab− , for some 1 ≤ ≤ − 1. Then = , thus, by Lemma 5, there is exactly one nice position, namely .
Now let = ba− , for some 1 ≤ ≤ − 1. It is known that a word of this form is the BWT of a standard word, or of a power of a standard word [20], with the first case if gcd(, − ) = 1. By the result of Likhomanov and Shur [21], the number of cycles of equals the greatest common divisor of the runlengths, namely = gcd(, − ). By Lemma 1 then, is nice. Proposition 5. Let = ba− 1. Then ℎ() = 1.
Proof. The standard permutation of is = (0, − 1, − 2, . . . , 2, 1), in cycle notation. By Lemma 1, 1 is nice, since has one cycle. 0 is not nice by Lemma 4. Every > 0 is a singleton left-only pseudo-cycle, since () = − 1, while all other pseudo-cycles are subsets of {1, . . . , − 1}, and thus left-only. Every left-only pseudo-cycle {} is -essential, blocking [ + 1, ], i.e. the only position which is nice is 1 (Fig. 3).
0
b
a
0
0
b
4
a
a
4
a
5
5
a
6
a
(a) 1 = {0, 1, 2, 3, 4, 5, 6},
(1) = {0, 1, 2, 3, 4, 5, 6}, 1 = [0, 0].
(b) 2 = {1}, (2) = {0}, 2 = [
Proposition 7. Let = b+1a . Then ℎ() = 2, in particular, 1 and are nice. Proof. First, since is a BWT, the number of cycles of is nice, by Lemma 1. Since the runlengths and + 1 are relatively prime, = 1, so 1 is nice. Let 0 < ≤ . The -essential pseudo-cycle is = {, + }, since () = + and () = + − ( + 1) = − 1. The critical interval of is = [ + 1, + ]. The union of these critical intervals is [2, − 1] ⊆ , since = || = 2 + 1. Finally, no -essential pseudo-cycles exist for > . Therefore, there are no left-only pseudo-cycles, and thus, by Lemma 4, is nice (see Figure 4). 4.2. Number of Words with Nice Positions over Alphabet Size 2 We now turn to the number of words with nice positions.
Definition 3. For > 0, ≥ 0, let () denote the number of fully clustered words with exactly nice positions over an alphabet of size .
From Prop. 4 it follows that 2(0) = 0, and from Prop. 4 and 5 it follows that 2(1) ≥ , since the − 1 words beginning with a and the word ba− 1 have 1 nice position. For a better understanding of the words with nice positions, we ran experiments on fully clustered words up to length 100, and studied their pseudo-cycles. These led to the following conjectures: 0 b Conjecture 1. For all , 2(1) = .
Conjecture 2. For even, ≥ 8, 2(2) = 0. For odd, 2(2) = 1.
Conjecture 3. For every , 2(⌈ 2 ⌉) = 2.
The two words with ⌈/2⌉ nice positions are bba− 2 and b− 1a. This is because both have ⌊/2⌋ pseudo-cycles whose critical intervals contain exactly one position each. From [22], we know that for words that are BWT images, the parity of nice positions is the same as the parity of the number of cycles. In these two cases, the pseudo-cycles block every position which have the opposite parity, leaving all the remaining positions available.
All our conjectures are confirmed by the histograms we produced for words up to length 100 and nice positions, up to 19 (data not shown). Furthermore, the words show a regular behaviour with distinct ’s. In particular, we can see that the 8 longest words (4 of even length, 4 of odd length) are disconnected from all the others. Moreover, the greater , the farther this group of 8 words is from the others. The first where this group is visible is = 6, and we identify the 4 words of even length as follows: two primitive words (1 = b7a13, 2 = b15a7), two power words (3 = b14a6, 4 = b8a14); and the 4 primitive words of odd length (5 = b8a15, 6 = b16a7, 7 = b9a16, 8 = b17a8).
These words give an idea of the regularity of 2() across diferent . Consider 1 = b7a13, and the same word with 4 more a’s and 2 more b’s, namely 1′ = b9a17. In both cases there are |1|b − 1 number of pseudo-cycles which have the same form, and starting from the one with the smallest boundary, they are shifted by one position to the right. Moreover, the critical interval of each of these pseudo-cycles has length |1| − 1 (in total they cover 2 · | 1| − 1 positions). On the other hand, there are |1|− 2·|21|− 1 additional pseudo-cycles blocking just one position each, e.g. 5 and 7 in resp. ′. For this reason, ℎ(1) = |1| − |1|− 2·|21|− 1 − 2 · | 1| − 1 and ℎ(1′) = |1′| − |1′|− 2·|21′|− 1 − 2 · | 1′| − 1, and therefore ℎ(1′) = ℎ(1) + 1. We observed this phenomenon holds adding iteratively the same number of a’s and b’s (up to length 100). Further, the same happens adding 2 b’s and 4 a’s to 4, 5, 7, and adding 4 b’s and 2 a’s to 2, 3, 6, 8. Our experiments suggest that for fixed , there are no words with greater length then those above, see Table 2. On the basis of these observations, we conjecture that the set ℱ 2() of binary words with nice positions is finite. Formally:
has exactly nice positions.
Finally, we noticed from our experiments that the smallest nice position is always a divisor of . Let divide . As we have seen before, = ba is the BWT of a word with a standard word and = gcd(, ) [20]. Thus is nice by Lemma 1. The standard permutation of has cycles, and the largest minimum of a cycle is − 1, blocking all positions ≤ − 1. Thus, given , where is a divisor of , e.g. the word ba( − 1) has smallest nice position . We conjecture that the converse is true also: Conjecture 5. An integer can occur as a smallest nice position for some fully clustered word of length if and only if divides .
In this paper we continued the study of a combinatorial problem introduced in [22]: which are the positions where a dollar can be inserted into a word to make it a BWT (so-called nice positions). We strengthened the characterization via pseudo-cycles of nice positions given there. Pseudo-cycles are particular subsets of the indices; here we showed that a much smaller subset of pseudo-cycles sufices to characterize the set of nice positions of a word.
We further presented an algorithm that returns the smallest set of pseudo-cycles needed to identify all nice positions of the input word, and using this algorithm, we studied nice positions of fully clustered words over a binary alphabet. We presented properties on the number of nice positions for distinct fully clustered words, and we gave some conjectures on the number of words with fixed number of nice positions, for which we have experimental evidence.
As future work we are planning to extend the study to larger alphabets. We already have extensive experimental data for = 3, and plan to prove related properties as for the binary alphabet. For example, w.r.t. Conj. 4 we could characterize a consistent phenomenon we observe in the histograms for the ternary alphabets. For ≥ 3 we reach a plateau after a certain length, which we believe to be strongly related to the conjectured . Moreover the words appearing in this plateau seem to be consisting of only two types, namely ac bℓ and cb aℓ. [18] I. M. Gessel, A. Restivo, C. Reutenauer, A bijection between words and multisets of necklaces, European Journal of Combinatorics 33 (2012) 1537–1546. [19] J. W. Daykin, R. Groult, Y. Guesnet, T. Lecroq, A. Lefebvre, M. Léonard, É. Prieur-Gaston, A survey of string orderings and their application to the Burrows–Wheeler transform, Theoretical Computer Science 710 (2018) 52–65. [20] S. Mantaci, A. Restivo, M. Sciortino, Burrows–Wheeler transform and Sturmian words,
Information Processing Letters 86 (2003) 241–246. [21] K. M. Likhomanov, A. M. Shur, Two Combinatorial Criteria for BWT Images, in: Proceeding of the 6th International Computer Science Symposium in Russia (CSR 2011), 2011, pp. 385–396. [22] S. Giuliani, Zs. Lipták, F. Masillo, R. Rizzi, When a dollar makes a BWT, Theoretical
Computer Science 857 (2021) 123–146. [23] J. Simpson, S. J. Puglisi, Words with simple Burrows-Wheeler Transforms, Electronic
Journal of Combinatorics 15 (2008). [24] A. Restivo, G. Rosone, Burrows-Wheeler transform and palindromic richness, Theor.
Comput. Sci. 410 (2009) 3018–3026. [25] A. Restivo, G. Rosone, Balancing and clustering of words in the Burrows–Wheeler transform, Theoretical Computer Science 412 (2011) 3019–3032. [26] S. Ferenczi, L. Q. Zamboni, Clustering words and interval exchanges, Journal of Integer
Sequences 16 (2013) 3. [27] M. Bóna, Combinatorics of Permutations, Second Edition, Discrete mathematics and its applications, CRC Press, 2012.