A Hybrid Search Algorithm for the Whitehead Minimization Problem

Details A Hybrid Search Algorithm for the Whitehead Minimization Problem A Hybrid Search Algorithm for the Whitehead Minimization Problem

2006-04-09

arxiv.org/abs/math/0604206v1

Mathematics

Group Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Hybrid Search Algorithm for the Whitehead Minimization Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Hybrid Search Algorithm for the Whitehead Minimization Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Hybrid Search Algorithm for the Whitehead Minimization Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-267782