Information Technology Reference
In-Depth Information
of the classification system, including generation of training datasets and feature
representation of elements in a free group. In the section we describe evaluation
procedure and give empirical results on the performance of the system.
2
Whitehead's Minimization Problem
In this section we give a brief introduction to the Whitehead minimization prob-
lem.
Let
X
be a finite alphabet,
X
−
1
x
−
1
=
{
|
x
∈
X
}
be the set of formal
inverses of letters from
X
,and
X
±
1
=
X
X
−
1
. For a word
w
in the alphabet
∪
X
±
1
we denote the length of
w
.Aword
w
is called
reduced
if it does
not contain subwords of the type
xx
−
1
by
|
w
|
or
x
−
1
x
for
x
∈
X
. Applying reduction
rules
xx
−
1
ε, x
−
1
x
ε
(where
ε
is the empty word) one can reduce each
word
w
in the alphabet
X
±
1
to a reduced word
w
.Theword
w
is uniquely
defined and does not depend on the order in a particular sequence of reductions.
The set
F
=
F
(
X
) of all reduced words over
X
±
1
→
→
forms a group with respect
to multiplication defined by
u
·
v
=
uv
(i.e., to compute the product of words
u, v
F
one has to concatenate them and then reduce). The group
F
with
the multiplication defined as above is called a
free
∈
group with
basis
X
.The
cardinality
is called the
rank
of
F
(
X
). Free groups play a central role in
modern algebra and topology.
A bijection
φ
:
F
|
X
|
→
F
is called an
automorphism
of
F
if
φ
(
uv
)=
φ
(
u
)
φ
(
v
)for
every
u, v
F
.Theset
Aut
(
F
) of all automorphisms of
F
forms a group with
respect to composition of automorphisms. Every automorphism
φ
∈
Aut
(
F
)
is completely determined by its images on elements from the basis
X
since
φ
(
x
1
...x
n
)=
φ
(
x
1
)
...φ
(
x
n
)and
φ
(
x
−
1
)=
φ
(
x
)
−
1
for any letters
x
i
,x
i
∈
∈
X
±
1
.
An automorphism
t
Aut
(
F
(
X
)) is called a
Whitehead's automorphism
if
t
satisfies one of the two conditions below:
∈
1)
t
permutes elements in
X
±
1
;
2)
t
fixes a given element
a
X
±
1
X
±
1
,x
=
a
±
1
∈
and maps each element
x
∈
to one of the elements
x
,
xa
,
a
−
1
x
,or
a
−
1
xa
.
By
Ω
(
X
) we denote the set of all Whitehead's automorphisms of
F
(
X
). It is
known [8] that every automorphism from
Aut
(
F
) is a product of finitely many
Whitehead's automorphisms.
The automorphic orbit
Orb
(
w
)ofaword
w
∈
F
is the set of all automorphic
images of
w
in
F
:
Orb
(
w
)=
{
v
∈
F
|∃
ϕ
∈
Aut
(
F
)
such that ϕ
(
w
)=
v
}
.
Aword
w
∈
F
is called
minimal
(or
automorphically minimal
)if
|
w
|≤|
ϕ
(
w
)
|
for
any
ϕ
Aut
(
F
). By
w
min
we denote a word of minimal length in
Orb
(
w
). Notice
that
w
min
is not unique. By
WC
(
w
) (the
Whitehead's complexity
of
w
)wedenote
a minimal number of automorphisms
t
1
,...,t
m
∈
∈
Ω
(
X
) such that
t
m
...t
1
(
w
)=
w
min
. The algorithmic problem which requires finding
w
min
for a given
w
∈
F
Search WWH ::
Custom Search