Home » visits » Computations in small overlap monoids

Computations in small overlap monoids

For several days in June 2018, Mark Kambites (Manchester) visited James Mitchell in St Andrews, supported by the CoDiMa research visits programme. The visit allowed Mark Kambites and James Mitchell to discuss algorithms for performing computations in small overlap monoids. Efficient algorithms for various problems in this important class of finitely presented monoids were developed by Mark in a series of papers published between 2007 and 2011. The most basic of these (to solve the word problem) was implemented by Mark himself in the GAP SmallOverlap package in 2008. James and students have recently re-implemented this much more efficiently, and also begun to implement Mark’s other algorithms for more sophisticated tasks such as computing normal forms. However, they have encountered some problems with practical implementation of the algorithms in Mark’s papers. The visit allowed James to explain these issues, and Mark to clarify how some of the algorithms were supposed to function. In addition, the visit allowed Mark to attend the 28th NBSAN meeting, which provided a valuable opportunity for discussions with other experts in the field.