# Computing Maximal Lyndon Substrings of a String
## 4 The Algorithm _Bsla_
### The Refinement
(_Note that before the removal of \(H\) from \(gr(j_{\ell,k})\), the index \(i^{\prime}\) was not eligible to be considered for \(prev(i)\) as \(i\) and \(i^{\prime}\) were both from the same group._)  
Theorem 3.1 shows that having a \(t\)-complete group configuration \(\langle G_{k},...,G_{t+1},G_{t},...,G_{1}\rangle\) and refining it by \(G_{t}\), then the resulting system of groups is a \((t+1)\)-complete group configuration. This allows carrying out the refinement in an iterative fashion. Theorem 3.2: _Let \(Conf=\langle G_{k},...,G_{t+1},G_{t},...,G_{1}\rangle\) be a \(t\)-complete group configuration, \(1\leq t\). After performing the refinement of Conf by group \(G_{t}\), the resulting system of groups denoted as \(Conf^{\prime}\) is a \((t+1)\)-complete group configuration._  
Proof. : We carry the proof in a series of claims. The symbols \(gr()\), \(con()\), \(\mathcal{C}()\), \(prev()\), and \(val()\) denote the functions for \(Conf\), while \(gr^{\prime}()\), \(con^{\prime}()\), \(c^{\prime}()\), \(prev^{\prime}()\), and \(val^{\prime}()\) denote the functions for \(Conf^{\prime}\). When a group \(G_{t+1}\) is partitioned, a part of it is moved as the next group in the list, and we call it \(H_{t+1}\); thus, \(G_{t+1}\prec H_{t+1}\prec G_{t}\). For details, please see (\(R_{3}\)) above. Claim 1: \(Conf^{\prime}\) _is a group configuration_, _i.e._, \((C_{1})\), \((C_{2})\), \((C_{3})\), and \((C_{4})\) for \(Conf^{\prime}\) hold. Proof of Claim 1.: \((C_{1})\) and \((C_{2})\) follow from the fact that the process is a refinement, i.e., a group is either preserved as is or is partitioned into two or more groups. The doubling of the contexts in Step \((R_{3})\) guarantees that the increasing order of the contexts is preserved, i.e., \((C_{3})\) holds. For any \(j\in G_{t}\) so that \(j=prev(i)\
eq nil\), \(con(gr(prev(j)))\) is [PERSON], and \(con(gr(j))\) is also [PERSON], while \(con(gr(prev(j)))\prec con(gr(j))\), so \(con(gr(prev(j)))con(gr(j))^{val(j)}\) is [PERSON] as well; thus, \((C_{4})\) holds. _To illustrate the concatenation: let us call \(con(gr(prev(i)))\) as \(A\) and \(con(gr(j))\) as \(B\), and let \(val(j)=m\), then we know that \(A\) is [PERSON] and \(B\) is [PERSON] and \(A\prec B\); so, \(AB^{m}\) is clearly [PERSON] as if \(A\) and \(B\) were letters._  
This concludes the proof of Claim 1. Claim 2: \(\{\mathcal{C}^{\prime}(i)\mid i\in 1..n\}\) _is proper and has the Monge property_, _i.e._, \((C_{7})\) and \((C_{8})\) for \(Conf^{\prime}\) hold. Proof of Claim 2.: Consider \(\mathcal{C}^{\prime}(i)\) for some \(i\in 1..n\). There are two possibilities:  
1. \(\mathcal{C}^{\prime}(i)=\mathcal{C}(i)\) or
2. \(\mathcal{C}^{\prime}(i)=\mathcal{C}(i)\mathcal{C}(i_{1})...\mathcal{C}(i_{v})\), for some \(i_{1},i_{2},...,i_{v}\in G_{t}\), so that for any \(1\leq\ell\leq v\), \(i=prev(i_{\ell})\), \(\mathcal{C}(i_{\ell})=con(G_{t})\), \(v=val(i_{\ell})\) and for any \(1\leq\ell<k\) and \(i_{\ell+1}=i_{\ell}+|con(G_{t})|\). _Note that \(con(gr(i))\prec con(G_{t})\)._  
Consider \(\mathcal{C}^{\prime}(i)\) and \(\mathcal{C}^{\prime}(j)\) for some \(1\leq i<j\leq n\). 1. Case \(\mathcal{C}^{\prime}(i)=\mathcal{C}(i)\) and \(\mathcal{C}^{\prime}(j)=\mathcal{C}(j)\). 1. Show that \((C_{7}(a))\) holds. If \(\mathcal{C}^{\prime}(j)\subsetneq\mathcal{C}^{\prime}(i)\), then \(\mathcal{C}(j)\subsetneq\mathcal{C}(i)\), and so, by \((C_{7}(a))\) for \(Conf\), \(con(G_{t})\prec con(gr(j))\), and thus, \(con^{\prime}(H_{t+1})\prec con(G_{t})\prec con(gr(j))=con^{\prime}(gr^{ \prime}(j))\). Therefore, \((C_{7}(a))\) for \(Conf^{\prime}\) holds. Show that \((C_{\mathcal{S}})\) holds. If \(\mathcal{C}^{\prime}(i)\cap\mathcal{C}^{\prime}(j)\
eq\emptyset\), then \(\mathcal{C}(i)\cap\mathcal{C}(j)\
eq\emptyset\), so \(\mathcal{C}(j)\subseteq\mathcal{C}(i)\), and so, \(\mathcal{C}^{\prime}(j)\subseteq\mathcal{C}^{\prime}(i)\); so, \((C_{\mathcal{S}})\) for \(\mathit{Conf}^{\prime}\) holds. 2.