= Recursive area bounds and the word problem
A <finite group presentation> has a recursive upper bound on its <Dehn function> exactly when its <word problem for a group> is decidable. If the maximal <relator> length is $\ell$ and a word has length $n$, a diagram of area at most $N$ can be chosen with at most $\ell N+n$ edges. Enumerating all finite labelled planar diagrams within that bound gives a terminating test. Conversely, a word decider identifies the finitely many null words of length at most $n$; exhaustive finite diagram searches find their minimal areas, whose maximum computes the <Dehn function>.
Back to article page
