Compressed word problems in HNN-extensions and amalgamated products

Niko Haubold, Markus Lohrey

It is shown that the compressed word problem for an HNN-extension with base group H and finite associated subgroups is polynomial time Turing-reducible to the compressed word probl…