Given a group defined by a presentation with a single defining relation $w=1$, the prefix membership problem asks whether there is an algorithm for deciding membership in the submonoid of the group generated by the prefixes of the word $w$. Motivation for studying this problem comes from results of Ivanov, Margolis and Meakin (2001) who proved that, if $w$ is cyclically reduced, then a positive solution to the prefix membership problem for the group implies that the one-relator inverse monoid with the same presentation has decidable word problem. In this talk I will present some joint work with Igor Dolinka on the prefix membership problem for one-relator groups. I will explain two new approaches to the problem arising from our work. The first allows us to solve the prefix membership problem for certain examples that are low in the Magnus–Moldavanski hierarchy. The second approach is a method that goes via the groups of units of one-relator inverse monoids. I will explain these two approaches and show how they can be applied to solve the prefix membership problem in certain cases.

Date and Venue

Start Date
Venue
Online Zoom meeting
End Date

Speaker

Robert Gray

Speaker's Institution

University of East Anglia

Files

Area

Semigroups, Automata and Languages

Financiamento