On real-time word problems

by Derek Holt and Claas Röver

Keywords

word problems of groups, real-time languages

Abstract

We prove that the word problem of the direct product of two free groups of rank two can be recognised by a two-tape real-time but not by a one-tape real-time Turing machine. We also prove that the Baumslag-Solitar groups B(1,r) have 5-tape real-time word problem for all non-zero r.

This is published in J. London Math. Soc. (2) 67 (2003), no. 2, 289-301

Of course you can also ask me for a hard copy.