od - 谷聖一研究室

ブレイド群のband generatorを
用いた標準形を構成する
アルゴリズムの実装
谷研究室
冨士英恵
目次
１．はじめに
２．背景
３．ブレイドの様々な定義
４．Javaにおける実装
５．今後の課題
１．はじめに
ブレイドとは(定義)
 2つの平行な平面に接続したn本の紐から
なる集合
 左側から1つの紐をたどっていくと必ず右
側につく
１．はじめに
ブレイドとは(定義)
 2つの平行な平面に接続したn本の紐から
なる集合
 左側から1つの紐をたどっていくと必ず右
側につく
１．はじめに
同値関係
 V,Wが同値
Vの端点を固定し、紐を出さずに上下関係
を維持したまま動かしWに一致させること
が出来る時
１．はじめに
同値関係
 V,Wが同値
Vの端点を固定し、紐を出さずに上下関係
を維持したまま動かしWに一致させること
が出来る時
V
W
１．はじめに
定義(積)
 任意のブレイドＶ,Ｗの積VWとはVの右端
とＷの左端を繋げたもの
V
W
１．はじめに
定義(積)
 任意のブレイドＶ,Ｗの積VWとはVの右端
とＷの左端を繋げたもの
V
W
VW
２．背景
共役問題
 2つのブレイドV,Wが共役
∃α: V=αWα
-1
２．背景
共役問題
 2つのブレイドV,Wが共役
∃α: V=αWα
V
-1
W
２．背景
共役問題
 2つのブレイドV,Wが共役
∃α: V=αWα
V
-1
α
W
α
-1
２．背景
共役問題
 2つのブレイドV,Wが共役
-1
∃α: V=αWα
 与えられた2つのブレイドが共役かどうかを
判定する問題→共役問題
 共役問題は難しい→公開鍵暗号への利用
(K.H. Ko, S.J. Lee 等)
２．背景
共役問題
 2つのブレイドV,Wが共役
-1
∃α: V=αWα
 与えられた2つのブレイドが共役かどうかを
判定する問題→共役問題
 共役問題は難しい→公開鍵暗号への利用
標準形の利用
２．背景
標準形について
 ブレイド問題を考える上で一番基本となる
もの
 J.S. Birman,K.H. Ko,等によって標準形
構成アルゴリズムの提案
 田邉による上記アルゴリズムの改善
２．背景
標準形について
 ブレイド問題を考える上で一番基本となる
もの
 J.S. Birman,K.H. Ko,等によって標準形
構成アルゴリズムの提案
 田邉による上記アルゴリズムの改善
このアルゴリズムを実装
(j2sdk1.4.0_01)
３．ブレイドの様々な定義
定義(単位元)
 ブレイドの単位元e(1度も交差しないもの)
３．ブレイドの様々な定義
定義(σi)
 σiを
i と i+1 番目の紐を1度だけ入れ替え
たブレイド
4
3
2
1
３．ブレイドの様々な定義
定義(σi)
 σiを
i と i+1 番目の紐を1度だけ入れ替え
たブレイド
この時負の傾きを持
つ方が上に来る!!
σ1
4
3
2
1
３．ブレイドの様々な定義
定義(σi)
 σiを
i と i+1 番目の紐を1度だけ入れ替え
たブレイド
σ1 = a21と表記
4
3
2
1
３．ブレイドの様々な定義
定義(σi)
 σiを
i と i+1 番目の紐を1度だけ入れ替え
たブレイド
この時σ1の逆元
になっている!!
σ1
4
3
2
1
-1
３．ブレイドの様々な定義
定義(σi)
 σiを
i と i+1 番目の紐を1度だけ入れ替え
たブレイド
σ1
4
3
2
1
σ1
-1
３．ブレイドの様々な定義
band generatorとは
 複数の紐の交差を一まとめにした生成元
３．ブレイドの様々な定義
band generatorとは
 複数の紐の交差を一まとめにした生成元
a61
6
5
4
3
2
1
３．ブレイドの様々な定義
band generatorとは
 複数の紐の交差を一まとめにした生成元
