Pseudo-natural algorithms for finitely generated presentations of monoids and groups (Q1115973)

Many problems in algebra (e.g. word problems) and formal language theory (e.g. derivability-membership in r.e. languages) ask whether a certain word can be produced by insertions and/or deletions of words from a given set (relators or productions). Usually there is a ``natural strategy'' to solve the problem, i.e. an exhaustive search through all possible derivations. In some cases the problems are naturally structured to allow efficient search procedures (e.g. small cancellation theory in Combinatorial Group Theory, the CKY algorithm for membership in context- free languages). Based on these observations, the authors consider pseudonatural algorithms for word problems of finitely generated groups and monoids in the Grzegorczyk hierarchy \(\{E_ n:\) \(n\geq 1\}\). The best pseudonatural algorithms can yield complexities arbitrarily far from the inherent complexity of the problem itself in the hierarchy. Thus the authors restrict the usual notion of derivation to strong derivation where only insertions of trivial relators are allowed. They prove that the resulting notion of strong derivational complexity of a word (the length of the shortest strong derivation) realizes optimal algorithms in a Grzegorczyk class. Theorem 3.5. Let \(n\geq 1\). For each finitely generated group G with an \(E_ n\)-decidable word problem, there exists a finitely generated presentation \(<\Sigma;L>\) satisfying the following two conditions: (i) the set L of defining relators is \(E_ 1\) decidable (hence context-sensitive); (ii) The strong derivational complexity of \(<\Sigma;L>\) is bounded above by a function in the class \(E_ n\). Examples are shown to exist of such presentations (with tight bound n) where the derivational complexity has a tight derivational complexity in \(E_ m\) with predetermined gap m (even from a context-free presentation). A similar statement for context-free relators is false since only finitely presented groups have context-free sets of defining relators. Similar results for monoids in place of groups are obtained, although the question remains open whether there exist monoids for which context-free presentations of the same complexity are not possible.