（应用数学专业论文）最小全一问题的解及其算法的研究.pdf

摘要 摘要 细胞自动机是一种离散动力系统。它包含了由细胞单元的状态构成的配制 以及作用在配制上的传递规则。下面我们总是假设g = ( ke ) 是一个有限无向 的简单连通图。图上的每一个顶点可以看作细胞自动机上的一个细胞单元，细 胞单元上状态的值或者是o 或者是1 。如果每一个细胞单元的状态都被赋予了一 个值，则所有细胞单元状态值的集合被称为细胞自动机上的一个配制。自动机 的演化由局部传递规则决定。如果x 是时刻t 的一个配制，y 是局部传递规则作 用在x 后于时刻t + l 的配制，那么l ，称为x 的后继，x 被称为】7 的前驱。在配制 进化领域里的一个基本问题就是研究对于一个给定的目标配制确定它的前驱 是否存在的问题。这个问题被称作前驱存在问题。更进步，如果给定一个 界p ，寻找基数最多为卢的前驱配制问题被称为界定前驱存在问题。给定一个有 趣的目标配制1 ，即目标配制是每一个细胞单元的状态值都为1 ，我们将以基于 局部规则一及盯下的图上的细胞自动机作为对象展开研究。 对于仃+ 规则，当初始配制为o ，目标配制为1 时，相应的前驱存在问题也 被称为矿全一问题或者直接称为全一问题【2 7 】。p e l e d 提出了一个等价的问题被 称为点灯问题【2 2 。类似的，对于口规则，当初始配制为0 ，目标配制为l 时， 相应的前驱存在问题被称为一全一问题。为方便起见，目标配置的前驱也被称 为解。 近年来全一问题已经被广泛的研究，见s u t n e r 2 9 ，3 l 】，b a r u a 和r a m a s h n a n 2 】以及d o d i s 和w i n k l e r 1 1 。全一问题解的存在性问题已经被完全解决。用线 形代数的方法，s u t n e r 2 8 】证明了全一问题的解总是存在的，并给出了几n 的 格子图上解的一些计数结果。s u 协e r 曾提问是否可用图论的方法证明解的存在 性问题( 2 8 】。e r i k i s s o ne ta 1 【1 3 给出了解存在性的图论证明。进而，c h e ne ta 1 【6 给出了一个精巧的图论算法用来找到一般图上的解。如果我们也要求前驱 配制中非零状态的细胞单元个数最少，相应的问题被简称为最小全一问题。这 个问题已经被证明对于任意图是j 7 、r p 一完全问题 2 5 】。最近，b r o e r s m a 和l i 又证 明了对于二部图这个问题也是p 一完全的【3 。全一问题也可以被称为点点问 摘要 题。由点点问题我们很容易提出下面三个问题：点边问题，边点问题和边边 问题。这些问题即使不与全一问题联系，从算法的角度都有其各自的研究意 义。 与全一问题不同的是，o 全一问题对于一些图类可能并不存在解。并且最 小盯全一问题对于二部图也已经被证明是p 完全问题。所以对于任意给定的 树图，特殊的二部图，确定其解存在问题及在解存在的条件下是否存在多项式 时间算法寻找最小解的问题就成为了十分有趣的问题。进一步，如果我们要求 从任意的配制开始在a 规则作用下到达全的配制，相应的一全问题就被称为 一般盯全一问题和一般最小盯全一问题。 本论文按照如下结构组织成文：第一章论述了盯+ 规则以及。规则下的全 问题的历史背景以及为算法研究的方便，我们将以图论的语言对所研究的问题 进行具体描绘。 第二章，我们研究树的最小全一问题。首先，对于树的任意一组解我们通 过引进准全一问题的定义来给出解结构的解释。然后我们推导出解的计数公 式。通过调用最小奇( 偶) 和问题的算法作为子过程，我们得到了最小全一问 题的线性时间最优算法。由解的结构特性，我们还得到了线性时间算法用于求 得单圈图的全一问题的解。 在第三章中我们给出了线性时间算法求得单圈图以及双圈图上最小全一 问题的解。这些算法都是以带有限制的树的最小全一问题算法为基础的。 在第四章中我们研究新的全一问题及其相应的最小全问题。对于点边 问题，我们证明当且仅当二部图时解是存在的，并且只有可能存在两组解，因 此存在线性时间算法确定最小解。对于边点问题，我们证明当且仅当图具有偶 数个顶点时才存在解。我们通过多项式变换将最小边点问题转换成了最小完美 匹配问题，从而得到了存在多项式时间算法解决最小边点问题的结论。对于边 边问题的研究可以被转化成研究线图上的点点问题。 在第五章，我们得到了两个线性时间算法用于解决树上的一般a 全问 题。第一个算法用来解决在解存在的情况下解的计数问题。第二个算法用来解 决最小口全一问题。进而，我们稍加修改第二个算法就可推广成一般最小盯全一 i i 摘要 问题的嚣优算法。 i i i a b s t r a c t a b s t r a c t ac e l l u l a ra u t o m a t o ni sad i s c r e t ed y n a m i c a is y s t e mt h a tc o n s i s t so fa na r r a n g e m e n to f b a s i cc o m p o n e n t sc a l l e dc e l l st o g e t h e rw i t hat r a n s i t i o nr u l e i nw h a tf 0 1 1 0 w s w ea l w a y sa s s u m et h a tg = ( ve ) i saf i n i t ec o n n e c t e ds i m p l eu n d i r e c c e d 矿a p h e a c h v e n e x ( c e l l ) a s s u m e so n eo ft l et w o8 t a t e s ，v i z oo r1 a na s s i g n m e n to fs t a t e st om e v e n i c e sw i l lb ec a l l e dac o n 丘g u r a t i o n n eb e h a v i o ro ft h ea u t o m a t o ni sd e t e r n l i n e d b y a1 0 c a lt r a n s i 石o nm l e i fxi sac o n f i g u r a t i o na tn m et ，yi st h ec o n f i g u r a t i o na tt i m e t + 1b yc h el o c a lt r a n s i t i o nm l eo ne v e r yc e l l ( v e r t e x ) ，t h e ny i sc a l l e dt h es u c c e s s o ro f x ，a n dc o n v e r s e l y ，xi sap r e d e c e s s o ro fy o n eo ft h eb a s i cp r o b l e mi nm es t u d yo f t h ee v 0 1 u t i o no fc o n 行g u r a t i o n si st od e t e r f n i n ew h e t h e rag i v e nt a 曙e tc o n 6 9 u r a t i o nh a s ap r e d e c e s s o r t h i sp r o b i e mi sr e f e 功耐a st h ep 阳d e s s o r 蹦括把n c 已p r d 6 k m ( p e p ) 2 5 】i fg i v e nab o u n dpa n dt h ep r e d e c e s s o rc o n n g u r a t j o nj sr e q u i r e dt oh w ec a r d i n a l i t ya tm o s c 卢，t h i sp r o b l e mi sc a l l e dt h e 扫口“凡d 蒯p ，霸出c p 盼口r “i s 把凡c ep m 扫f 已m ( b p e p ) g i v e nt h ei n t e r e s t i n gt a 瞎e tc o n 矗g u r a t i o nw h i c hi s 矗x e dt ob e1 ，t h ev e c t o r w i t ha l lc o m p o n e n t se q u a lc ol ，w es t u d yc e l l u l a ra u t o m a t ab a s e do nt w ow e l l ，s t u d i e d 1 0 c a lt r a n s i t i o nr u l e s 矿r u l ea n d 口一n l l eo ng r a p h si nm i st h e s i s f o rt h e 盯十一r u l e ，w h e nm ei n i t i a lc o n 6 9 u r a t i o ni s 最x e dt ob eoa n dt h et a r g e t c o n f i g u r a t i o ni s 矗x e dt ob el ，t h ec o r r e s p o n d i n gp r e d e c e s s o re x i s t e n c ep r o b l e mi sa l s o c a l l e d 口+ 口盯- d 咒p 5p ，d 西? p ，犯o r 日z z d n 已sp r d 扫z e m 【2 7 s j m p l y ，a ne q u j v a l e n tv e r s i o n o fc h ea l i - o n e sp r o b i e mw a sp r o p o s e d b yp e i e di n ( 2 2 ，w h e r ei cw a sc a i l e dt h e 肠仰 2 瞎h f f 馏p r d 凸j 已m s i m i l a r l y ，f o rt h e 盯- r u l e ，w h e nm ei n i t i a lc o n f l g u r a t i o ni s 矗x e dt ob e oa n dt h e “l r g e tc o n 矗g u m t i o ni s 疗x e dt ob e1 ，t h ec o n s p o n d i n gp r e d e c e s s o re x i s t e n c e p r o b l e mi sc a l l e d 盯d f f - o n e sp r d 扫f 已m f o rt h es a k eo fc o n v e n i e n c e ，ap r e d e c e s s o ro f t h et a r g e tc o n 矗g u r a t i o ni sa l s oc a l l e da5 0 ? “f j d 胛 t h ea 1 1 一o n e sp r o b l e mh a sb e e ne x c e n s i v e l ys t u d i e dr e c e n t l y ，s e es u t n e r 【2 9 ，3 1 ， b a m aa n dr 锄a k r i s h n a n 【2 】a n dd o d i sa n dw i n k l e r 1 1 】t h ee x i s t e n c eo fs o i u t i o n s o ft h ea 1 1 一o n e 8p r o b l e mf o rg e n e r a lg r a p h sw a ss 0 1 v e da l r e a d y 、u s i n g1 i n e a ra l g e b r a ， v a b s t r a c t s u t n e r 【2 8 p r o v e dt h a ti c i s a l w a y sp o s s i b l et o1 i g h te v e r y1 a i n pi na n yg r a p h sb y 盯十一r u l e ，a n dg a v es o m er e s u l t so ne n u m e r a t i n gt h en u m b e ro fs o l u t i o n sf o r 佗ng 订d g r 印h s i n 2 8 】，s u t n e ra s k e dw h e t h e rt h e r ei sag m p h t h e o r e t i cp r o o ff o rt h ee x i s t e n c e b r i k i s s o ne ta 1 【1 3 g a v eas u c hp r o o f c h e ne ta l 6 】g a v ea ne l e g a n tg r a p h m e o r e t i c a l g o “t h mt oo b t a i nas o l u t i o nf o rg e n e r a lg r a p h a n di fw ea l s or e q u i r et h em i n i m u m n u m b e ro fc e l l sw i t hn o n z e t os t a t e s ，t h ec o r r e s p o n d i n gp r e d e c e s s o re x i s t e n c ep r o b l e m i ss i m p l ya d d r e s s e da sm 加f m “m 日z z o n e s p 阳扫f e mw h i c hw a ss h o w nt ob en p c o m p l e t e f o rg e n e r a lg r a p h si n 【2 5 r e c e n t l y ，b r o e r s m aa n dl ip r o v e dt h a tt h ep r o b l e mi sn p 。 c o m p l e t ee v e nf b rb j p a r t i t eg r a p h s 【3 】t h ea 1 1 一o n e sp m b l e mc a na i s ob ec a l l e d 山e v e r c e x v e r c e xp r o b l e m f m mm ev e r t e x v e r t e xp r o b l e m ，o n ei se a s i l yl e dt op r o p o s e t h ef o l l o w i n gt h r e ep r o b l e m s ：t h ev e r 沧x e d g ep r o b l e m ，m ee d g e v e r t e xp r o b l e ma n d t h ee d g e e d g ep r o b l e m ，r e s p e c t i v e l y t h e s ep r o b l e m sh a v et h e i ro w ni n t e 】汜s t sa n da r e w o n ht ob es t u d i e df r o ma l g 洲t 1 1 m i cp o i n to fv i e w ，e v e ni fn o tr e l a t 酣t ot l ea 1 1 一o n e s p r o b l e m d i f f e r e n tf r o mt h ea 1 1 一o n e sp m b l e m ，t h e 矿a l l o n e sp r o b l e mm a yn o th a v es o l u t i o n sf o rs o m eg r a p h s a n d ，t h em i n i m u m 盯a l i - o n e sp r o b l e mj sa l s on p c o m p l e t e e v e nf o rb i p a r t i t eg r a p h s s o ，i tb e c o m e sa ni n t 朗e s t i n gq u e s t i o nt o6 n dp o l y n o m i a l t i m ea l g o r i t h m st od e t e n n i n ei ff o rag i v e nt i t e ，as p e c i a lb i p a n i t eg r a p h ，t h ep r o b l e m h a ss o l u t i o n s ，a n di fi td o e s ，t of i n das 0 1 u t i o nt ot h em i n i m u m 口a l l o n e sp r o b l e m f u r t h e m o r e ，i fw es t a nf r o ma n yc o n 矗g u r a t i o na n de n da t 山ea l 】一o n e sc o n 矗g u r a t i o n ，【h e c o n e s p o n d i n g 口a u o n e sp m b l e m sa r ec a l l e d 占已胛已m f 盯以肼。凡p jp m 扫? 吕ma n dg p 凡已阳f m j i 聊m m 盯d 2 z - d n e sp r d 扫2 8 m t h et h e s i si so 曙a n i z e da sf 0 1 1 0 w s ：i nc h a p t e rlw ei n t r o d u c et h eb a c k g m u n do f a 1 1 - o n e sp r o b l e ma n dr e p h r a s et h ep r o b l e m si nt e m so fg r a p h t h e o r e t i ct e m l i n o l o g y f o rd e s c r i b i n go u r a l g o “t h m sm o r ec o n v e n i e n t l y i nc h a p t e r2w es t u d ya 1 1 一o n e sp m b l e mf o rt r e e s 、f i r s t 、f o ra n ys o l u t i o nt ot h e p r o b l e mf o rac r e ew eg i v eac h a r a c t e r i z a t i o no nt h ee i e m e n t si nt h es o l u t i o n ，b yi n + t r o d u c i n gt h ec o n c 印to fq u a s i a l l - o n e sp r o b l e m t h e nw eg i v et h ee n u m e r a t i o nf o r t h en u m b e ro fs o l u t i o n si nat r e e b yu s i n gt h em i n i m u mo d d ( e v e n ) s u mp r o b l e ma s v i a b s t r a c t s u b p r o c e s s ，w eo b t a i na1 i n e a rt i m ea l g o r i t h mf o rt h em i n j m u ma 1 】一o n e sp r o b l e mf o r t r e e s w ea l s og e tal i n e a rt i m ea l g o r i 山mf o r 矗n d i n gs 0 1 u t i o n st ot h ea 1 1 一o n e sp m b l e m i nau n i c y c l i cg r 印h i nc h 印t e r3 ，w eg i v eg r a p h 一出e o r e t i ca l g o r i t h m so f1 i n e a rt i m et ot h em i n i m u m a 1 1 一o n e sp r o b l e mf o ru n i c y c l i ca n db i c y c l i cg r a p h s t h e s ea l g o r i t h m sa r eb a s e do na g r 印h t h e o r e t i ca l g o r i t h mo fl i n e a rt i m et ot h em i n i m u ma 1 1 o n e sp r o b l e mw i t hr e s t “c t i o n sf o rt r e e s i nc h 印t e r4w es t u d y 也en e wv a r i a t i o n so ft h ea l l o n e sp r o b l e ma n dt h ec o r r e s p o n d i n gm i n i m u ma l l o n e sp r o b l e m f o rm ev e n e x e d g ep r o b l e m ，w es h o wt h a ta 目a p hh a sas 0 1 u n o ni fa n do n l yi fi ti sb i p a r t i t e ，a n dt h e r e f o r ei th a so n l yt w op o s s i b l es 0 1 u t i o n sa n d 。p t i m a 】s 0 1 u t j o n s a1 i n e a rp r o g r a mv e r s i o ni sa l s og i v e n f o rt h e e d g e v e r t e x p r o b l e m ，w es h o w t h a t a g r a p h h a s as o h j t i o n i f a n d o n l y j f i cc o n t a j n se v e n n u m b e ro fv e r t i c e s b ys h o w i n gt h a tt h em i n i m u me d g e v e r t e xp r o b l e mc a nb ep o l y n o m i a l l yt r a n s f o m e di n t ot h em i n i m u mw e 蟾h tp e 彘c tm a t c h i n gp r o b l e m ，w eo b t a i n t h a tt h em i n i m u m e d g e - v e n e xp r o b l e mc a nb es o l v e di np 0 1 y n o m i a 1t i m ei ng e n e r a l t h ee d g e e d g ep r o b l e mi sr e d u c e dt om ev e n e x v e n e xp r o b l e mf o rt h e1 i n eg r a p ho fa g r a p h ， i nc h a p t e r5w ef l n dc w oa l g o r i t h m so f1 i n e a rt i m et os 0 1 v et h eg e n e r a l 盯a 1 1 ，o n e s p r o b l e mf o rt r e e s t h e 疗r s to n ej sg o o df o re n u m e r a t j n gt h en u m b e ro fs 0 1 u t i o n sj f s o l u t i o n sd oe x j s t ，a n dt h es e c o n do n ei sg o o df o rs o l v i n gt h em i n j m u m 盯a 1 】- o n e s p r o b l e m f u r t h e r m o r e ，w ec a nm o d i f yt h es e c o n da l g o r i t h ms l i g h t l yt os o l v ec h eg e n e r a lm i n i m u m 盯a 1 1 o n e sd r o b i e m k e yw o r d s ：( m i n i m u m ) 盯+ a 1 1 一o n e sp r o b l e m ，( m i n i m u m ) ( g e n e r a l ) 盯a 1 1 一o n e sp r o b 一 1 e m ，t r e e ，u n j c y c l i cg r a p h ，b i c y c l i cg r a p h ，g r a p ha l g o n t h m ，m i n j m u mw e i 曲tp e r f e c t m a t c h i n g ，1 i n e a rt j m e a m s s u b j e c tc i a s s i 6 c a t i o n ( 2 0 0 0 ) ：0 5 c 0 5 ，0 5 c 7 0 ，0 5 c 8 5 ，6 8 r 1 0 ，6 8 q 2 5 ，9 0 c 2 7 v i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：易廷晓岩 二g 年牛月o 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： i 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下 内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长每，爵少于l o 年) 机密2 0 年( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：蜀久晓岩 二占年牛月护日 c h a p t e r1 i n d u c c i o n c h a p t e r1 i n t r o d u c t i o n 1 1 b a c k g r o u n d s c e l l u l a ra u t o m a t aw e r eo r i g i n a l l yp r 叩o s e db yj o h nv o nn e u m a n na sf o m a lm o d e l so fs e l f _ r e p r o d u c i n go 唱a n i s m s ac e l l u l a ra u t o m a t o ni sad i s c r e t ed y n a m i c a ls y s t e m t h a tc o n s i s t so fa na r r a n g e m e n to fb a s i cc o m p o n e n t sc a l l e dc e l l st o g e t h e rw i 山at r a n s i t i o nr 【1 1 e a s s u m et h a tg = ( v e ) i sa 疗n i t ec o n n e c t e ds i m p l eu n d i r e c c e dg r a p h e a c h v e n e x ( c e i i ) a s s u m e so n eo ft h et w os t a t e s ，v i z 0o r1 a na s s i g n m e n to fs t a t e st ot h e v e r t i c e sw i l lb ec a l l e dac o n 6 9 u r a t i o nt h eb e h a v i o ro ft h ea u t o m a t o ni sd e t e m l i n e d b ya1 0 c a lt r a n s i t i o nr u l e ：t h es t a t eo fv e r t e x ( c e u ) a tt i m et + 1d e p e n d so n l yo nm e s t a t e so ft h ev e n i c e s ( c e l l s ) i nt h en e i 曲b o r h o o do f a tt i m et a sf 缸b a c ka sl9 4 8j o h nv o nn e u m a n ni n t r o d u c e dt h ei d e ao fat h e o r yo fa u - t o m a t ai nac o n f e r e n c ea tt h eh i x o ns y m p o s i u m ，s 印t e m b e r19 4 8 【3 4 】w h e nt h em i n d s w e r eu n d e rt h ei n 臼u e n c eo ft h et u n gm a c h i n e s 3 3 ，t h e 矗r s tn e u r a ln e t w o r k s 2 0 a n da l s om en a t u r a la n da m f i c i a la u t o m a t ao fc y b e m e t i c s 【3 6 t h et e mc e l l u l a ra u - t o m a t aw a si n t r o d u c e db yv o nn e u m a n n 3 5 】a saf o m a im o d e lo fs e i f r e p r o d u c i n g b i o l o g i c a ls y s t e m s k e yi d e a so ft h ec o n s t m c t i o nc a nb et r a c e db a c ke v e ne a r l i e r t oh i s t a l ko nm o d e l i n go fb i o l o g i c a ls y s t e m s 3 4 i nt h ep r e s e n te r a ，c e l l u l a ra u t o m a t aa r e b e j n gs t u d j e dh d mm a n yw i d e l yd i f f e r e n ta 1 1 9 l e sa i l dt h er e l a t i o n s h i po ft h e s es t r u c 一 1 c h a p 耐1i n t r o d u c t l o n t u r e st oe x i s t i n gp r o b l e m sa r eb e i n gc o n s t a n t l ys o u g h ta n dd i s c o v e r e d 1 0 ，1 5 ，5 ，3 9 w ef o c u so nt h et o p i cw h i c hi s 行n i t ea d d i t i v ec e l l u l a ra u t o m a t ao ng r a p h s ，i e ，c e l l u l a r a u t o m a t aw i t | la d d i t i v er u l e so nf i n i t eu n d i r e c t e dg r a p h s w es t u d yt h ec a s ew h e nt h e a d d m v em e sa r et w ow e u s t u 击e d1 0 c a lt r a n s m o nm l e s 矿一m l ea n d 盯一“es p e c j 枷y c 1 a s s i c a lc e l l u l a ra u t o m a t aw i t ht h e s em l e sw e r es t u d i e df o re x a m p l ei n 3 7 ，3 8 ，3 2 f o rc y c l e sa n dp a t h ss e e 1 9 ，2 6 】i n 1 7 】a u t o m a t ao nt r e e sw i t h 盯+ 一r u l ea r ei n t r o d u c e dr u l e s 仃+ a n d 盯a r ec a l l e dm l e1 5 0 a n d9 0 ，r e s p e c t i v e ly ，i n 3 7 0 n ei m p o r t a n t a r e ao f 印p l i c a t i o nf o rf i n i t ec e l i u l a ra u t o m a t ai si nv l s id e s 远n ；s e e 5 f o rd e t a i l so f 印p l i c “o n so fa d d i t i v ec e l l u l a ra u t o m a t at ov l s i a ni m p o n a n tp r o b l e mi n v l s i 印p l i c a t i o n si st od e s i g nan u l lb o u n d a r y9 0 1 5 0c e l l u l a ra u t o m a t ag i v e n a ni r r e d u c i b l eo rp n m i t i v ep o l y n o m i a l ，w h i c hi st h ec h a r a c t e r i s t i cp 0 1 y n o m l a lf o rm ec e l l u l a r a u t o m a t a t h ep m b l e mw a s 疗r s tm e n t i o n e di n 1 ，a n das 0 1 u t i o n 印p e a r si n 2 4 u s i n gav e r s i o no ft h el a n c z o st r i d i a g o n a l i z a t i o na l g o r i t h mo v e rg f ( 2 ) ac e l l u l a r a u t o m a t aw h e r et h ec e l l sc 柚h a v ed i h e r e n ts t a t es e t si sc a l l e dap 0 1 y g e n e o u sc e l l u l a r a u t o m a t a s u c hc e l l u l a ra u t o m a t o n sh a v en o tr e c e i v e dm u c ha t t e n t i o ne x c e p tf o rt h e w o r ko fh o l l a n d 4 t h ec a s ew h e r et h es t a t es e t so fa 1 1c e u sa r et h es a m ei st h eu s u a l o n e t h i ss e tc a nh a v ea na l g e b r a i cs t r u c t u r e f o rl i n e a rc e l l u l a ra u t o m a t a ，t h es t a t e s e ti su s u a l l yt a k e nt ob ean e l d 【19 ，m o u 曲c e l l u l a ra u t o m a t aw i t hs t a t es e t sz m ，山e i n t e g e r sm o d u l om ，f o ra r b i t r a r ym h a v ea i s ob e e ns t u d i e d 1 6 i nt h ev l s ic o n t e x t ， t h i ss e ti st a k e nt ob e o ，1 ) ，t h ef i e l do ft w oe l e m e n t s g i v e nt h ei n t e r e s t i n gt a r g e t c o n 行g u r a t i o nw h i c hi s 矗x e dt ob e1 ，t h ev e c t o rw i t ha l lc o m p o n e n t se q u a lt o1 ，w e s t u d y 行n i t ea d d i t i v ec e l l u l a ra u t o m a t ab a s e do n 盯+ 一r u l ea n d 盯一r u l eo ng r a p h si nt h i s t h e s j s w ec o n s i d e rl o c a lr u l e 盯o fav e r ys i m p l ea l g e b r a i cn a t u r e ：s t a t e sa r ee l e m e n t s o v e rg f ( 2 ) a n dt h en e x ts t a t eo fav e n e x ( c e u ) i st h es u mo ft h es t a t e so fa l ln e i 曲一 b o r i n gv e n i c e s ( c e l l s ) a n a l o g o u s l y ，f o r 盯+ 一r u l e ，t h es t a t eo fav e r t e x 口a tt i m et + l i st h es u m ( m o d u l o2 ) o ft h es t a t e sa tt i m eto ft h en e i g h b o r sa sw e l la st h es t a t eo f t h ev e n e x i t s e l f i f 义i sac o n 行g u r a t i o na tt i m et ，yi st h ec o n 6 9 u r a t i o na tt i m e + lb y 盯一o r 盯+ 一r u l eo ne v e r yc e u ( v e r t e x ) ，t h e nyi sc a l l e dt h es u c c e s s o ro fx ( w i t h r e s p e c tt o 盯o r 盯+ ) ，a j l dc o n v e r s e l y ，xi sap r e d e c e s s o ro fy o n eo ft h eb a s i cp r o b l e m 2 c h 印t e r li n t r o d u c n o n i nt h es t u d yo ft h ee v 0 1 u t i o no fc o n 6 9 u r a t i o n si st od e t e 功1 i n ew h e t h e fag i v e nt a 曙e t c o n 矗g u r a t i o nh a sap r e d e c e s s o r t h i sp r o b l e mi sr e f e r r e da st h ep 理d 已c 8 s s d r 蹦l j 把n c 已 p