|
|
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
November 23, 2021 18:30, Moscow, Steklov Mathematical Institute
|
|
|
|
|
|
Complexity of the word problem in HNN-extensions
Markus Lohrey Universität Siegen
|
Number of views: |
This page: | 109 |
|
Abstract:
In the talk I will consider the computational complexity of the word problem in HNN-extensions.
Already for simple cases, the complexity is open. For instance, it is not known whether the
word problem for an HNN-extension of a free group with finitely generated associated subgroups
can be solved in polynomial time. On the other hand, for a Baumslag Solitar group BS(p,q) the
word problem is known to be solvable in polynomial time (even in logarithmic space by a result of Armin
Weiß). One just has to do Britton reduction and thereby store exponents of powers in binary encoding. I will
generalize this result as follows: the word problem for an HNN-extension of a hyperbolic group
with cyclic associated subgroups can be solved in polynomial time. This result directly generalizes
to fundamental groups of graphs of groups with hyperbolic vertex groups and cyclic edge groups.
* для получения пароля Zoom-трансляции напишите Алексею Таламбуце (altal@mi-ras.ru) |
|