（计算数学专业论文）压缩变换半群及其性质.pdf

学位论文原创性声明和关于学位论文使用授权的声明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人或集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律责任由本人承担。 论支作者签名：压蜥 刎每j 冀7 日 关于学位论文使用授权的声明 本人完全了解贵州师范大学有关保留、使用学位论文的规定，同意学校保留 或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅： 本人授权贵州师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或其他复制手段保存论文和汇编学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名 筮晒 导师签名： 谢每j 旯7 日 摘要 半群理论是一门年轻的学科，一壹以来人们都在对它进行深入的研究。 它在许多领域都有着广泛的用途，比如计算机科学，自动机理论，编码和 密码理论等等。随着时代的发展，半群理论越来越呈现出强大的活力和广 泛的用途。 在半群理论中，由于任何一个抽象半群都能嵌入到一个变换半群中，所 以变换半群总是一个充满活力的课题就从理论而言，对予半群理论的研 究，只要研究变换半群就足够了。 一直以来，由于有限变换半群优良的可计算性和一系列的组合性质使其 受到广大半群学者的青睐。，j a 。g r e e 觳在王9 5 王年首次研究了格林关系，格林 关系在半群理论的发展中扮演着基础性作用的角色，特别是在有限变换半 群理论的发展中。许多的学者对全变换半群和它的一些子半群进行了深入 的研究例如， h o i w e 【5 9 】，游泰杰【2 3 2 7 】，裴惠生【1 2 1 6 】，杨秀良【1 & 2 2 】 等等。 。 设d ( z ，秒) 是x 上的距离函数，也就是，函数d ：x x _ r ，且满足以下 几个条件： ( 1 ) d ( z ，暑) 0 ，v 2 ，gx 且d ( z ，y ) = o 协z 当耖； ( 2 ) d ( 髫，爹) 蠢( 茹，名) 七基( z ，影) ，￥奎，爹，名x ； ( 3 ) 烈z ，可) = d ( ，z ) 对比，耖x ，用 茁一爹| 表示d ( 窑，办毁表示集合灭上的全变换半群，在第2 章中，研究强的一类新子半群，压缩变换半群g ( s ) x 即 g ( s ) x = q ：￥未，爹x ，蠢( 。8 ，爹玟) d ( 霪，爹) 2 。2 节讨论了g ( s ) 菇的格林关系，2 。3 节讨论了c ( s ) 靠的正则子半群冠够( s ) 糟) 。 在第3 章中，研究戥的一类新子半群，保序压缩变换半群d g 拶) x 的格林 关系即 d c ( s ) x = = o ：0 x ：、9 毫，箩x ，矗( o a ，影复) d ( z ，爹) ， 主要结论如下： 第一覃给出了半群理论的一些基本概念 定理2 1 4 设a c ( s ) 竹，记a ：f a l a 2 山1 ，a 口： 一 - 1 睨嘶夕 肌t 地娟一l 归m ，罅。耻= ( 象0 王0 一 = 1 ，2 。，r ， ，a q = m 十圣一1 ，薯= o 王 定理2 工5 设口c ( s ) n ，若口= ( 象01 m0 1 ) ，a 口= m + t 一 1 ，i = 1 ，2 ，r ，则口是幂等元兮m + t 一1 a ，i = 1 ，2 ，r 命题2 1 6 设e = ( 尝01 ：m0 二1 ) ( 2 仇n 一鬼) 是c ( s ) n 的幂等 、mm 十上m 十甩一上， 元，则在c ( s ) n 中存在幂等元叩1 ；叩2 使得= 7 7 l 啦 定理2 2 7 任给口，p c ( s ) n ，若( q ，p ) ，贝! j 墨口= k p 定理2 2 8 任给q ，p c ( s ) n ，若j 0 q = p 且口一p ，贝! j ( q ，p ) c 定理2 2 9 任给q ，p c ( s ) n ，( 0 f ，p ) 冗营丌( a ) = 7 r ( p ) 定理2 2 1 0 任给0 f ，p c ( s ) n ，若( 0 f ，p ) d ，则i ( q ) i = i ( p ) i 定理2 2 1 1 任给0 f ，p c ( s ) n ，若i 矗( q ) i = l 墨( p ) i 且q 一，则( q ，p ) d 推论2 2 1 2 任给q ，p c ( s ) n ，( q ，p ) 冗7 r ( 口) = 7 r ( p ) 且( q ) = 叉k ( ) ，q p 定理2 3 1 任给口c ( s ) n ，q 是正则元存在【a ：茁j ) 的一个连续截 面a 命题2 3 4 任给q ，p r ( c ( s ) n ) ，则q p r ( c ( s ) n ) 营 0 1 ，0 2 ，嘶) 是 b ，岛，耳) 的截面，其中啦口 命题2 3 5 任给q ，p 兄( c ( s ) n ) ，则下述条件等价： ( 1 ) ( q ，p ) ； ( 2 ) a = p ； ( 3 ) 存在丌( 口) 的一个连续截面a 命题2 3 6 任给q ，p 冗( c ( s ) n ) ，则( a ，p ) 冗甘丌( 口) = 7 r ( p ) 命题2 3 8 任给q ，p 冗( c ( s ) n ) ，则( 口，) 口兮i ( 口) i = i ( p ) j 推论2 3 9 任给q ，p 兄( c ( s ) n ) ，则 ( 1 ) ( a ，p ) 冗叉_ a = p 且，r ( q ) = 7 r ( p ) ( 2 ) ( q ，p ) 了营( q ，夕) d 定理3 1 设口d c ( s ) n ，贝i jx q = 【m a ， 么】n x 推论j 2 设口：f a 1a 2 a 1 o c ( s ) n ，则锄+ 1 一吼：1 ，a a + 1 t ： 1 ，2 ，一1 口1 蚧 定理3 4 比，p 0 c ( s ) n ，则下述条件等价： ( 1 ) ( 口，p ) c ； ( 2 ) x q = x p ，a n dv m q 口i ，i 口 a 一1 i = i o t p 一1 i ； ( 3 ) | 妒7 r ( ，口) ，妒i z ( 卢) 是双射，且妒+ a = 矽 定理3 5 比，p d c ( s ) n ，则下述条件等价： ( 1 ) ( 口，p ) 冗； ( 2 ) 7 r ( a ) = 7 r ( ) ； ( 3 ) j 妒：x 口_ x p 是双射，且p = q 妒 定理3 7 比，矽d c ( s ) 他，则下述条件等价： ( 1 ) ( q ，卢) 口； ( 2 ) i x q i = f x p i 且i ( m 盘+ 后) 口1 i = l ( 仇p + 七) p - 1 l ，七= 1 ，2 ，坞一m q 一1 ； ( 3 ) | 妒7 r ( p ，口) ，妒i z ( 卢) ：z ( 乜) ，z ( p ) 是保序双射 第四章给出了一些后继课题 关键词：压缩半群，压缩正则子半群，保序压缩半群，西e b s 关系，正 则元，幂等元 2 0 0 0m r 主题分类号2 0 m 2 0 中图法分类号0 1 5 2 7 3 a bs t r a c t s e m i g r o u pt h e o r ：i ri say o u n g 汕j e c t ，i th a sb e e nd e e p l yr e s e a r c h e d s e m i g r o u ps e 皿口o u pt n e o 巧塔ay o u n gs u b 】e c t ，l tn a sb e e nd e e p l yr e s e a r c n e d e r n l f o u p t h e o 巧h 嬲印p l i e di i lm 锄y 丘e l d s ，s u c l l 嬲c o m p u t e rs c i e n c e ，a u t o m a t at h e o 吼t h e o 巧 o fc o d i n g ，c r y p t o g r a p h ma n ds oo n i ti s 印p e 盯i n gs t r o n g 订g o ra n di tw o u l dh a sm o r e a n dm o r ea p p l i c a t i o n s i ns e m i 口o u pt h e o r y ，t r a n s f o r m a t i o ms e m i g r o u pw 船a h 嘞r saa c t i v et 弱ki i l1 嬲t d e c a d e s 8 i n c ee a c hs e m i g r o u pc a nb ei 1 1 s e t e di ns o m et r a n s f o r m a t i o n m i g r o u p t h e - o r e t i c a l l y f o ra b s t r a u c ts e 叫盯o u pt h e o r yi ti se n o u g ht os t u d yt r a n s f o r m a t i o ns e l i f o u p f i l l i t ef u ut r a n s f o r m a t i o n m i g r o u ph 蟠a t t a c t e dm 啷7s c h o l a r st h a m 【sf o ri t i 8 c o m p u t a b l ea n di th a sm a 哪w e uc o m b i i l a t o r i 缸p r o p e r 七i e s g r e e n sr e l a t i o n s ，丘r s t 8 t u d i e db yj a g r e e ni i l1 9 5 1 ，h a i v ep l r 甜af u n d 锄e n t a l lr 0 1 ei i lt h ed e v e l o p m e n t o fs e m i g r o u p ，e s p e c i a u mi nt h ed e v e l o p m e n to f 丘1 1 i t ef u ut r a n s f o r m a t i o ns e m i 口o u p m a n ys c h o r a i e sh a v er e s e 盯c h e dd e e p l yf o rf u ut r a n s f o r m a t i o n8 e m i g r o u pa l t l di t ss o m e s u b s e m i 盯o u p s f 0 re x 锄p l e ，h o i w e 5 9 】，y o u 删i e 【2 3 2 7 】，p e ih m s h e n g 1 2 1 6 】，y 皿g u n a n g 1 8 - 2 2 】，a n ds oo n l e td ( z ，秒) b ead i s t a n c 争f u n c t i o no nx ，t h a ti s ，色f u n c t i o ndf r o mx xt ot h er e a l n 1 】1 b e rf i e l d 咒，8 a t i s 丘n gt h ef 0 】硎n gc o n d i t i o 瑚： ) d ( z ，夕) o ，v z ，可xa n dd ( z ，可) = o 咎z = ； t ) d ( z ，y ) d ( z ，z ) + d ( z ，可) ，v z ，可，z x ； ( t i ) d ( z ，可) = d ( 可，z ) f 0 r 妇，可x ，d e n o t el z 暑，ia u sd ( z ，可) d e n o t eb y 取t h ef u ut r a j l s f o r m a t i o ns e 血口o u p o nx ，i nc h 印t e r2 ，an e l wk i l l do fs u b s e 血g r o u p so f 乃f ，s e 血g r o u po fc o m p r e 豁i o n c ( s ) xi sc o n s i d e r e d l e tt h es e t c ( s ) x = q 丁k ：v z ，秒x ，d ( z ，可q ) d ( z ，夕) ) g r e e n 7 sr e l a t i o i l so fc ( s ) n 踞ed i s c u s s e di ns e c t i o n2 2 ，t h es u b s e r n j g r o u po fc ( s ) ni s c o n s i d e r e di 1 1s e c t i o n2 3 i nc h 印t e r3 ，an e wl 【i n do fs u b s e m i g r o u p so f2 x ，s e m i f o u p o fc o m p r e s s i o nd c ( s ) xi sc o n s i d e r e d l e tt h e 舱t d g ( s ) x = o f 0 k ：v z ，箩x ，d ( z q ，可口) d ( z ，y ) ) t h e m a i l l ，e s l l l t s 缸e 舀v e na sf o l l 0 w i n g i nc h a p t e r1 w e 舀v es o m eb a s i cc o n s e p t i o na b o u ts e r n j 酽o u pt h e o r y t h e o r e m2 1 4l e t 口g ( s ) n ，d e n o t eq 4 ，a t q = 啦，口1 口2 、l 小 赴眈钆吼 i i 冀a 篡胁? 邯_ 1 ) i ；瑚，血蚍= ( 鲁01 _ 0 1 卜= 仇+ i 一1 ，i = 1 ，2 ，7 ： t h 毛。r e m2 工5l e ta c ( s ) n ，讧口= ( 象0 1i 仇0 1 ) ，a 口= m + o、仇m + 上仇+ r l ， 1 ，i - 1 ，2 ，r ，t h e nqi si d e m p o t e n t 兮仇+ t 一1 a ，i _ 1 ，2 ，r l e m m a2 1 6l e ts = t e n te l e m e n ti 1 1c ( s ) n ，t h e ne 0 1 _ 0 1 卜m m a n 池即争 t h e r ee ) 【i s ti d e m p o t e t s 叩1 ，啦i nc ( s ) nf o rw m c hs = 叩1 仇 t h e o r e m2 2 7f o ra l l l ya ，p c ( s ) n ，i f ( q ，p ) c ， t h e n q = p t h e o r e m2 2 8f o ra n y q ，p c ( s ) n ，i f j ，n q = k pa n d 口一p ，t h e n ( q ，p ) t h e o r e m2 2 9f b ra n yq ，p c ( s ) n ，( q ，p ) 7 已兮7 r ( 口) = 7 r ( p ) t h e o r e m2 2 1 0f o ra n y q ，p c ( s ) 几，i f ( q ，p ) 刃，t h e ni 叉_ ( q ) i = i j 气( p ) 1 t h e o r e m2 2 1 1f o ra j l y ( q ，p ) 刃 口，卢c ( s ) n ，i fi k ( q ) l = l k ( ) ia j l d 口一p ，t h e n c o r o l l a r y2 2 1 2 f 0 ra n y j 0 ( 口) = j ，n ( p ) ，a p 口，p c ( $ ) n ，( q ，p ) 冗亭7 r ( q ) = 7 r ( p ) a n d t h e o r e m2 3 1f 0 rq c ( s ) n ，qi 8ar e 叫盯营t h e r ee 姐s t st h a ta i sac o n t i 肌o u s c r o s s - s e c t i o no f a ：t ，) ： p r o p o s i t i o n2 3 4f b r0 f ，p r ( g ( s ) n ) ，t h e nc l 够 ac r o s s - s e c t i o no f b 1 ，岛，研) ，w h e r e 啦k 口 冗( c ( s ) n ) 兮【0 1 ，0 2 ，) i s p r o p o s i t i o n2 3 5 e d rq ，p r ( c ( s ) n ) ，t h e nt h ef o u o w i n gs t a t e m e n t s 缸ee q 山v - a l l e l l t ： ( 1 ) ( q ，p ) c ； ( 2 ) k 口= p ； ( 3 ) t h e r ee ) 【i s t sa w h i c hi sac o n t i n u o u sc r 0 8 s - 8 e c t i o no f7 r ( q ) p r o p o s i t i o n2 3 6f o rq ，p r ( c ( s ) n ) ，t h e n ( 口，p ) 7 已7 r ( q ) = 7 r ( p ) p r o p o s i t i o n2 3 8f b r 口，p r ( c ( s ) n ) ，t h e n ( q ，p ) 口 亭i j ( q ) i = i ( p ) 1 c o r o u a r y2 3 9f b rq ，p r ( c ( s ) n ) ，t h e n ( 1 ) ( 口，p ) 冗甘叉_ q = k pa n d7 r ( q ) = 7 r ( 卢) ( 2 ) ( q ，p ) 歹营( 口，p ) d t h e o r e m3 1l e tq d c ( s ) n ，t h e nx q = 【仇a ，m 二】nx 5 c ：o r o h a r y3 2 l e t 口= 或+ l ，誉= 王，2 ”。，r l 。 p g ( s ) 诏，t h e n 砚+ l 一峨= l ，a t h e o r e m3 4v q ，p 0 c ( s ) n ，t h e nt h ef o u a 而n gs t a t e m e n t sa r 6e q m v a l e n t ： ( 1 ) ( 瘦，多) ； ( 2 ) x a = x ，a 肛d 协 呶 眠，l 啦a 一1 i = l 啦芦一1 l ； ( 3 ) j 妒霄( 芦，口) ，妒| z i 8ab i j e e t i o n ，8 越d 妒章盘= 声 t k o r e 燃3 5 妇，多d 0 ( s ) 髓，t h e 黩t h e 弑l 栅粥蘸鑫t 激e 幽龇州谳e 砖： ( 1 ) ( 口，p ) 佗； ( 2 ) 霄( 搜) = 嚣( 多) ； ( 3 ) j 妒：x 口一x i sab i j e c t i o n ，a n d = 口妒 r k o r e m3 7v q ，多d e ( s ) n ，t k nt & 我濉) w i 醒s 毛8 乇锄晒毛s 船e 聪啦v 疵髓： ( 1 ) ( 0 f ，) 移； ( 2 ) l x 口l = l x 声l 蕊l ( + 竞) 穗一1 | = ( 脚竞) 多一1 | ，凳= 王，2 ，阮一一l ； ( 3 ) | 妒7 r ( p ，q ) ，妒l 岩) ：z ( q ) _ z ( p ) i sa no r d e r - p r e s e 舳gb i j e c 七i o n i nc h a p t e r4 ，w eg i v es o m ef u 恤e rw o r k k e y w l o r d s ：c o m p r e 辅i o no fs e m i g r o u p 8g ( s ) n ，鼬g t l l a rs u b s e m i f o u p0 fg ( s ) n ， g r e e n sr e l a t i o n s ，o r d e r _ p r e s e 耐n g 强a 潞f o r m 龇i o ns e 瞄铲o u po fp e ( s ) n ，r e 鲜l a re | _ e m e n t ，i d e m p o t e n t 2 0 0 0m 氛s 曲j e c 乇c l a s s 邋c a 主i o 载2 0 m 2 0 e h i n e s el i b r 鑫3 眵c 董a l s s i e a l 砉i o 珏0 王5 2 。7 6 、lf冬如如眈 矗 l a n ， c h a p t e r1 。 i n t r o d u c t l o na n nr r e 儿m l n a r l e s t-1j 1 广、1 1 王g o 戤e p 毛s 戡dp r 印瑟赫孙潞 t k 翘t r 拄璐f o r 皴越主l 礁s e 越琴。珏p 奴强毯。建e 磁姆s e tx h 铺b e 旺e s e 越妇e d 稍d e l yb yan 1 加出e ro f8 c h o l a r s ，e s p e c i a l u yf o rt h e 最i l i t ef u l lt r a 肌8 f 6 r m a t i o ns e m j - 寥o u p 磊f 镑e x 越懿p 至e ，t h er 8 矗鼢瓢遍t k 髓r u c t 瑚：e so f8 毽b s e 血g 零镦攀s 醴互lh 8 勰 b e e nr e 8 e a r c h e dd e e p l yb y 凹。伽i e ，y 伽t o 巧t ea n dy 帆gx 池玩a 佗9 ，e t c 【3 9 ，1 2 6 ，】 铡艟篮d e r - p 鸦r v i 珏gt r 幽r 班8 恚i o 器s 锄峨o u p 瓯h a sb e 旺鼬呔l 主e dd e e p 量yb y 嚣徽g t 8 【8 j 1 9 7 1 】y 删【1 9 ，2 0 ，2 2 】，g 口帆e sa n d 日伽z e 【2 ，1 9 9 2 】h a v em a d em o r ed e t a nd i s c u s s 耋泌迕。t h ep 皴t i 0 0 r d e r - p r e s e r v 主醒专r 雒溺6 r m 或i o 登删器。即p ) 怯w 鑫si 弱专r o d 封 c e d n r s t l yb yg o d m e sa i l d 日洲i e 【2 ，1 9 9 2 】舭c e n t l y p e i 【1 6 ，2 0 0 5 】i n t r o d u c e da 铷 i l i l yo f 臌k e 越即珏p so f 致，卷h 酗l s 珏) ，琵d 赵豁r e s e 躲杰穗毒k 删积毛妇，乇娩( e 缎 r e l a t i o 嬲a j l d8 0 m eo 七h e rp r o p e r t i e 8o f2 _ ( x ) i n 【1 7 ，2 0 0 5 】w h e ni x ii 8f i n i t e 王沁l 越i 秘g 毛ke q 氆v 矗粉搭e 删蠢gt r 锹塔如r m a t i o 套西g r o 印2 | ( x ) ，戳i i 逵r o 纛娃c e an e w 铷嘣1 yo fs u b s e m i g r o u p sc ( s ) xo f 乃【嬲f o u 0 v 巾堰 王感d ( 2 ，b ea 出或8 戳秘翘陇乞i o 羟。珏x ，t k 恚l s ，鑫f 毡戳毛i o 珏d 螽。氆x x 专。毫kr 越 n l 】加b e r6 e l dr ，s a t i s 最n gt h ef 0 u l r i n gc o n 出t i o l l s ： 0 ) 症( 。，爹) o ，v 奎，爹xa 致纛d ( 霉，帮) = o 2 = 寥； ( 托) d ( z ，分) d ( z ，z ) 十d ( z ，秒) ，v z ，y ，z x ； ( g 蕊) 耋( 鬈，爹) = 拄( 爹，z ) 。 l e t 。 g ( s ) x = 貔致：魄，影x ，d ( z 8 ，爹q ) d ( 。，爹) t h e na ( s ) xi sas u b s e r n j 髓o u po f 取i i lf a c t ，p g ( s ) x ，比，暑，x ，w eh a v e | 矗( z & 声，秽8 黟) d ( 。反，届) d ( z 一秽) ，8 0a 黟c ( s ) x w 毡e a 羹e ( s ) xa sac o i i l p r e s s i o n s e m i 酊o u po nt h es e tx ， 硒m n o w 强，w e n s i d e rt 圭l ec 瓣t h a tx = 蕊= l ，2 ，霸 研t h 疽( 霉，影) = 卜秒| ， a n dd e n o t ec ( 8 ) xb yg ( s ) 住a n d 戥b y 王硪sb ean o n - e m p 时s e t 硒t ha b i n a 科o p e r a t i o n o ni 毛，si sc a l l e d l a $ e m i 9 r d 印 i f ( z ) z = 留( z ) f o ra n yz ，秽，z s t h i s8 1 w 姆st a k e st h es i m p 王ef o r m ( z 爹) z 一2 ( 爹z ) 。 i fs e 嘶g r o u psc o n t a i n sa ne l e m e n t1w i t ht h ep r o p e r t y 鬈l = 王茹剐争掰霉鼠 w es a yt h a t1i sa nt d e 优t 坷e f e 仇e 佗to fsa n dsi sa m d 佗扰d c l e a r l y ，as e m i g r o u ps h a sa tm o s to n ei d e n t i 锣e l e m e n t l e t sb eas e l i g 互o u p a ne l e m e l l tz si sc a u e di d e 7 n p d 钯7 砧i j ez z = z ，a n dc a u e d r e 夕缸2 口7 i ft h e r ee 妃s t s 暑，ss u c ht h a tz = z 可z as e m i g r o u p si sc a u e d6 口几di fa ui t s e l e m e n t 盯ei d e i n p o t e n t 。a i n dc a u e d 他1 9 让2 0 ri fa ui t 8e l e m e n t 打er e g m 盯 l e t 日sa n d 日d ，日i 8c “e das u 6 s e m t 仇印0 isi fz 可日f o ra n yz ，秒日 si sc a u e d 卯忱d d d zi ft h es e to fi d e m p o t e n te l e m e n t si i lsf o m l sas u b s e m i g r o u p l e t 日b eas u b s e m i g r o u po fs ，日i 8c a u e da 他夕u c 凹s u 6 s e m t 9 r o t 正po fsi f 日i s r e g u l a r ，c a l l e daf e ，ti d e 口f ( r i 夕九亡t d e 凸r ) o fsi fz 日( 危z 日) f o ra j l yz sa 皿d 危日，8 j 1 dc a u e da j lz 如以o fsi fi ti sb o t h1 e 危i d e “a n dr i g h ti d e a lo fs l e t 日b ea n o n e m p t ys u b s e to fs i ff o ra n yz s ，t h e r e 耐s t0 1 ，口2 ，0 ，l 日 s u c ht h a tz = 口1 0 2 ，t h e n 日i sc a e da 夕e n e r 口t 卯s e to fsa n dd e n o t eb ys = w h e nsi 8f h m e 血g r o u p ，t h er a n ko fsi 8d 胡n e db y m 饥引日l ：日cs ，s = ， - 一 j w h e r e1 月li st h ec a r d i n a l lo f 日 l e txb ea n o n - e m p t ys e t ，a 跣n 口阿r e f 捌d npo nx i sas u b s e to fx x ，w 】1 e r e x xi st h ec 龃t e s i a np r o d u c t0 fxa n dx t h eb i n a 珂r e l a t i o npi 8c a u e da e q 乱t u o f e n c er e f c 咕i d ni f f o ra a a yz ，可，z x ，( 1 ) ( z ，z ) p ，( 2 ) ( z ，可) pi i n p l i e s ( 秒，z ) p ，a n d ( 3 ) ( z ，秒) j da n d ( 可，z ) pi m p l y ( z ，z ) p ae q m v a l l e n c er e l a 七i o n po 耳as e 血g r o u psi 8c a l l e dl e ，tc o 竹夕7 t 正e n c e ( r i 夕7 拓o d 7 姆r t 正e n c e ) i f ( z ，可) pi m p u e s ( 口z ，o 秒) p ( ( z 口，o ) p ) f o ra n yz ，o s pi sc a n e dc d n 夕r t 正e 竹c ei fp i sb o t hl e r c o n g r u e n c ea n dr i g h tc o n g r u e n c e l e tsb eas e l i g r o u p ；、h e n1 s ，l e ts 1 = s u 1 w i t h1 z = z 1 = z f o ra n y z s 1 ，a n ds 1 = sw h e n1 s t h e ns 1i sam o n o i d t h eg r e e n 7 sc ，冗，咒，口，了r e l a t i o n so ns 盯ed e f i n e da sf o l l o 谢n g f 0 ra n yz ，可s ， ( 1 ( 2 ( 3 ( 4 ( 5 0 ，可 0 ，可 ，可 ， ( z ，影 i ft h e r ee x i s to ，6 s 1s u c ht h a 七z = 口ya n d 可= 6 z ， 冗i ft h e r ee x i s to ，6 s 18 u c ht h a tz = 可口a n d 可= z 6 ， 咒i f ( z ，! ) ca i i 试( z ，可) 冗，a l w a y sd e n o t e db y 冗= c n 7 已， di f ，! ) c0 r ，夕) 冗，a l l w a y sd e n o t e db yd=c u 冗， 了i ft h e r ee ) 【i s to ，6 ，u ，u s 1s u c ht h a tz = 凸y 6a n d 可二t 正z 口 1 20 r g a n i z a t i o no ft h i st h e s i s t h er e s to ft h et h e s i si so r g a n i z a t i o na sf 0 1 1 0 w s 8 i nc h 印t e r2 ，an e wl 【i n do fs u b s e 血g r o u p so fc ( s ) n ，i sc o 璐i d e r e d i nf i l l i t e c a 8 e ， t h er e g l l l a r i t ya j l dg r e e n ，sr e l a t i o n so fc ( s ) na r ed i s c u s s e di ns e c t i o n2 2a n ds e c t i o n 2 3 ，t h eg r e e sr e l a t i o n s 刃= 了o nc ( s ) na n d 冗= 冗nc a l g e b r a i c ，c 伽曲i i l a t o r i 8 l 龇1 dr a n kp r o p e r t i e so f 靠h a v eb e e ns t u d i e do v e ra l o n gp e r i o da l l l dm a n yi n t e r e s t i n g r e s u l t sh a ee m e r g e d ( s e e ，f o re 舢p l e 【4 ，5 ，7 ，8 】) i nc h a p t e r3 ，9n e wk i i l do fs u b s e i 吐 g r o u p so fd c ( s ) n ，i sc o i l s i d e r e d i nf i l l i t ec 鹤e ，t h eg r e e n ，sr e l a t i o n so fd c ( s ) na r e 出s c u s s e di nc h a p t e r3 9 c h a p t e r 2 c o m p r e s s i o no fs e m i g r o u p sc ( s ) 元 s e c t i o n2 1p r e l i m i n a r i e so fg ( s ) n t h e6 r s t1 e 衄ai 8f a i r l yo b v i o u sa n di sc e r t 础坶n o tn e w l e m m a2 1 1l e te 死，t h e nei si d e 1 p o t e n t 兮t h er e s t r i c t i o ng l 概i si d e n t 耐m a p p m g w bw o l l l dn k et oi n t r o d u c eh e r eau s e f mp i e c eo fn o t i o n ：b v e 盯t r a n s f 6 m a t i o nqi n ? = w h e r et m ( q ) = 口l ，口2 一，劬) a n da = 0 t 口，t = 1 ，2 ，7 - ，c a u e dt h eb 1 0 c ko fq l e m m a2 1 2l e tq 4 ，d e n o t e t h e nqi si d e n l p o t e n t 兮啦a ，i 1 ，2 ，r p r o o ft h el e m m ai sf 出l yo 晰o u s d e f i n i t i o n2 1 3l e ta ，a n da 0 ，w ec a u d ( a ，七) = m i n l 口一七l ：口a ，a t q = 啦) ，i = 1 ，2 ，r ， t h ed i s t a n c e 行o m 七t 0a ，、 t h e 。r e m2 1 4l e tq c (