No Access

Quadratic normalization in monoids

Laboratoire de Mathématiques Nicolas Oresme, CNRS UMR 6139, Université de Caen, 14032 Caen, France

E-mail Address: patrick.dehornoy@unicaen.fr

Corresponding author.

and

INRIA πr2, Institut de Recherche en Informatique Fondamentale, CNRS UMR 8243, Université Paris 7, Case 7014, 75205 Paris Cedex 13, France

E-mail Address: yves.guiraud@pps.univ-paris-diderot.fr

Search for more papers by this author

https://doi.org/10.1142/S0218196716500399Cited by:5 (Source: Crossref)

Abstract

In the general context of presentations of monoids, we study normalization process that are determined by their restriction to length-two words. Garside’s greedy normal forms and quadratic convergent rewriting systems, in particular those associated with the plactic monoids, are typical examples. Having introduced a parameter, called the class and measuring the complexity of the normalization of length-three words, we analyze the normalization of longer words and describe a number of possible behaviors. We fully axiomatize normalizations of class $(4, 3)$ $(4, 3)$ , show the convergence of the associated rewriting systems, and characterize those deriving from a Garside family.

Communicated by S. Margolis

Keywords:

AMSC: 20M05, 68Q42, 20F10, 20F36, 18B40

References

1. S. I. Adyan, Fragments of the word Delta in a braid group, Mat. Zam. Acad. Sci. SSSR 36(1) (1984) 25–34; translated Math. Notes of the Acad. Sci. USSR 36(1) (1984) 505–510. Google Scholar
2. A. Bjorner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, Vol. 231 (Springer, Berlin, 2005). Google Scholar
3. L. Bokut, Y. Chen, W. Chen and J. Li, New approaches to plactic monoid via Gröbner–Shirshov bases, J. Algebra 423 (2015) 301–317. Web of Science, Google Scholar
4. A. Cain, R. Gray and A. Malheiro, Finite Gröbner–Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids, J. Algebra 423 (2015) 37–52. Web of Science, Google Scholar
5. A. Cain, R. Gray and A. Malheiro, Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids, Int. J. Algebra Comput. 25 (2015) 51–80. Link, Web of Science, Google Scholar
6. J. Cassaigne, M. Espie, D. Krob, J.-C. Novelli and F. Hivert, The Chinese monoid, Int. J. Algebra Comput. 11 (2001) 301–334. Link, Web of Science, Google Scholar
7. P. Dehornoy, Groupes de Garside, Ann. Sci. Éc. Norm. Supér. 35 (2002) 267–306. Web of Science, Google Scholar
8. P. Dehornoy and V. Gebhardt, Algorithms for Garside calculus, J. Symbolic Comput. 63 (2014) 68–116. Web of Science, Google Scholar
9. P. Dehornoy, M. Dyer and C. Hohlweg, Garside families in Artin-Tits monoids and low elements in Coxeter groups, Comptes-Rendus Math. 353 (2015) 403–408. Web of Science, Google Scholar
10. P. Dehornoy, with F. Digne, E. Godelle, D. Krammer, J. Michel, Foundations of Garside Theory, EMS Tracts in Mathematics, Vol. 22 (2015). Google Scholar
11. E. A. El-Rifai and H. R. Morton, Algorithms for positive braids, Quart. J. Math. Oxford 45(2) (1994) 479–497. Web of Science, Google Scholar
12. D. Epstein, with J. Cannon, D. Holt, S. Levy, M. Paterson and W. Thurston, Word Processing in Groups (Jones and Bartlett Publishers, Boston, 1992). Google Scholar
13. F. A. Garside, The braid group and other groups, Quart. J. Math. Oxford 20 (1969) 235–254. Web of Science, Google Scholar
14. S. Gaussent, Y. Guiraud and P. Malbos, Coherent presentations of Artin monoids, Compos. Math. 151 (2015) 957–998. Web of Science, Google Scholar
15. A. Hess, Factorable monoids: Resolutions and homology via discrete Morse theory, http://hss.ulb.uni-bonn.de/2012/2932/2932.pdf, 2012, PhD thesis. Google Scholar
16. A. Hess and V. Ozornova, Factorability, string rewriting and discrete Morse theory, arXiv:1412.3025. Google Scholar
17. M. Hoffmann and R. M. Thomas, A geometric characterization of automatic semigroups, Theoret. Comput. Sci. 369 (2006) 300–313. Web of Science, Google Scholar
18. D. Krammer, An asymmetric generalisation of Artin monoids, Groups Complex Cryptol. 5 (2013) 141–168. Google Scholar
19. V. Ozornova, Factorability, discrete Morse theory, and a reformulation of $K (π, 1)$ $K (π, 1)$ -conjecture, http://hss.ulb.uni-bonn.de/2013/3117/3117.pdf, 2013, PhD thesis. Google Scholar