UDC 512.54: 004.021
DOI: 10.36871/2618-9976.2021.02.001
Authors
Dobrynina Irina Vasilyevna
Doctor of Physical and Mathematical Sciences, Associate Professor, Professor of the Department
of Higher Mathematics, The Civil Defence Academy of the Ministry of the Russian Federation
for Civil Defence, Emergencies and Elimination of Consequences of Natural Disasters, Khimki,, Russia
Turenova Elena Lvovna
Candidate of Physical and Mathematical Sciences, Associate Professor, Associate Professor
of the Department of Higher Mathematics, The Civil Defence Academy of the Ministry of the Russian
Federation for Civil Defence, Emergencies and Elimination of Consequences of Natural Disasters,
Khimki, Russia
Abstract
The main algorithmic problems of combinatorial group theory
posed by M. Den and G. Titze at the beginning of the twentieth
century are the problems of word, word conjugacy and of group
isomorphism. However, these problems, as follows from the results
of P.S. Novikov and S.I. Adyan, turned out to be unsolvable
in the class of finitely defined groups.
Therefore, algorithmic problems began to be considered in specific
classes of groups. The word conjugacy problem allows for two
generalizations. On the one hand, we consider the problem of conjugacy
of subgroups, that is, the problem of constructing an algorithm
that allows for any two finitely generated subgroups to determine
whether they are conjugate or not. On the other hand, the
problem of generalized conjugacy of words is posed, that is, the
problem of constructing an algorithm that allows for any two finite
sets of words to determine whether they are conjugated or
not. Combining both of these generalizations into one, we obtain
the problem of generalized conjugacy of subgroups.
Coxeter groups were introduced in the 30s of the last century,
and the problems of equality and conjugacy of words are algorithmically
solvable in them. To solve other algorithmic problems,
various subclasses are distinguished. This is partly due
to the unsolvability in Coxeter groups of another important
problem – the problem of occurrence, that is, the problem of the
existence of an algorithm that allows for any word and any finitely
generated subgroup of a certain group to determine
whether this word belongs to this subgroup or not. The paper
proves the algorithmic solvability of the problem of generalized
conjugacy of subgroups in Coxeter groups with a tree structure.
Keywords
Algorithmic problem
Algorithm
Coxeter group
Tree structure
Conjugacy
Subgroup