a61 = (σ5 σ4 σ3 σ2 )σ1 (σ2 σ3 σ-14 σ5 -1)
6
5
4
3
2
1
-1
-1
３．ブレイドの様々な定義
band generatorとは
 複数の紐の交差を一まとめにした生成元
a61 = (σ5 σ4 σ3 σ2 )σ1 (σ2 σ3 σ-14 σ5 -1)
6
5
4
3
2
1
-1
-1
３．ブレイドの様々な定義
＋
定義(BBn)
 正ブレイド(aijにおいて、i>jが成り立つ)で作
られた集合
３．ブレイドの様々な定義
Braidの同値性に関する性質1
 atsarq≡arqats ((t-r)(t-q)(s-r)(s-q)>0)
３．ブレイドの様々な定義
Braidの同値性に関する性質1
 atsarq≡arqats ((t-r)(t-q)(s-r)(s-q)>0)
…
…
t
t
…
…
r
r
q
…
…
s
…
…
s
…
…
q
３．ブレイドの様々な定義
Braidの同値性に関する性質2
 atsasr≡atrats≡asratr (∀t,s,r(n≧t＞s＞r≧1))
３．ブレイドの様々な定義
Braidの同値性に関する性質2
 atsasr≡atrats≡asratr (∀t,s,r(n≧t＞s＞r≧1))
t
…
s
s
…
…
…
r
r
…
…
…
r
t
…
…
s
…
…
…
t
３．ブレイドの様々な定義
Braidの同値性に関する性質3
 at(t+1)as(s+1)≡as(s+1)at(t+1) (|t-s|>1)
３．ブレイドの様々な定義
Braidの同値性に関する性質3
 at(t+1)as(s+1)≡as(s+1)at(t+1) (|t-s|>1)
…
…
t
t
s
s
…
s+1
…
s+1
…
t+1
…
t+1
３．ブレイドの様々な定義
Braidの同値性に関する性質4
 as(s+1)a(s+1)(s+2) as(s+1)
≡a(s+1)(s+2)as(s+1)a(s+1)(s+2)
３．ブレイドの様々な定義
Braidの同値性に関する性質4
 as(s+1)a(s+1)(s+2) as(s+1)
≡a(s+1)(s+2)as(s+1)a(s+1)(s+2)
…
…
s+2
s+2
s+1
s+1
s
s
…
…
３．ブレイドの様々な定義
正同値
 これらの4つの性質を有限回適用させるこ
とによって得られるブレイド
３．ブレイドの様々な定義
Fundamental wordδの定義
 an(n-1)a(n-1)(n-2)・・・a21と正同値であるブレ
イド
３．ブレイドの様々な定義
Fundamental wordδの定義
 an(n-1)a(n-1)(n-2)・・・a21と正同値であるブレ
イド
３．ブレイドの様々な定義
≦の定義
 V,W:BBn
V≦W
V
+
(∃P1,P2∈BBn)[W=P1VP2]
W
３．ブレイドの様々な定義
≦の定義
 V,W:BBn
V≦W
P1
V
+
(∃P1,P2∈BBn)[W=P1VP2]
P2
W
３．ブレイドの様々な定義
[r,s]nの定義
+
r
 {W∈BBn|δ≦W≦δ
}
s
３．ブレイドの様々な定義
[r,s]nの定義
+
r
 {W∈BBn|δ≦W≦δ
δ
0
W
}
s
δ
1
３．ブレイドの様々な定義
Left-weightedの定義
 X∈[0,1]n
+
 P∈BBnに対してPの分割XAが任意のPの
X’A’に対してX’≦Xとなるとき
と表す
X￢A
３．ブレイドの様々な定義
Left-weightedの定義
 X∈[0,1]n
+
 P∈BBnに対してPの分割XAが任意のPの
×
X’A’に対してX’≦Xとなるとき
 X￢Aと表す
X
A
３．ブレイドの様々な定義
Left-weightedの定義
 X∈[0,1]n
+
 P∈BBnに対してPの分割XAが任意のPの
×
X’A’に対してX’≦Xとなるとき
 X￢Aと表す
