Derivation- bounded groups
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...
- Autores:
-
Madlener, K.
Otto, F.
- Tipo de recurso:
- Article of journal
- Fecha de publicación:
- 1985
- Institución:
- Universidad Nacional de Colombia
- Repositorio:
- Universidad Nacional de Colombia
- Idioma:
- spa
- OAI Identifier:
- oai:repositorio.unal.edu.co:unal/48769
- Acceso en línea:
- https://repositorio.unal.edu.co/handle/unal/48769
http://bdigital.unal.edu.co/42226/
- Palabra clave:
- Problems
combinatorial properties
limits
set of algorithms
groups
- Rights
- openAccess
- License
- Atribución-NoComercial 4.0 Internacional
| 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. |
|---|