The subject of this thesis is the algorithmic solution to various decision problems in the braid groups.
In chapter 1, we introduce the notion of braids and important decision problems of the braid groups.
In chapter 2, we introduce the band-generator presentation and study the semigroup of positive words in this presentation. Then we give an algorithmic solution to the word problem using this new presentation. Our algorithm is faster than the classical algorithm using Artin's presentation.
In chapter 3, we solve the conjugacy problem by an algorithm which is parallel to the prior works of Garside, Thurston and Elrifai-Morton. Moreover we improve the cycling theorem, which is one of two main theorems for the conjguacy problem, for both of Artin's presentation and the band generator presentation.
In chapter 4, it is proved that there is a polynomial time algorithm for the conjugacy problem of the 4-braid group, after analyzing the structure of the reduced super summit set.
In chapter 5, we solve the shortest word problem in the 4-braid group and show that the closure of a positive 4-braid bounds a Bennequin surface. And we give an example which shows that the Bennequin theorem cannot be generalized to all of the 4-braids.
In chapter 6, we classify all conjugacy classes of 3-braids that are related by flype operations. Among them we determine which conjugacy classes have representatives that admit both (+) and (-) flypes as an effort to search for a potential example of a pair of transversal knots that are topologically isotopic and have the same Bennequin number but are not transversally isotopic.
본 논문에서는 땋임 군의 여러 가지 판별문제들에 대한 구현가능한 해에 대해서 연구한다.
1장에서는 땋임 군을 소개하고, 중요한 판별문제들에 대해서 알아본다.
2장에서는 땋임 군의 띠-생성자 표현을 소개하고 이 군 표현의 양의단어들로 이루어진 반군의 구조를 연구한다. 또한 이 새로운 군 표현을 이용하여 땋임 군에서의 단어문제를 푸는 알고리듬을 만들고, 이 알고리듬이 그 동안 연구되었던 아틴 표현을 이용한 알고리듬보다 더 빠르다는 것을 보인다.
3장에서는 가사이드, 써스톤, 엘리파이-모튼 등이 아틴 표현을 사용하여 만든 땋임 군의 공액문제에 대한 이론을 띠-생성자 표현을 사용해서도 전개할 수 있음을 보인다. 또한 공액문제를 푸는 가장 중요한 두 정리 중 하나인 순환정리를 아틴 표현과 띠-생성자 표현 모두에 대해 개선한다.
4장에서는 축약된 최정상집합의 구조를 연구한 뒤 4-땋임 군에서는 공액문제를 다항식 시간에 풀 수 있음을 보인다.
5장에서는 최소단어문제를 4-땋임 군에 대해서 풀고, 양의 4-땋임에 닿는 변환을 해서 얻어지는 고리는 Bennequin 곡면의 경계가 됨을 보인다. 또한 Bennequin 정리가 4-땋임 군 전체에 대해서는 성립하지 않는 예가 있음을 보인다.
6장에서는 flype 변환으로 서로 바꿀 수 있는 3-땋임의 공액류들을 분류한다. 이들 중 (+)과 (-) flype 변환을 모두 적용할 수 있는 공액류들에 대해서도 알아본다.
