Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




Seminars "Proof Theory" and "Logic Online Seminar"
December 5, 2022 18:30, Moscow, Steklov Mathematical Institute (8 Gubkina), room 313 + Zoom
 


The Dehn functions of a class of one-relation monoids

Carl-Fredrik Nyberg-Brodda

Université Gustave Eiffel
Video records:
MP4 180.3 Mb

Number of views:
This page:136
Video files:30



Abstract: The Dehn function for a semigroup or group $M$ is an asymptotic measure of how bad the "naive solution" to the word problem in $M$ may be. The word problem in $M$ is decidable if and only if the Dehn function of $M$ is a recursive function, but frequently the Dehn function is significantly more poorly behaved than the complexity of the word problem. On the other hand, the word problem for one-relation monoids is one of the most intriguing and important open problems in semigroup theory. For that reason, it makes sense to ask: how bad can the Dehn function of a one-relation monoid be? I will present the history of the problem, which has a natural starting point in S. I. Adian's classical theory of left cycle-free monoids. I will then present some of my own recent progress on this topic for the class of one-relation monoids where the relation is of the form $bUa = a$, for a word $U$. In particular, I will exhibit monoids with Dehn functions of exponential growth in this class, answering a question posed by Cain & Maltcev in 2013.

Language: English
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024