X
A
○
X
A
３．ブレイドの様々な定義
標準形とは
 W∈BBnに対して
u
W=δA1A2･･･Apという形式の表現が
一存在する
唯
但、 1≦i≦p-1となる各iに対してAi∈[0,1]n
Ai￢Ai+1 が成り立つ
u∈ Z
３．ブレイドの様々な定義
標準形を作るには?
 maximal
headとtailにわける
 更にtailをmaximal headとtailにわける
 それを繰り返す
３．ブレイドの様々な定義
maximal headとtail
 headとtail
３．ブレイドの様々な定義
maximal headとtail
 headとtail
a
b
head
tail
=
c
３．ブレイドの様々な定義
maximal headとtail
 Pのhead
Hがmaximal headであるとは
HとHを取り除いたPのtailがleft-weighted
となるとき
３．ブレイドの様々な定義
maximal headとtail
 Pのhead
Hがmaximal headであるとは
HとHを取り除いたPのtailがleft-weighted
となるとき
P
×
H
tail
３．ブレイドの様々な定義
maximal headとtail
 Pのhead
Hがmaximal headであるとは
HとHを取り除いたPのtailがleft-weighted
となるとき
P
○
H
tail
４．Javaにおける実装
作成したクラスファイル
 BGList
 Enum_equiv
 Procedure_01
 Find_max_head_12
 Procedure_find_max_head
 BandGenerator
４．Javaにおける実装
BGList
 ブレイドの基本情報をオブジェクトとして
記憶
 基本情報
☆入力ブレイドの本数
☆BandGenerator
４．Javaにおける実装
Enum_equiv
 (入力)V∈BBn
 (出力)Vの同値類全て
４．Javaにおける実装
Procedure_01
+
 (入力)V∈BBn
if V ∈ [0,1]n
False if V ∈ [0,1]n
 (出力)True
４．Javaにおける実装
Find_max_head_12
 (入力)V∈[1,2]n
 (出力)Vのmaximal_headと
そのtailの対(H,T)
４．Javaにおける実装
Procedure_find_max_head
+
∈BBn
 (出力)Vのmaximal_headと
そのtailの対(H,T)
 (入力)V=x1,x2,… xm
４．Javaにおける実装
BandGenerator
+
 (入力)V∈BBn
 (出力)δ
