A Hybrid Search Algorithm for the Whitehead Minimization Problem
| dc.creator | Myasnikov, A. D. | |
| dc.creator | Haralick, R. M | |
| dc.date | 2006-04-09 | |
| dc.date.accessioned | 2026-07-07T07:10:42Z | |
| dc.date.available | 2026-07-07T07:10:42Z | |
| dc.description | The Whitehead Minimization problem is a problem of finding elements of the minimal length in the automorphic orbit of a given element of a free group. The classical algorithm of Whitehead that solves the problem depends exponentially on the group rank. Moreover, it can be easily shown that exponential blowout occurs when a word of minimal length has been reached and, therefore, is inevitable except for some trivial cases. In this paper we introduce a deterministic Hybrid search algorithm and its stochastic variation for solving the Whitehead minimization problem. Both algorithms use search heuristics that allow one to find a length-reducing automorphism in polynomial time on most inputs and significantly improve the reduction procedure. The stochastic version of the algorithm employs a probabilistic system that decides in polynomial time whether or not a word is minimal. The stochastic algorithm is very robust. It has never happened that a non-minimal element has been claimed to be minimal. | |
| dc.identifier | https://arxiv.org/abs/math/0604206 | |
| dc.identifier | http://arxiv.org/abs/math/0604206 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/111503 | |
| dc.subject | Group Theory | |
| dc.subject | Probability | |
| dc.title | A Hybrid Search Algorithm for the Whitehead Minimization Problem | |
| dc.type | text |