Heuristics for the Whitehead Minimization Problem

DOI10.1080/10586458.2005.10128906MaRDI QIDQ3418622zbMATH OpenOpenAlexFDO

Authors Robert Haralick, Alexei D. Miasnikov, Alexei Myasnikov

Publication date 5 February 2007

Published in Experimental Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0604204, https://eudml.org/doc/53072

automorphic orbits automorphism problem elements of minimal length free generating sets free groups heuristic algorithms minimization problem probabilistic algorithms reduced words Whitehead algorithm Whitehead method

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Automorphisms of infinite groups (20E36) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Abstract: In this paper we discuss several heuristic strategies which allow one to solve the Whitehead's minimization problem much faster (on most inputs) than the classical Whitehead algorithm. The mere fact that these strategies work in practice leads to several interesting mathematical conjectures. In particular, we conjecture that the length of most non-minimal elements in a free group can be reduced by a Nielsen automorphism which can be identified by inspecting the structure of the corresponding Whitehead Graph.

Recommendations

Cited in

(4)

This page was built for publication: Heuristics for the Whitehead Minimization Problem

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