On Dehn Functions of Finitely Presented Bi-Automatic Monoids
Friedrich Otto · 2000
For each automatic monoid the word problem can be solved in quadratic time Cambell et al. 1997), and hence, the Dehn function of a finitely presented automatic monoid is recursive. Here we show that this result on the Dehn function cannot be improved in general by presenting finitely presented bi-automatic monoids the Dehn functions of which realize arbitrary complexity classes that are sufficiently rich.