10 citations · 34 across the 21 of their papers we have counts for
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…
An Automaton Group with PSPACE-Complete Word Problem
Jan Philipp Wächter, Armin Weiß
We construct an automaton group with a PSPACE-complete word problem, proving a conjecture due to Steinberg. Additionally, the constructed group has a provably more difficult, namel…
On the Average Case of MergeInsertion
Florian Stober, Armin Weiß
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of compa…
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…