Factorizing the Brauer monoid in polynomial time
<|reference_start|>Factorizing the Brauer monoid in polynomial time: Finding a minimal factorization for a generic semigroup can be done by using the Froidure-Pin Algorithm, which is not feasible for semigroups of large sizes. On the other hand, if we restrict our attention to just a particular semigroup, we could leverage its structure to obtain a much faster algorithm. In particular, $\mathcal{O}(N^2)$ algorithms are known for factorizing the Symmetric group $S_N$ and the Temperley-Lieb monoid $\mathcal{T}\mathcal{L}_N$, but none for their superset the Brauer monoid $\mathcal{B}_{N}$. In this paper we hence propose a $\mathcal{O}(N^4)$ factorization algorithm for $\mathcal{B}_{N}$. At each iteration, the algorithm rewrites the input $X \in \mathcal{B}_{N}$ as $X = X' \circ p_i$ such that $\ell(X') = \ell(X) - 1$, where $p_i$ is a factor for $X$ and $\ell$ is a length function that returns the minimal number of factors needed to generate $X$.<|reference_end|>
@article{marchei2024factorizing,
    title={Factorizing the Brauer monoid in polynomial time},
    author={Daniele Marchei, Emanuela Merelli, Andrew Francis},
    journal={arXiv preprint arXiv:2402.07874},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07874},
    primaryClass={math.RA cs.DS}
}