One-Relator Inverse Monoids with Decidable Word Problem Are Algorithmically Unclassifiable

Abstract: A classical result from Combinatorial Group Theory, the Adian-Rabin Theorem, states that there does not exist an algorithm which takes a finitely presented group G and decides whether G possesses a given Markov property. An example of such a property is having decidable word problem. Consequently, there is no algorithm that takes a finitely presented group and decides whether the group has decidable word problem. On the other hand, Magnus proved in the 1930s that every one-relator group has decidable word problem, so in the one-relator case such an algorithm (trivially) does exist.

In contrast, in 2019, Gray proved that there exists a one-relator inverse monoid with undecidable word problem. One key question arising from that work is whether it might be possible to classify the one-relator inverse monoids with decidable word problem. Related to this one can ask whether there is an algorithm that takes a one-relator inverse monoid as input and decides whether or not that one-relator inverse monoid has decidable word problem.

In this talk, I will show that there does not exist an algorithm which takes a one-relator inverse monoid M as input and decides whether M has decidable word problem. In other words, the one-relator inverse monoids with decidable word problem are algorithmically unclassifiable.

Mathematics

Audience: researchers in the topic

ANTLR seminar

Series comments: This is the Algebra, Number Theory, Logic and Representation theory seminar.