A hybrid search algorithm for the Whitehead minimization problem.

DOI10.1016/J.JSC.2006.04.001MaRDI QIDQ2457368zbMATH OpenOpenAlexFDO

Authors Alexei D. Miasnikov, Robert Haralick

Publication date 23 October 2007

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0604206

zbMATH Keywords

automorphic orbitsautomorphism problemelements of minimal lengthfree groupsheuristic search algorithmshybrid search algorithmslength-reducing automorphismsWhitehead minimization problem

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to group theory (20-04) Free nonabelian groups (20E05) Automorphisms of infinite groups (20E36) Generators, relations, and presentations of groups (20F05) Symbolic computation and algebraic computation (68W30)

Abstract: 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.

Recommendations

• Heuristics for the Whitehead Minimization Problem
• ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
• scientific article; zbMATH DE number 2144698
• Pattern recognition and minimal words in free groups of rank 2
• On the genericity of Whitehead minimality

Cites work

• A public key system with signature and master key functions
• Artificial Intelligence and Symbolic Computation
• Automorphic orbits in free groups.
• Clusters, Currents, and Whitehead's Algorithm
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Heuristics for the Whitehead Minimization Problem
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 2144698 (Why is no real title available?)
• scientific article; zbMATH DE number 2144699 (Why is no real title available?)
• scientific article; zbMATH DE number 2144700 (Why is no real title available?)
• On equivalent sets of elements in a free group
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• The subadditive ergodic theorem and generic stretching factors for free group automorphisms.
• What does a basis of F(a,b) look like?

Cited in

(4)

• Counting words of minimum length in an automorphic orbit.
• Heuristics for the Whitehead Minimization Problem
• ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
• scientific article; zbMATH DE number 2144698 (Why is no real title available?)

This page was built for publication: A hybrid search algorithm for the Whitehead minimization problem.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2457368)