(A) fast algorithm to the conjugacy problem on generic braids = 일반적 땋임들의 공액문제에 대한 빠른 알고리즘

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 319
  • Download : 0
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.
Advisors
Ko, Ki-Hyoungresearcher고기형researcher
Description
한국과학기술원 : 수학전공,
Publisher
한국과학기술원
Issue Date
2007
Identifier
263459/325007  / 020025229
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 수학전공, 2007.2, [ v, 39 p. ]

Keywords

땋임동역학 판별 문제; 땋임; reducibility problem; conjugacy problem; braid; 공액 문제

URI
http://hdl.handle.net/10203/41891
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=263459&flag=dissertation
Appears in Collection
MA-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0