Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
5 декабря 2022 г. 18:30, г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Контур Толк
 


The Dehn functions of a class of one-relation monoids

Carl-Fredrik Nyberg-Brodda

Université Gustave Eiffel
Видеозаписи:
MP4 180.3 Mb

Количество просмотров:
Эта страница:167
Видеофайлы:40



Аннотация: 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.

Язык доклада: английский
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024