u
A1 A2 … Ap (=V)
(u∈Z,∀ Ai∈[0,1]k 、
Ai￢Ai+1が成り立つ)
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←{(V,λ)}
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α ･･･
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
→
x
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
H’’
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
[0,1]kに入
っている
かCHECK
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
[0,1]kに入
っている
かCHECK
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
λ
･･･
β
･･･
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
V
α
α←{(V,λ)}
･･･
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
･･･
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
･･･
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
λ
･･･
β ･･･
H
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←{(V,λ)}
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
←入力Braid
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←{(V,λ)}
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
←Enum_equiv
・・・・・・
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←{(V,λ)}
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
←Enum_equiv
・・・・・・
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←{(V,λ)}
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを取り除いたブレイド
β←β∪{(H’’,xT)}
od
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
od
←Enum_equiv
・・・・・・
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←{(V,λ)}
Repeat do
β←φ
for each (H,T)∈α do
H←Enum_equiv(H)
for each H’∈H do
x←H’の最右のband generator
H’’←H’から最右のxを
取り除いたブレイド
od
β←β∪{(H’’,xT)}
od
od
for each (H,T) ∈ βdo
if (H∈[0,1] k) return(H,T)
od
α←β
α←Enum_equiv(V)
for (i=1;i<交点数;i++) do
for each H∈α do
x←Hの右からi個のband generator
H’←Hからxを取り除いたブレイド
if (H’∈[0,1] k) return(H’,x)
od
od
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←Enum_equiv(V)
for (i=1;i<交点数;i++) do
for each H∈α do
x←Hの右からi個のband generator
H’←Hからxを取り除いたブレイド
if (H’∈[0,1] k) return(H’,x)
od
od
←V
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←Enum_equiv(V)
for (i=1;i<交点数;i++) do
for each H∈α do
x←Hの右からi個のband generator
H’←Hからxを取り除いたブレイド
if (H’∈[0,1] k) return(H’,x)
od
od
←V
←Enum_equiv
α
・・・・・・
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←Enum_equiv(V)
for (i=1;i<交点数;i++) do
for each H∈α do
x←Hの右からi個のband generator
H’←Hからxを取り除いたブレイド
if (H’∈[0,1] k) return(H’,x)
od
od
α
H’
・・・・・・
x
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←Enum_equiv(V)
for (i=1;i<交点数;i++) do
for each H∈α do
x←Hの右からi個のband generator
H’←Hからxを取り除いたブレイド
if (H’∈[0,1] k) return(H’,x)
od
od
α
H’
・・・・・・
x
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←Enum_equiv(V)
for (i=1;i<交点数;i++) do
for each H∈α do
x←Hの右からi個のband generator
H’←Hからxを取り除いたブレイド
if (H’∈[0,1] k) return(H’,x)
od
od
α
・・・・・・
H’
x
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←Enum_equiv(V)
for (i=1;i<交点数;i++) do
for each H∈α do
x←Hの右からi個のband generator
H’←Hからxを取り除いたブレイド
if (H’∈[0,1] k) return(H’,x)
od
od
α
H’
・・・・・・
x
４．Javaにおける実装
Procedure Find_max_head[1,2]n
<Procedure Find_max_head[1,2]n>
(入力)V∈[1,2]k
(出力)Vのmaximal headとそのtailの対(H,T)
α←Enum_equiv(V)
for (i=1;i<交点数;i++) do
for each H∈α do
x←Hの右からi個のband generator
H’←Hからxを取り除いたブレイド
if (H’∈[0,1] k) return(H’,x)
od
od
α
・・・・・・
H’
x
５．今後の課題
今後の課題
n
の入力からの標準形作成
 Braidの可視化
 parallelのより良い判定法(現在は6
重ループ)
 BB
置換 π
 ブレイドの右点列から左点列への紐の動
きを追うことで,ブレイドに対応した置換が
得られる
４
４
３
３
２
２
１
１
π=
1234 =4213
3142
descedingcycle
 長さjの{1,2,…,n}上の巡回置換
π={tj,tj-1,…,t1}に対して
tj>tj-1>…>t1となるとき
○ π=4321,321 etc
× π=4132, 423,4123 etc
parallel
 descedingcycleの任意の対
{tj,tj-1,…,t1}{si,si-1,…,s1}において
(ta-sc)(ta-sd)(tb-sc)(tb-sd)>0を満たすとき
但,1≦a<b ≦ j,1 ≦ c<d ≦ i
群の定義
 結合律
 単位元
 逆元
結合律
 ∀x,y,z∈G
(x･y)z=x(y･z)
x
y
z
x
y
z
定義(単位元)
 ブレイドの単位元e(1度も交差しないもの)
定義(σi)
 σiを
i と i+1 番目の紐を1度だけ入れ替え
たブレイド
この時σ1の逆元
になっている!!
σ1
4
3
2
1
-1
定義(σi)
 σiを
i と i+1 番目の紐を1度だけ入れ替え
たブレイド
σ1
4
3
2
1
σ1
-1
標準形構成アルゴリズムの計算量
 J.S.Birman,
K.H.Ko等
Ο(|W| 2p)時間で構成
 田邉
Ο(|W| 2)時間で構成
u
W∈BBn: δ A1 A2 …Ap
標準形
4
4
3
3
2
2
1
1
標準形
○
4
4
3
3
2
2
1
1
43 32 21
42 43 21
32 42 21
43 31 32
43 21 31
42 21 43
32 41 42
32 21 41
41 43 32
31 41 32
21 43 31
41 42 43
21 41 43
41 32 42
31 32 41
21 31 41
標準形
○
4
4
3
3
2
2
1
1
43 32 21
42 43 21
32 42 21
43 31 32
43 21 31
42 21 43
32 41 42
32 21 41
41 43 32
31 41 32
21 43 31
41 42 43
21 41 43
41 32 42
31 32 41
21 31 41
Left-weightedの定義
 X∈[0,1]n
