| RUS ENG |
| Full version |
|
|
|
| SEMINARS |
|
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
|
|||
|
|
|||
|
Complexity of the word problem in HNN-extensions Markus Lohrey Universität Siegen |
|||
|
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) |
|||