BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Algebra seminar
SUMMARY:The compressed word problem in groups - Derek Holt
\, Warwick
DTSTART:20191126T160000Z
DTEND:20191126T170000Z
UID:TALK3883AT
URL:/talk/index/3883
DESCRIPTION:Let G be a finitely generated group. The word prob
lem WP(G) of G is the problem of deciding whether
a given word w over the elements of some finite ge
nerating set and (their inverses) of G represents
the identity element of G. It was proved in the 19
50s that there are groups with unsolvable\nword pr
oblem\, 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) a
s a function of the length of the input word w. Ma
ny of the groups that arise\nin geometric group th
eory\, including nilpotent groups\, hyperbolic gro
ups\, Coxeter groups\, Artin groups\, braid groups
\, and mapping class groups are known to have word
problem solvable in low degree polynomial time (u
sually linear or quadratic).\n\nFor the compressed
word problem CWP(G)\, words are input in compress
ed form as straight line programs or\, equivalentl
y\, as context-free grammars. For some words\, suc
h as powers of generators\, the uncompressed word
can be exponentially longer than its compressed ve
rsion. So the complexity of CWP(G) could conceivab
ly be exponentially greater than WP(G). As motivat
ion for studying this question\, we observe that i
t is can be shown that the ordinary word problem i
n finitely generated subgroups of Aut(G) is polyno
mial time reducible to CWP(G).\n\nIt turns out tha
t for some classes of (finitely generated) groups
in which WP(G) is solvable in polynomial time\, in
cluding nilpotent groups\, Coxeter groups\, and ri
ght-angled Artin groups\, CWP(G) 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(G) has been proved
to be NP-hard.\n\nIn this talk\, we will discuss
a (fairly) recent result of Lohrey and Schleimer t
hat\, for hyperbolic groups G\, CWP(G) is solvable
in polynomial time\, and speculate on whether thi
s result can be extended to include groups that ar
e\nhyperbolic relative to a collection of abelian
subgroups.\n
LOCATION:Watson Building\, Lecture Room C
CONTACT:Chris Parker
END:VEVENT
END:VCALENDAR