+
 P∈BBnに対してPの分割XAが任意のPの
×
X’A’に対してX’≦Xとなるとき
 X￢Aと表す
X
A
○
X
A
≦の定義
 V,W:BBn
V≦W
P1
V
+
(∃P1,P2∈BBn)[W=P1VP2]
P2
W
実行時一覧表
real
紐の本数交点数
メモリ(M)
50
55.8s 16-32
100
4m49.0s 16-32
150
4m40.1s 16-32
200
14m 4.4s 16-32
4本
300
2m41.0s 128-256
400
4m35.8s 128-256
500
50m14.8s 128-256
1000 3h15m50.2s 128-512
50
50.2s 16-32
100
3m30.5s 128-256
150
7m41.6s 128-256
5本
200
14m26.5s 128-256 CPU : Pentium4 2.4G
300 1h31m20.9s 128-256 メモリ : 1G
400 2h47m 8.4s 128-512
OS : RedHat Linux8.0
ねじれているかの判定
 Cの巡回置換の全ての分割{}に対して,(j-
1)の合計がband generatorの合計(交点
数)より小さいとき⇒ねじれている
ex) ブレイドCが(41)(32)という置換で表されているとき
band generatorの合計数＞(2-1)+(2-1)⇒ねじれている
band generatorの合計数＝(2-1)+(2-1)⇒ねじれていない
[0,1]に入るか判定する定理
 A braid
word A is in [0,1] if and only if
A=δ πδ
...δ
for
1
π
2
πk some parallel,
desceding cycles π1 ,π2 ,... ,πK in Σn
－
BBnのある時の標準形作成
δ
ｰ
を考え、必要ならばband generatorを
付け足して考える
－
BBnのある時の標準形作成
δ
ｰ
を考え、必要ならばband generatorを
付け足して考える
－
BBnのある時の標準形作成
δ
ｰ
を考え、必要ならばband generatorを
付け足して考える
δ
-1
同値関係
 V,Wが同値
Vの端点を固定し、紐を出さずに上下関係
を維持したまま動かしWに一致させること
が出来る時
V
W
正同値
 ブレイドの同値性に関する性質を有限回
適用させることによって得られるブレイド
同値
正同値
巡回置換の実装
１
２
３
４
１
２
３
４
π=
1234 =4213
3142
４
４
３
３
２
２
１
１
巡回置換の実装
１
２
３
４
１
３
２
４
π=
1234 =4213
3142
４
４
３
３
２
２
１
１
巡回置換の実装
１
２
３
４
３
１
２
４
π=
1234 =4213
3142
４
４
３
３
２
２
１
１
巡回置換の実装
１
２
３
４
３
１
４
２
π=
1234 =4213
3142
４
４
３
３
２
２
１
１
巡回置換の実装
１
２
３
４
３
１
４
２
π=
1234 =4213
3142
４
４
３
３
２
２
１
１
巡回置換の実装
１
２
３
４
３
１
４
２
π=
1234 =4213
3142
４
４
３
３
２
２
１
１
procedure Canonical_form
(入力) V∈BBk
(出力) δ uA1 A2 ... Ap (=V)(u∈ Z ∀Ai∈[0,1]k)
STEP0 同値類の表を作成
u
STEP1 V=δ Pとなるu∈ ,P∈BBk を構成
STEP2 T←P, i←０
while(T＝λ) do
i←i+1
(Ai,T)←Find_max_head(T)
od
u
return δ A1 A2 ... Ap
procedure Canonical_form
(入力) V∈BBk
(出力) δ uA1 A2 ... Ap (=V)(u∈ Z ∀Ai∈[0,1]k)
STEP0 同値類の表を作成
u
STEP1 V=δ Pとなるu∈ ,P∈BBk を構成
STEP2 T←P, i←０
while(T＝λ) do
i←i+1
(Ai,T)←Find_max_head(T)
od
u
return δ A1 A2 ... Ap
その都度行うことに
よって、メモリ使用を
抑えることができる

Download Report