Compressed word problems in HNN-extensions and amalgamated products

2008/11/20 by Niko Haubold, Haubold, Niko, Markus Lohrey +1 · 1 citation
Computer Science · #semigroups and automata theory #Algorithms and Data Compression #Cellular Automata and Applications

paper · pdf · doi:10.48550/arxiv.0811.3303

Abstract

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 problem for H. An analogous result for amalgamated free products is shown as well.

Cited by

• HNN extensions of free groups with equal associated subgroups of finite index: polynomial time word problem

Related

• Complexity of word problems for HNN-extensions
• The compressed word problem in relatively hyperbolic groups
• Compressed words and automorphisms in fully residually free groups
• Polynomial-time word problems
• Hilbert space compression for free products and HNN-extensions