Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
14 Downloads (Pure)

Abstract

We prove the following results: (1) There is a one-relator inverse monoid Inv⟨A|w=1⟩ with undecidable word problem; and (2) There are one-relator groups with undecidable submonoid membership problem. The second of these results is proved by showing that for any finite forest the associated right-angled Artin group embeds into a one-relator group. Combining this with a result of Lohrey and Steinberg (J Algebra 320(2):728–755, 2008), we use this to prove that there is a one-relator group containing a fixed finitely generated submonoid in which the membership problem is undecidable. To prove (1) a new construction is introduced which uses the one-relator group and submonoid in which membership is undecidable from (2) to construct a one-relator inverse monoid Inv⟨A|w=1⟩ with undecidable word problem. Furthermore, this method allows the construction of an E-unitary one-relator inverse monoid of this form with undecidable word problem. The results in this paper answer a problem originally posed by Margolis et al. (in: Semigroups and their applications, Reidel, Dordrecht, pp. 99–110, 1987).

Original languageEnglish
Pages (from-to)987-1008
Number of pages22
JournalInventiones Mathematicae
Volume219
Issue number3
Early online date9 Sep 2019
DOIs
Publication statusPublished - Mar 2020

Keywords

  • 20F05
  • 20F10
  • 20F36
  • 20M05
  • 20M18
  • FREE-PRODUCTS
  • IDENTITY PROBLEM

Cite this