# Computing Maximal Lyndon Substrings of a String
## 3 \(\mathbf{\top}\)-Reduction Algorithm (Tkla)
### Properties Preserved by \(\mathbf{\Upsilon}\)-Reduction
Thus, \(\tau(x)[i_{1}..m]\prec\tau(x)[k_{1}..m]\) for any \(i_{1}<k_{1}\leq j_{1}\), and so, \(\tau(x)[i_{1}..j_{1}]\) is proto-Lyndon by Lemma 1. Now, let us assume that \(j\) is white. Then, \(j-1\) is black, and \(x[i..j-1]\) is proto-Lyndon, so as in the previous case, \(\tau(x)[t(i)..t(j-1)]\) is proto-Lyndon. Now, we can show that \(\tau\)-reduction preserves some right-maximal Lyndon substrings. Lemma 6: _Let \(x=x[1..n]\), and let \(\tau(x)=\tau(x)[1..m]\). Let \(1\leq i<j\leq n\). Let \(x[i..j]\) be a right-maximal Lyndon substring, and let \(i\) be a black position._  
\[\text{Then, } \begin{cases}\tau(x)[t(i)..t(j)]\text{ is a right-maximal Lyndon substring}&\text{if $j$ is black}\\ \tau(x)[t(i)..t(j-1)]\text{ is a right-maximal Lyndon substring}&\text{if $j$ is white.}\end{cases} \]  
Proof: Since \(x[i..j]\) is Lyndon and hence proto-Lyndon, by Lemma 5, we know that \(\tau(x)[t(i)..t(j)]\) is proto-Lyndon for \(j\) black, while for white \(j\), \(\tau(x)[t(i)..t(j-1)]\) is proto-Lyndon. Thus, in order to conclude that the respective strings are right-maximal Lyndon substrings, we only need to prove that the property \((c)\) of Lemma 1 holds in both cases. Since \(x[i..j]\) is right-maximal Lyndon, either \(j=n\) or \(x[j+1..n]\prec x[i..n]\) by Lemma 1, giving \(j=n\) or \(x[j+1]\preceq x[i]\). Since \(x[i..j]\) is Lyndon and hence unbordered, \(x[i]\prec x[j]\). Thus, either \(j=n\) or \(x[j+1]\preceq x[i]\prec x[j]\). If \(j=n\), then there are two simple cases. If \(n\) is white, \(n-1\) is black and \(m=t(n-1)\), so \(t(j-1)=m\), giving us (c) of Lemma 1 for \(\tau(x)[t(i)..t(j-1)]\). On the other hand, if \(n\) is black, then \(m=t(n)\), and so, \(m=t(j)\) giving us (c) of Lemma 1 for \(\tau(x)[t(i)..t(j)]\). Thus, in the following, we can assume that \(j<n\) and that \(x[j+1]\preceq x[i]\prec x[j]\). We will proceed by discussing two possible cases, one where \(j\) is black and the other where \(j\) is white. 1. Case: \(j\) is black. We need to show that either \(t(j)=m\) or \(\tau(x)[t(i)..m]\succ\tau(x)[t(j)+1..m]\). If \(j=n\), then \(t(j)=m\), and we are done. Thus, we can assume that \(j<n\). We must show that \(\tau(x)[t(j)+1..m]\prec\tau(x)[t(i)..m]\). Case: \(x[j+1]\preceq x[j+2]\). Then, \(x[j]\succ x[j+1]\) and \(x[j+1]\preceq x[j+2]\), and so, \(j+1\) is black. It follows that \(t(j)+1=t(j+1)\). By Lemma 4, \(\tau(x)[t(j+1)..m]\prec\tau(x)[t(i)..m]\) because \(x[j+1..n]\prec x[i..n]\), thus \(\tau(x)[t(j)+1..m]\prec\tau(x)[t(i)..m]\). (1b) Case: \(x[j+1]\succ x[j+2]\). Then, \(x[j]\succ x[i]\succeq x[j+1]\succ x[j+2]\). It follows that the \(\tau\)-pair \((j,j+1)\) is followed by a \(\tau\)-pair \((j+2,j+3)\), and thus, \(t(j)+1=t(j+2)\). Thus, \((x[j+2],x[j+3])\prec\mathfrak{(}x[i],x[i+1])\prec\mathfrak{(}x[j],x[j+1])\); hence, \(p(j+2,j+3)\prec p(i,i+1)\prec p(j,j+1)\). Since \(\tau(x)[t(j)+1]=p(j+2,j+3)\), \(\tau(x)[t(i)]=p(j,i+1)\), and \(\tau(x)[t(j)]=p(j,j+1)\), it follows that \(\tau(x)[t(j)+1]\prec\tau(x)[t(i)]\), and so, \(\tau(x)[t(j)+1..m]\prec\tau(x)[t(i)..m]\). (2) Case: \(j\) is white. We need to prove that \(\tau(x)[t(j-1)+1..m]\prec\tau(x)[t(i)..m]\). Since \(j\) is white, necessarily both \(j-1\) and \(j+1\) are black and \(t(j-1)+1=t(j+1)\). By Lemma 5, \(\tau(x)[t(i)..t(j-1)]\) is proto-Lyndon as both \(i\) and \(j-1\) are black and \(x[i..j-1]\) is proto-Lyndon. Since \(x[i..n]\succ x[j+1..n]\) and both \(i\) and \(j+1\) are black, by Lemma 4, we get \(\tau(x)[t(i)..m]\succ\tau(x)[t(j+1)..m]=\tau(x)[t(j-1)+1..m]\). \(\Box\)  
Now, we are ready to tackle the proof of Theorem 2. Proof of Theorem 2.: Let \(\mathcal{L}^{\prime}_{\mathbf{X}}[i]=j\) where \(i\) is black. Then, \(t(i)\) is defined, and \(x[i..j]\) is a right-maximal Lyndon substring of \(x\). We proceed by analysis of the two possible cases of the label for the position \(j\).