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 and a word has length , a diagram of area at most can be chosen with at most 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 ; exhaustive finite diagram searches find their minimal areas, whose maximum computes the Dehn function.
Articles by others on the same topic
There are currently no matching articles.