Eraser morphisms and membership problem in groups and monoids

2019/10/04 by Daniele D’Angeli, D'Angeli, Daniele, Emanuele Rodaro +5
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1910.02134

openalex publication_date 2019/10/04 · openalex created_date 2019/10/10 · openalex updated_date 2026/07/28

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-\calJ-above (inverse) monoids. We prove that the image of the eraser morphism in the free inverse monoid case (and more generally, in the finite-\calJ-above case) has decidable membership problem, and relate its kernel to the free group fragile words.

Related

• Asymptotic properties of free monoid morphisms
• The word problem of finitely presented special inverse monoids via their groups of units
• On the submonoid membership problem for HNN extensions of free groups
• New results on the prefix membership problem for one-relator groups
• Reset thresholds of transformation monoids