Lehrstuhl Mathematik & InformatikWord Problems for groups and contextfree recognition
Abstract. Lipton and Zalcstein have proved, that the word
problem for linear groups over a field with characteristic zero is solvable
in (deterministic) logspace [6]. One important conclusion was that the
word problem for free groups is solvable in logspace, since free groups
are representable as groups of matrices over \mathbb{Z}. In this paper
I like to pass some complementary remarks. First I prove that the word
problem for linear groups over a field with prime characteristic is solvable
in logspace. Secondly I analyze the time-complexity and compare the resulting
product-complexity with the optimal one.
References:
[6] Lipton and Zalcstein, Word Problems solvable
in logspace, Research Report #60, 1976.