The compressed word problem in groups

Add to your list(s) Download to your calendar using vCal

• Derek Holt, Warwick
• Tuesday 26 November 2019, 16:00-17:00
• Watson Building, Lecture Room C.

If you have a question about this talk, please contact Chris Parker.

Let G be a finitely generated group. The word problem WP(G) of G is the problem of deciding whether a given word w over the elements of some finite generating set and (their inverses) of G represents the identity element of G. It was proved in the 1950s that there are groups with unsolvable word problem, but for groups with solvable word problem, it is interesting both in theory and in practice to study the time and space complexity of WP(G) as a function of the length of the input word w. Many of the groups that arise in geometric group theory, including nilpotent groups, hyperbolic groups, Coxeter groups, Artin groups, braid groups, and mapping class groups are known to have word problem solvable in low degree polynomial time (usually linear or quadratic).

For the compressed word problem CWP , words are input in compressed form as straight line programs or, equivalently, as context-free grammars. For some words, such as powers of generators, the uncompressed word can be exponentially longer than its compressed version. So the complexity of CWP could conceivably be exponentially greater than WP(G). As motivation for studying this question, we observe that it is can be shown that the ordinary word problem in finitely generated subgroups of Aut(G) is polynomial time reducible to CWP .

It turns out that for some classes of (finitely generated) groups in which WP(G) is solvable in polynomial time, including nilpotent groups, Coxeter groups, and right-angled Artin groups, CWP is also solvable in polynomial time, whereas for others, such as the wreath product of a nonabelian finite group by an infinite cyclic group, CWP has been proved to be NP-hard.

In this talk, we will discuss a (fairly) recent result of Lohrey and Schleimer that, for hyperbolic groups G, CWP is solvable in polynomial time, and speculate on whether this result can be extended to include groups that are hyperbolic relative to a collection of abelian subgroups.

This talk is part of the Algebra seminar series.

This talk is included in these lists:

• Algebra seminar
• School of Mathematics events
• Watson Building, Lecture Room C

Note that ex-directory lists are not shown.