Eraser morphisms and membership problem in groups and monoids

Abstract

We develop the theory of fragile words by introducing the concept of eraser morphism and extending the concept to more general contexts such as (free) inverse monoids. We characterize the image of the eraser morphism in the free group case, and show that it has decidable membership problem. We establish several algorithmic properties of the class of finite-$\mathcal{J}$-above (inverse) monoids. We prove that the image of the eraser morphism in the free inverse monoid case (and more generally, in the finite-$\mathcal{J}$-above case) has decidable membership problem, and relate its kernel to the free group fragile words.

Communicated by Scott Thomas Chapman

Keywords:

• Eraser morphism
• fragile words
• groups
• inverse monoids

2010 Mathematics Subject Classification:

• 20F10
• 20M18
• 20M35
• 68R15

Acknowledgments

We would like to thank Enric Ventura for helpful conversations in which he conjectured that Theorem 4.4 holds, and Montse Casals-Ruiz for pointing out the reference [5] which allowed us to prove Theorem 4.5.

Correction Statement

This article has been republished with minor changes. These changes do not impact the academic content of the article.

Additional information

Funding

The first author thanks Austrian Science Fund project FWF P29355-N35. The third author was partially supported by CMUP (UID/MAT/00144/2019), which is funded by FCT (Portugal) with national (MCTES) and European structural funds through the programs FEDER, under the partnership agreement PT2020. The last author was supported by the ERC Grant 336983, by the Basque Government grant IT974-16, by the grant MTM2017-86802-P of the Ministerio de Economia y Competitividad of Spain, by the grant 346300 for IMPAN from the Simons Foundation and the matching 2015-2019 Polish MNiSW fund, and by “Native towns,” a social investment program of PJSC “Gazprom Neft.”