A hybrid search algorithm for the Whitehead Minimization problem
| Autor: | Alexey D. Myasnikov, Robert M. Haralick |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Discrete mathematics
Algebra and Number Theory Rank (linear algebra) Group (mathematics) Probability (math.PR) Probabilistic logic Automorphism problem Group Theory (math.GR) Heuristic search Free groups Computational Mathematics Search algorithm Free group FOS: Mathematics Heuristics Time complexity Mathematics - Group Theory Word (computer architecture) Mathematics - Probability Mathematics |
| Zdroj: | Journal of Symbolic Computation. (7):818-834 |
| ISSN: | 0747-7171 |
| DOI: | 10.1016/j.jsc.2006.04.001 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|