4 papers · 1 filter
Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
Laurent Bartholdi, Michael Figelius, Markus Lohrey +1
We give lower bounds on the complexity of the word problem of certain non-solvable groups: for a large class of non-solvable infinite groups, including in particular free groups, G…
The power word problem
Markus Lohrey, Armin Weiß
In this work we introduce a new succinct variant of the word problem in a finitely generated group , which we call the power word problem: the input word may contain powers $p^x…
The isomorphism problem for finite extensions of free groups is in PSPACE
Géraud Sénizergues, Armin Weiß
We present an algorithm for the following problem: given a context-free grammar for the word problem of a virtually free group , compute a finite graph of groups w…
On the dimension of matrix embeddings of torsion-free nilpotent groups
Funda Gul, Armin Weiß
Since the work of Jennings (1955), it is well-known that any finitely generated torsion-free nilpotent group can be embedded into unitriangular integer matrices for some…