서지주요정보
(A) fast algorithm to the conjugacy problem on generic braids = 일반적 땋임들의 공액문제에 대한 빠른 알고리즘
서명 / 저자 (A) fast algorithm to the conjugacy problem on generic braids = 일반적 땋임들의 공액문제에 대한 빠른 알고리즘 / Jang-Won Lee.
저자명 Lee, Jang-Won ; 이장원
발행사항 [대전 : 한국과학기술원, 2007].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8018021

소장위치/청구기호

학술문화관(문화관) 보존서고

DMA 07003

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

The subjects of this thesis are the algorithmic solution to the conjugacy problem on generic braids and the solution to the reducibility problem. In chapter 1, we introduce the conjugacy problem on braid groups and three dynamic types of braids. In chapter 2, We study random braids that are formed by multiplying randomly chosen permutation braids by analyzing their behavior under weighted decomposition and cycling. Using this analysis, we propose a polynomial-time algorithm to the conjugacy problem that is successful for random braids in overwhelming probability. As either the braid index or the number of permutation-braid factors increases, the success probability converges to 1 and so, contrary to the common belief, the distribution of hard instances for the conjugacy problem is getting sparser. We also show that some power of a pseudo-Anosov braid is always cyclically weighted up to cycling and we also give upper bounds for the necessary exponent and the necessary number of iterated cyclings. In chapter 3, We propose an algorithm for deciding the dynamic type of a given braid. The algorithm is based on Garside's weighted decomposition and is polynomial-time in the word-length of an input braid. Moreover a reduction system of circles can be found if the input is a certain type of reducible braids.

본 논문은 일반적 땋임의 공액 문제에 대한 해와 땋임의 동역학 종류에 대한 판별 문제의 해에 관해서 연구한다. 1장에서는 땋임 군을 중요한 개념들을 소개한다. 그리고 공액 문제와 그것의 해를 주는 중요한 공액 불변 집합들을 소개하고 그것들의 중요한 성질에 대해서 알아본다. 그리고 닐슨-서스턴 곡면사상으로서의 땋임의 동역학 종류를 소개한다. 2장에서는 무작위로 선택된 순열 땋임의 곱으로 만들어진 일반적 땋임의 가중 분해와 순환 연산에 대해 분석한다. 그리고 이 분석을 이용하여 압도적인 확률로 일반적 땋임의 공액 문제의 올바른 해를 주는 다항시간 알고리즘을 소개한다. 이 알고리즘은 땋임 지수와 순열 땋임의 수가 증가할수록 공액 문제의 올바른 해를 구할 확률이 땋임 지수와 순열 땋임의 수가 증가할수록 1에 가까워짐을 보인다. 또한, 유사-아노소프 땋임은 땋임의 적당한 제곱과 반복적인 순환 연산을 통하여 항상 순환 가중형태가 됨을 보인다. 그리고 그것들의 상한을 제시한다. 3장에서는 땋임의 동역학 종류에 대한 판별 문제의 해를 주는 다항시간 알고리즘을 제안한다. 가사이드의 가중 분해에 기반을 둔 이 알고리즘은 땋임의 단어 길이에 대하여 다항 시간임을 보인다.

서지기타정보

서지기타정보
청구기호 {DMA 07003
형태사항 v, 39 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 이장원
지도교수의 영문표기 : Ki-Hyoung Ko
지도교수의 한글표기 : 고기형
학위논문 학위논문(박사) - 한국과학기술원 : 수학전공,
서지주기 Reference : p. 37-39
주제 braid
conjugacy problem
reducibility problem
땋임
공액 문제
땋임동역학 판별 문제
QR CODE qr code