2 papers
math.GR2008
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…
cs.LO2008
Automatic structures of bounded degree revisited
Dietrich Kuske, Markus Lohrey
The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We p…