## Derivation- bounded groups

##### Type

**Artículo de revista**

##### Document language

**Español**

##### Publication Date

**1985**

##### Metadata

Show full item record##### Summary

For some problems which are defined by combinatorial properties good complexity bounds cannot be found because the combinatorial point of view restricts the set of solution algorithms. In this paper we present a phenomenon of this type with the classical word problem for finitely presented groups. A presentation of a group is called En-derivation-bounded (En-d.b.), if a function kϵEn exists which bounds the derivations of the words defining the unit element. For En-d.b. presentations a pure combinatorial En-algorithm for solving the word problem exists. It is proved that the property of being En-d.b. is an invariant of finite presentations, but that the degree of complexity of the pure combinatorial algorithm may be as far as posible from the degree of complexity of the word problem itself.##### Keywords

##### Collections

This work is licensed under a Creative Commons Reconocimiento-NoComercial 4.0.This document has been deposited by the author (s) under the following

**certificate of deposit**