Recognition of Whitehead-Minimal Elements in Free Groups of Large Ranks - Artificial Intelligence and Symbolic Computation - page 213

is called the Minimization Problem for F , it is one of the principal problems
in combinatorial group theory and topology. There is a famous Whitehead's
decision algorithm for the Minimization Problem, it is based on the following
result due to Whitehead ([11]): if a word w

∈ F ( X ) is not minimal then there

exists an automorphism t . Unfortunately, its

complexity depends on cardinality of Ω ( X ) which is exponential in the rank of
F ( X ). We refer to [6] for a detailed discussion on complexity of Whitehead's
algorithms.
In this paper we focus on the Recognition Problem for minimal elements in
F . It follows immediately from the Whitehead's result that w

∈ Ω ( X ) such that | t ( w ) | < | w |

∈ F is minimal if

and only if Ω ( X ) (such elements sometimes are called

Whitehead's minimal ). This gives one a simple deterministic decision algorithm
for the Recognition Problem, which is of exponential time complexity in the rank
of F . Note, that the worst case in terms of the rank occur when the input word w
is already minimal. In this situation all of the Whitehead automorphisms Ω ( X )
have to be applied.
Construction of a probabilistic classifier which recognizes words of minimal
length allows one to solve the recognition problem quickly in expense of a small
classification error. Such classifier can be used as a fast minimality check heuristic
in a deterministic algorithm which solves the minimization problem.
It is convenient to consider the Minimization Problem only for cyclically
reduced words in F .Aword w = x 1 ...x n ∈

| t ( w ) |≥| w | for every t ∈

X ± 1 )is cyclically

F ( X )( x i ∈

= x − 1
n

reduced if x 1 . Clearly, every w ∈ F can be presented in the form w =

u − 1

wu for some u ∈ F ( X ) and a cyclically reduced element w ∈ F ( X ) such that

| w is unique and it is called a cyclically reduced form of w .

Every minimal word in F is cyclically reduced, therefore, it suces to construct
a classifier only for cyclically reduced words in F .

w | = | w | +2 | u | .This

3 Recognition of Minimal Words in Free Groups

One of the main applications of Pattern Recognition techniques is classification
of a variety of given objects into categories. Usually classification algorithms
or classifiers use a set of measurements (properties, characteristics) of objects,
called features , which gives a descriptive representation for the objects. We refer
to [2] for detailed introduction to pattern recognition techniques.
In this section we describe a particular pattern recognition system PR MIN
for recognizing minimal elements in free groups. The corresponding classifier
is a supervised learning classifier which means that the decision algorithm is
“trained” on a prearranged dataset, called training dataset in which each pattern
is labelled with its true class label. The algorithm is based on Support Vector
Machines (SVM) classification algorithm.
In Section 1 we have stressed that the number of parameters required to
be estimated by the classification model based on quadratic regression is of
order O( n 4 ), where n is the rank of a free group F n . This constitutes two main
problems. First, in order to compute the parameters we have to multiply and