# Computing Maximal Lyndon Substrings of a String
## 3 \(\mathbf{\top}\)-Reduction Algorithm (Tkla)
### \(\mathbf{\Upsilon}\)-Reduction  
For each \(\tau\)-pair \((i,i+1)\), we consider the pair of alphabet symbols \((\mathbf{x}[i],\mathbf{x}[i+1])\). We call them _symbol \(\mathbf{\tau}\)-pairs_. They are in a total order \(\vartriangleleft\) induced by \(\prec:(\mathbf{x}[i_{j}],\mathbf{x}[i_{j}+1])\vartriangleleft\mathbf{x}[i_{\ell}],\mathbf{x}[i _{\ell}+1])\) if either \(\mathbf{x}[i_{j}]\prec\mathbf{x}[i_{\ell}]\), or \(\mathbf{x}[i_{j}]=\mathbf{x}[i_{\ell}]\) and \(\mathbf{x}[i_{j}+1]\prec\mathbf{x}[i_{\ell}+1]\). They are sorted using the radix sort with a key of size two and assigned letters from a chosen \(\tau\)-alphabet that is a subset of \(\{0,1,...,\tau(\mathbf{x})|\}\) so that the assignment preserves the order. Since the input string is over an integer alphabet, the radix sort is linear.  
In the example (Figure 2), the \(\tau\)-pairs are \((1,2)(3,4)(4,5)(6,7)(7,8)(9,10)\), and so, the symbol \(\tau\)-pairs are \((0,1)(1,0)(0,2)(3,1)(1,2)(2,\$). The sorted symbol \(\tau\)-pairs are \((0,1)(0,2)(1,0)\)\((1,2)(2,\$)(3,1)\). Thus, we chose as our \(\tau\)-alphabet \(\{0,1,2,3,4,5\}\), and so, the symbol \(\tau\)-pairs are assigned these letters: \((0,1)\to 0\), \((0,2)\to 1\), \((1,0)\to 2\), \((1,2)\to 3\), \((2,\$)\to 4\), and \((3,1)\to 5\). Note that the assignments respect the order \(\vartriangleleft\) of the symbols \(\tau\)-pairs and the natural order \(<\) of \(\{0,1,2,3,4,5\}\).  
The \(\tau\)-letters are substituted for the symbol \(\tau\)-pairs, and the resulting string is terminated with \(\$\). This string is called the _\(\mathbf{\tau}\)-reduction_ of \(\mathbf{x}\) and denoted \(\mathbf{\tau}(\mathbf{x})\), and it is a \(\$\)-terminated string over an integer alphabet. For our running example from Figure 2, \(\tau(\mathbf{x})=021534\). The next lemma justifies calling the above transformation a reduction.  
Figure 2: Illustration of the \(\tau\)-reduction of a string **011023122**. The rounded rectangles indicate symbol \(\tau\)-pairs; the ovals indicate the \(\tau\)-pairs. below are the colour labels of the positions; at the bottom is the \(\tau\)-reduction.  
**Lemma 3**.: _For any string \(\mathbf{x}\), \(\frac{1}{2}|\mathbf{x}|\leq|\tau(\mathbf{x})|\leq\frac{2}{3}|\mathbf{x}|\)._  
Proof.: There are two extreme cases; the first is when all the \(\tau\)-pairs do not overlap at all, then \(|\tau(\mathbf{x})|=\frac{1}{2}|\mathbf{x}|\); and the second is when all the \(\tau\)-pairs overlap, then \(|\tau(\mathbf{x})|=\frac{2}{3}|\mathbf{x}|\). Any other case must be in between.  
Let \(\mathcal{B}(\mathbf{x})\) denote the set of all black positions of \(\mathbf{x}\). For any \(i\in 1..|\tau(\mathbf{x})|\), \(b(i)=j\) where \(j\) is a black position in \(\mathbf{x}\) of the \(\tau\)-pair corresponding to the new symbol in \(\tau(\mathbf{x})\) at position \(i\), while \(t(j)\) assigns each black position of \(\mathbf{x}\) the position in \(\tau(\mathbf{x})\) where the corresponding new symbol is, i.e., \(b(t(j))=j\) and \(t(b(i))=i\). Thus,  
\[1..|\tau(\mathbf{x})|\overset{\text{\tiny{$\mathrm{b}$}}}{\underset{\mathsf{t}}{ \rightleftarrows}}\mathcal{B}(\mathbf{x})\]  
In addition, we define \(p\) as the mapping of the \(\tau\)-pairs to the \(\tau\)-alphabet.  
In our running example from Figure 2, \(t(1)=1\), \(t(3)=2\), \(t(4)=3\), \(t(6)=4\), \(t(7)=5\), and \(t(9)=6\), while \(b(1)=1\), \(b(2)=3\), \(b(3)=4\), \(b(4)=6\), \(b(5)=7\), and \(b(6)=9\). For the letter mapping, we get \(p(1,2)=0\), \(p(3,4)=2\), \(p(4,5)=1\), \(p(6,7)=5\), \(p(7,8)=3\), and \(p(9,10)=4\).