Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 10/2014

О.Н. БИРЮКОВ

ЭФФЕКТИВНЫЙ АЛГОРИТМ РАСПОЗНАВАНИЯ ТИПА КОСЫ ПО НИЛЬСЕНУ-ТЕРСТОНУ В ГРУППЕ $B_3$

Государственное автономное образовательное учреждение высшего профессионального образования ``Московский государственный областной социально-гуманитарный институт'', РОССИЯ, 140410, Московская область, Коломна, ул. Зеленая, 30 oleg_biryukov@mail.ru

This preprint was accepted Jule 29, 2014

АННОТАЦИЯ:
Рассматривается группа кос и е\"е гомоморфизм в группу 
гомеотопий компактной ориентированной  двумерной поверхности рода нуль. 
В соответствии с классификацией гомеотопий по 
Нильсену-Т\"ерстону различают периодические, 
псевдоаносовские и приводимые косы. 
В статье описывается эффективный алгоритм распознавания 
типа косы по классификации Нильсена-Т\"ерстона в группе кос $B_3$. 
Алгоритм имеет линейную сложность по длине входного слова.

Ключевые слова: группа кос, классификация Нильсена-Т\"ерстона

O. N. Biryukov

Effective algorithm for recognition of Nielsen-Thurston type of braid in the group $B_3$

ABSTRACT:
The braid group and its homomorphism in the group of homeotopies of
compact oriented two-dimensional surface of zero genus are studied.
There are periodic, pseudo-Anosov and reducible braids as provided
by the Nielsen-Thurston classification. In this paper an effective
algorithm for recognition of Nielsen-Thurston type of braid in the
group $B_3$ is described. The algorithm has linear complexity on the
length of input word.

 
Key words:  braid group, Nielsen-Thurston classification


[Full text:
 Preprint in Russian (.pdf.gz)]







Back to all preprints


Back to the Steklov
Institute of Mathematics at St.Petersburg