UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Continual pattern replication Munro, James Ian 1969

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1969_A6_7 M85.pdf [ 2.31MB ]
Metadata
JSON: 831-1.0052022.json
JSON-LD: 831-1.0052022-ld.json
RDF/XML (Pretty): 831-1.0052022-rdf.xml
RDF/JSON: 831-1.0052022-rdf.json
Turtle: 831-1.0052022-turtle.txt
N-Triples: 831-1.0052022-rdf-ntriples.txt
Original Record: 831-1.0052022-source.json
Full Text
831-1.0052022-fulltext.txt
Citation
831-1.0052022.ris

Full Text

CONTINUAL PATTERN REPLICATION by JAMES IAN MUNRO B . A . , U n i v e r s i t y of New Brunswick,  1968  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in  the  Department of  Computer S c i e n c e  We accept t h i s t h e s i s as conforming to required  standard.  The U n i v e r s i t y o f B r i t i s h Columbia August,  1969  the  In p r e s e n t i n g an  this  thesis  inpartial  advanced degree a t the U n i v e r s i t y  the  Library  shall  make i t f r e e l y  I f u r t h e r agree tha for  permission  his representatives.  of  this  written  permission.  Computer  The U n i v e r s i t y o f B r i t i s h V a n c o u v e r 8 , Canada  Date  gain  September,  1969  Science Columbia  Columbia,  I agree  that  f o r r e f e r e n c e and study.  f o r extensive  copying o f this  thesis  by t h e Head o f my D e p a r t m e n t o r  I t i s understood  thesis f o r financial  Department o f  of British  available  s c h o l a r l y p u r p o s e s may be g r a n t e d  by  f u l f i l m e n t o f the requirements f o r  shall  that  copying o r p u b l i c a t i o n  n o t be a l l o w e d w i t h o u t my  ABSTRACT  This t h e s i s continues repeated g e n e r a t i o n of f i n i t e n i t e automata.  strings  Waksman handles  arithmetic" algorithm.  the s t u d i e s o f A . Waksman (1969) i n the  This is  i n a one d i m e n s i o n a l a r r a y of  t h i s p p r o b l e m by the use o f a "modulo shown to be v e r y r e s t r i c t i v e w i t h r e g a r d  to the number o f c h a r a c t e r s p e r m i t t e d i n the output s t r i n g . is  fi-  shown t h a t u n l e s s the l e n g t h o f the s t r i n g which i s  In f a c t ,  it  to be repeated  is  oc  of  the form p , where p i s  p r i m e , o n l y one output c h a r a c t e r i s  T h i s o f course makes the p r o c e s s For t h i s  reason,  quite  between i t  meaningless.  a new a l g o r i t h m i s  f e r r e d to as the wheel a l g o r i t h m , s i n c e  developed.  there i s  s t r i n g behind i t  This is  an obvious  and a w h e e l , w i t h the output s t r i n g on i t s  r o l l i n g alonggthe  permitted.  re-  analpgy  circumference  a r r a y and l e a v i n g the i m p r i n t of the c h a r a c t e r s i n the i n the same way t h a t a wheel l e a v e s t i r e t r a c k s .  The  number o f s t a t e s r e q u i r e d f o r such an a l g o r i t h m i s  l a r g e and so the b i -  nary wheel a l g o r i t h m i s  a l g o r i t h m , i n which  an output s t a t e i s  introduced.  By u s i n g t h i s  r e p r e s e n t e d as a s t r i n g of b i t s  i n several c e l l s ,  number of s t a t e s r e q u i r e d , i n a d d i t i o n to the n output s t a t e s , reduced to about 4  the  can be  n.  Both the wheel and b i n a r y wheel a l g o r i t h m s are then to the two d i m e n s i o n a l and f i n a l l y the d - d i m e n s i o n a l c a s e s .  extended  ii  TABLE OF CONTENTS Page I II III IV  Introduction  1  A More D i r e c t Method of D e t e r m i n i n g {bO  7  The V a l u e of ^  .  .  12  An A l t e r n a t i v e Method of C o n t i n u a l R e p l i c a t i o n of  V  .  Linear Patterns  — The Wheel A l g o r i t h m  E x t e n s i o n of the Wheel A l g o r i t h m to the  . . . .  2-dimensional  Case VI VII  E x t e n s i o n to the d - d i m e n s i o n a l Conclusion  22  . Space  . . . . . . .  31 44 46  iii ACKNOWLEDGEMENTS  I wish to  thank D r . R. S. Rosenberg f o r the guidance  a s s i s t a n c e which he extended to me i n the p r e p a r a t i o n of t h i s and  D r . A . Mowshowitz  f o r h i s h e l p f u l remarks i n p r e p a r i n g the  and  thesis final  manuscript. The Canada i s  f i n a n c i a l a s s i s t a n c e of the N a t i o n a l Research C o u n c i l of  also gratefully  acknowledged.  1. I  INTRODUCTION  In a recent of  finite  of  k symbols  p a p e r , Waksman (1969) uses a o n e - d i m e n s i o n a l  s t a t e machines represented  to model the c o n t i n u a l r e p l i c a t i o n of a sequence by the s t a t e s of the c e l l s of the a r r a y .  c o n t i n u a l r e p l i c a t i o n of a sequence of l e n g t h k we mean t h a t a p p r o p r i a t e l e n g t h of t i m e , {ik+1, i k + 2 , . . . ( i + l ) k }  array  dependent  on m, the subsets of  for i = l , 2 , . . . , m  s i r e d sequence of k symbols.  after  an  cells  w i l l each be r e p l i c a s  of the  Thus i f our alphabet were {0,1}  wanted to reproduce the s t r i n g of l e n g t h  By  de-  and we  4 (0111) c o n t i n u a l l y ,  after  an  a p p r o p r i a t e l e n g t h of time we would have {0111011101110111...} The p r i n c i p a l r e s t r i c t i o n on the t r a n s f o r m a t i o n to be performed is  that  the s t a t e of any c e l l a t time  of  that  cell  and i t s  (t+1)  two immediate neighbours  a method o f generating- c o n t i n u a l l y s t r i n g s d e s c r i b e d manner p r o v i d e d the c h a r a c t e r s structed  are chosen g  That i s ,  g^ i s  a f u n c t i o n of the at time t .  states  Waksman shows  of l e n g t h k i n the  previously  from which the s t r i n g i s  con-  from the r i n g of i n t e g e r s mod g^, ^ § k > where  = gcd{(^)}  k  is  i-l,2  k-1.  (1.1)  the g r e a t e s t common d i v i s i o n of the set  of b i n o m i a l c o -  k efficients  (^)  other  than those which are  The problem i s  1.  f o r m u l a t e d by Waksman as  Suppose we want to generate c o n t i n u a l l y the s t r i n g  follows: (a^}  t h e n , we s t a r t w i t h the i n i t i a l c o n f i g u r a t i o n c o n s i s t i n g transition state,  P , the next k c e l l s i n s t a t e s b^  o t h e r c e l l s i n the q u i e s c e n t s t a t e ,  Q.  It  i=l,2,...,k; of c e l l 0 i n a  i = l , 2 , . . . , k and a l l  can be seen that  the  relation  2. between the s t r i n g s a. =  I  and  b^  is  g i v e n by  (T"h b.  (1.2)  The a c t u a l method of c a l c u l a t i n g {b^}given {a^} plained l a t e r .  It  is  any c e l l  At time t , is  cell  s t a t e P and the time a f t e r  process i s , cell  i  it  i n state a  this state.  . at time t ,  t,i f o r i=l,2,...^kY we d e f i n e  t+l,i  where a c e l l  =  a  ,  a  t,i  +  a  To r e d e f i n e  the  T a b l e 1 which i n d i c a t e s  for  it  enters  A t each time s t e p the  cell  After this  The i n t e r e s t i n g  p a r t of  a c e l l e n t e r s the t r a n s i t i o n  has the  state.  w i t h the i n i t i a l c o n d i t i o n a„  .=b.  t,i-l  1  . by JX  ,  i n the q u i e s c e n t s t a t e i s  the t e r m i n a l s t a t e .  The p r o c e s s  o,i CTJ,  -'  the  enters statePP.  retains  transition  two segments, the' time b e f o r e  t h e n , what happens b e f o r e  is  a  it  i n the  r i g h t hand neighbour exchange s t a t e s .  happened to a c e l l ,  If  t o n l y w i l l be i n s t a t e P .  b a s i c a l l y broken i n t o  i n s t a t e P and i t s  ex-  to be understood t h a t a l l a r i t h m e t i c w i l l be modulo  At each time step one and o n l y one c e l l i s state, P.  w i l l be  (1.3) c o n s i d e r e d to be i n s t a t e  0.  f u n c t i o n i n a more formal manner we may  follow  the t r a n s f o r m a t i o n up to the time of e n t r y  To r i g o r o u s l y d e f i n e  c e l l s as h a v i n g an a d d i t i o n a l f l i p  the  f u n c t i o n we may t h i n k of  f l o p which i s  neighbour of a c e l l e n t e r s s t a t e P . aAt t h a t  into  off  u n t i l the  time the f l i p  flop  t u r n e d on and no f u r t h e r change can o c c u r i n the s t a t e of the  is  cell.  right  3. •TABLE 1* Flip Q = P = $ = a. =  flop i n position 0 quiescent s t a t e transition state no c e l l present ( l e f t neighbour o f c e l l 0) an element of Ze,  * The output g i v e n i n t h i s and a l l s i m i l a r t a b l e s i s time t+1.  at  R i g h t neighbour c e l l state time t  at a. l  a  Left neighbour  k  a  P  i  + a  k  P  a  i  \  +  P  R i g h t neighbour Left neighbour  R i g h t neighbour  Q  a.  Left neighbour  Q Q  a.  No o t h e r c o n f i g u r a t i o n s  can o c c u r .  Thus i f we i n i t i a l i z e  the  a r r a y as p r e v i o u s l y mentioned and f o l l o w the t r a n s i t i o n of T a b l e 1, c e l l 0 w i l l enter  the t e r m i n a l s t a t e a^, c e l l 1, h^+b  c e l l i-1 e n t e r s t e r m i n a l s t a t e i E (. ^) b . = a_^ (by e q u a t i o n j=l ~ 2  a t time t = i .  3  = a^ and i n g e n e r a l  1.2)  1  Out problem i s now to c a l c u l a t e { b } f o r a g i v e n set { a}  Waksman found t h a t { b .} manner.  2  L e t a, .=a. li I  c o u l d be generated i=l.,2,...,k '  '  from { a.}  and w r i t e a  i n the  .a.„ . . . a  11 12 l T  following lk 1 7  .  Then  .  4. complete  a k x k m a t r i x by a  and  letting  . = a + a mj m-l,jvm-l,j+l  m=2,3,...,k . , * ' *  1  a , = a , , = a, mk lk k  (1.4)  The a r i t h m e t i c i s process  is  peated,  or that  of course mod g^.  c o n t i n u e d f o r m = k+1, a m  ^ ] o c  is  due to the f a c t  is  essentially  j  c  that  =  a m  k+2,...,  j  a  =  a n  y  Waksman shows t h a t  the  and t h a t the m a t r i x i s  re-  tue p o s i t i v e  the a r i t h m e t i c i s  integer.  done modulo g^.  Thi$ property  This  process  what happens i n the a c t u a l g e n e r a t i n g machine b e f o r e  P state is  entered.  stationary  instead  The o n l y d i f f e r e n c e of moving to the  is  t h a t the k - t u p l e  remains  right.  A f t e r the k x k m a t r i x has been formed the c a l l e d the f i r s t  the  t r a n s p o s i t i o n column.  first  T h i s column i s  column w i l l be  taken as an i n i -  t i a l i z i n g row f o r a second m a t r i x formed i n the same manner, and hence the  first  column of t h i s m a t r i x i s  Waksman shows t h a t i f column w i l l be the s e t  c a l l e d the second t r a n s p o s i t i o n column.  g^ such m a t r i c e s are formed the g^th {a.}.  T h e r e f o r e the f i r s t  transposition  row of the g, t h m a t r i x , K.  X  o r the  ( g , - l ) s t t r a n s p o s i t i o n column generates {a.}  ponding to t h a t of the  generating  function.  i n a manner c o r r e s -  Hence the  (g^-l)st  trans-  p o s i t i o n column may be taken as {b_^}. A n u m e r i c a l example may make t h i s p r o c e s s Suppose we are fo generate {021}  continually,  somewhat  so k=3 and  Then w r i t e 0 2 1  and f o l l o w  formula (1.4)  3-1=2  times  clearer*  5. (1)  0 2 1 2 0 1 2  (2)  0 2 2 i s the f i r s t  transposition  11  0 2 2 0 2 0 i s the second 2  column and so  To check t h a t or third  transposition  12  0 0 2  the  column  0,2,0 '  '  =  b. l  {0,2,0} w i l l indeed produce {0,2,1} we s h a l l  form  matrix.  (3)  0 2 0 2 2 0 12  We see then, t h a t the p r e v i o u s l y  0 the d e s i r e d  mentioned f a c t  sequence {0,2,1} i s produced.  To i l l u s t r a t e  t h a t i f t h i s p r o c e s s i s c o n t i n u e d the e n t i r e  m a t r i x w i l l be r e p e a t e d , and so t h e g ^ t h t r a n s p o s i t i o n column w i l l be r e peated we s h a l l c o n t i n u e a few more time s t e p s .  •  12 0 0 2 0 2 2 0 12  0  0 2 0 2 2 0 12 0  02.2 0 2 2 0  6. We s h a l l now s t a r t  the g e n e r a t i n g f u n c t i o n w i t h  {b^}={0,2,0}  TABLE 2  0  1  2  3  4  5  6  7  8  0  P  0  2  0  Q  Q  1  0  P  2  2  0  Q  2  0  2  P  1  2  0  Q  -  0  2  0  Q  0  P  2  2  0  1  0  2  P  1  2  - - - - Q - 0 Q -  3  0  2  1  P  4  0  2  1  5  0  2  6  0  2  1  0  2  1  P  0  2  0  Q  7  0  2  1  0  2  1  0  P  2  2  0  9  10  A f t e r time s t e p 3 we note t h a t the d e s i r e d sequence has been generated once and t h a t the " g e n e r a t i n g bud" i s the same as i t was when initialized.  Thus we see t h a t the p r o c e s s w i l l work.  An important c o n s i d e r a t i o n i n j u d g i n g the m e r i t o f such a scheme is  the number o f s t a t e s r e q u i r e d .  Waksman r e q u i r e s the f o l l o w i n g  1  Q the q u i e s c e n t  1  P  2.g^  the i n t e g e r s from 0 to (g^-1) and a l s o a f l i p  states:  state  the t r a n s i t i o n s t a t e flop to  i n d i c a t e whether a c e l l has e n t e r e d i t s t e r m i n a l s t a t e or n o t . This gives a t o t a l  o f 2(g^+l) s t a t e s ,  as output c h a r a c t e r s .  t h a t i s about t w i c e as many s t a t e s  Another method o f c o n t i n u a l g e n e r a t i o n of s e -  quences w i l l be i n t r o d u c e d i n Chapter 4 and at t h a t  time i t w i l l be  useful to compare the number of states required for the present method and the one introduced at that time.  II  A More Direct Method of Determining {b_^}  Once {b_^} has been determined and the generating been i n i t i a l i z e d  function has  the generation of a^'s i s straight forward.  The process  occurs as fast as can be expected f o r such a structure; that i s , one new output c e l l per time step.  The generation of {b^} by Waksman's method  i s , however, very tedious, expecially i f g^ i s f a i r l y large.  Fortunately  i t turns out that the method i s somewhat i n e f f i c i e n t and that {b_^} may be determined d i r e c t l y , rather than by i t e r a t i v e procedures, from {a_^}. Consider the following discussion: Recall equation 1.2 i ., a.1 = S (T~:) b . . J-1 3 J=l  •1  J  J  Rewriting this i n vector-matrix a  l  notation, we have:  io  1 (2.1)  or a = A b We want to express b i n terms of a. 2.1 to y i e l d  This may be done by rewriting equation  8. Our problem i s  1  now s i m p l y to i n v e r t A .  We s h a l l show t h a t :  0 ...  -1 1 1 A"  1  = A  1  1  =  uj:i)(-D  1 + j  } 0  (-l)  k + 1  k(-l)  k + 2  k(-l)  -1  To express t h i s s i m p l y i n words, A A , however  the  (k,j)th  (-1)"''^. A more u s e f u l  element has the s i g n of  +  Theorem 2.1  1  =  E  d"h(-l)  j-1  i + J  a,. j  To prove t h i s theorem we need the f o l l o w i n g lemma: Lemma 2.11  m=j l  E m=j  (i-l)! (m-l)!(i-m)!  (m-1) ! (j-l)!(m-j)!  (-D  1  has the same elements as  way of w r i t i n g t h i s r e l a t i o n would be as Theorem 2.1.  b.  2 k _ 1  m  9. (i-l)-(j-l)=i-j (i-j)-(m-j)=i-m l e t k = m-j h =i-j  =  <-l) (J" ) j  "  By expanding (1-1) h 2  k=0 and  (h(-D  S  1  J  k=0  i  k  K  we note t h a t  . C)(-l) = 0 K  hence  QED We a r e now ready to prove the theorem. P r o o f o f Theorem  2.1 f  1-1 (. ) f o r i=l,2,...,k n  j=l,2,...,l  L e t a. . ="S  0  f o r 1=1,2,...,k  j=l+l,...,k  T h i s d e f i n e s the m a t r i x A = {a..}. S i m i l a r l y we d e f i n e f/ -lw_iN :J <;_?<-i>i  a'..  i +  H l — l y 2 j • i«jk  and so d e f i n e A  v  = {a ;.} 1  13  2™* 1*^*1 > • • • >k  10. Then from the d e f i n i t i o n of  {b }. i n e q u a t i o n 1.2, we have  shown t h a t a = A b . What we are to prove i s  b. = 1  Z  d"h(-l)  j-1  that  a.  i + j  2  2  or that b = A ' a . That means A  -  = A ' or that AA'=I.  1  L e t AA' = { « . . }  then « . . = ii J  k Z a. a'. im mi m=l  i  J  We s h a l l show t h a t <*.. =1 and t h a t « . . = 0 i f i ii ij c o n s i d e r i n g the t h r e e cases (i) i < j  (i)  i  (ii)  1= j  (iii)  i > j  1  t r i a n g u l a r , therefore a. =0 f o r m = i + l , . . . , k • im i s t r i a n g u l a r , therefore a ^ = 0 for m=l,2,...,j-1  Therefore a. a'. = 0 f o r m=l,2 (j-1) im mj and f o r m = ( i + 1 ) , . . . , k and as i  < j a . a . =-0 im mj J  Hence « . . = 0 (ii)  ^ j , by  < j  A is A  ;  for i  f o r m=l,2,...,k ' ' ' < j .  i = j A g a i n we have a. =0 im a'. = 0  for  m=i+l,...,k  f o r m=l,2,...(j-1)  11, but as i = j  we have  a. a'. = 0 im mj  for m ^ i  therefore  . = a., ii  11  a!. ii  but a . . - ( ? - b - l ii l-l a  i i = (i:i)(-D  therefore (iii)  =i  2 i  <=. . = 1  i > j a g a i n a. =0 im a'.  for i = j  f o r m=(i+1) , . . . , k  = 0  for  therefore  = 0 '  Hence « . . = ii  m  (-D  m  m  for m = l , . . . , j - l and m= (i+1) , . . . , k  -'  E a. a . = E a. a . , ". im mi . im mim=l m=j • •  J  m=j  m=l,...,(j-l)  J  _  d  1  2  E  ~  1  c b e ' i ^ m—1 i-1  1  )  1  1  1  m=j  by lemma 2.11  0 Therefore  . = 0  u Hence  j-l { 0  .. = ij  So AA' = I thus b . = 1  for i  > j .  if i = j otherwise  n  o r A' = A  -  E (T"b(-l) J-l J" 1  1  i + j  a. J  QED  12. R e c a l l i n g the example at the end o f chapter I we s h a l l now recalculate  {b.} g i v e n {a.}  =  {0,2,1}  k=3  Su ^ =  By theorem 2.1 - l  h  (Jiix-i) *., 1  3 —1 so b  l  *  a  l - °  b  2  = a  2  -  b  3  = a  3  - 2a + a  &  1  = 2 2  1  = 1 - 2(2) + 0 = 0  Hence we have {b^} =  {0,2,0} which agrees w i t h the v a l u e  c a l c u l a t e d by Waksman's method.  I t i s easy to see t h a t when k i s  f a i r l y l a r g e Waksman's method i n v o l v e s (g, - l ) k ( k - l )  (mod 3)  a great d e a l o f c a l c u l a t i o n —  additions.  The method which we have j u s t developed i s k much more d i r e c t , r e q u i r i n g l e s s than E 2 ( i - l ) a r i t h m e t i c o p e r a t i o n s . k  i=l That i s l e s s than 2*  1  * k = k(k-l)- arithmetic operations.  method i s b e t t e r by a f a c t o r g^.  F o r the e n t i r e p r o c e s s  The  to have any  meaning g^ must be a t l e a s t 2.  Ill  The Value o f  ^  g.^ i s e s s e n t i a l l y  the number o f c h a r a c t e r s p e r m i t t e d i n the  alphabet over which the s t r i n g i s generated by the Waksman t e c h n i q u e , since  t h e r e a r e g^ elements i n ^g^* Waksman says n o t h i n g more about the s i z e o f the a l p h a b e t ,  which the c h a r a c t e r s to be generated may be chosen, g, rC  as g . c . d { ( ) } k  X  i=l,2,...,k-l.  from  other than to d e f i n e  As i t turns o u t , upon c l o s e r  13. investigation, put of  g^ i s 1 u n l e s s k i s a prime or a power of a p r i m e .  i t even more s i m p l y , g^ i s  i n g e n e r a l 1 and so the Waksman technique  g e n e r a t i n g sequences c o n t i n u a l l y i s meaningless  cases o f k .  F o r to generate  To  except  in special  a s t r i n g o f any l e n g t h w i t h o n l y one c h a r a c t e r  c o n t i n u a l l y i s merely to generate  this  one c h a r a c t e r c o n t i n u a l l y .  To prove the r e s u l t we have j u s t s t a t e d we must f i r s t prove s e v e r a l lemmas. First, f a c t o r o f x.  d e f i n e N '(x) as the number of times p  Hence N2(12)=2, N,-(17)=0 et c e t e r a ,  N (xq)=N (x)+N (y) p  p  when x#),  p  the prime p i s a  It  is quite  y#).  Lemma 3.11 N (i+kp )=N ( i ) P P  f o r 1=1,2  e  or i f  i=p  3  and  (p -l) 3  p ^(k+l).  Proof  Let  i = mp  so  N (i+kp ) P 3  But  as  then If  p^m  pVi» N  (i+kp )  a  B  But,  e  C  = <*+N (m+kp "") P 3  )  = cc = N ( i ) p  on the o t h e r hand, i - p N (i+kp ) P  a  = N (p (m+kp "° )) P  P^On+kp^ 3  p  then 0<_<3  3  f o r 1=1,2  and p. ^(k+1) we have  = N ( ( k + l ) p ) = 3 + N (k+1) P P e  as  J?Vk+l) N (i+kp ) P 3  = 6 = N (i) P QED  (p -l) S  clear  14. Lemma  3.12 cc  (ps!) =  N  Z p J-1  P  j  _  1  Proof: We s h a l l prove t h i s obviously  lemma by i n d u c t i o n on  t r u e f o r « = 0 and f o r  f o r " ^ B and prove i t  r : a  f o r <*=8+l.  =l.  First,  it  We s h a l l assume the lemma i s  Hence by i n d u c t i o n the lemma w i l l  is true be  true. Assuming N (p  8  i 1 E (p) w r i t e out j-1 shown. 3  !)  =  P  divide i t  i n t o p s e c t i o n s as p^+D,  .  1  f  .  2  —  ^ I (p. +l)  . . . 2p |  B  m  m  t  P  ...  6  (p  8+1  1) i n f u l l  |((p'-l)p +l)' e  and  ...p-  Now by lemma 3.11 we know t h a t N (i+kp )  = N (i)  B  p  for i = l , 2 , . . . , p  p  and a l s o f o r i = l , 2 , . . . (p --1)  e  when k = 0 , 1 , . . . <p -2)  when k = p - l .  - 8 Furthermore when i=p  and k = p - l  N (i+kp ) = N ( ( p - l + l ) p ) P P B  Thus p i s  B  = N (p P  B + 1  )  = 8+1 = N ( p )  +1  P  a f a c t o r of each of the s e c t i o n s shown, except the l a s t ,  same number o f t i m e s ;  and i s  the  a f a c t o r o f the l a s t one more time than of g  the o t h e r s .  section  is p  1-1  3  E  However, the f i r s t  (p  J  )  times.  j=l Thus  N P  (p  (  3  +  1  )  !)=P  E j-1  (p  J _ 1  )  + 1  ! , and so p i s  a  factor  15. T h i s lemma may be extended to g i v e the v a l u e o f N ( r ! ) where p  r is  not n e c e s s a r i l y a power of p .  Lemma  3.13 N ((p'x)!) P  = xN (p"!) P  + N (x!) P  Proof: C l e a r l y the lemma i s the lemma i s  true for x=l.  t r u e f o r x=y and prove i t  We s h a l l t h e r e f o r e  f o r x=y+l.  assume  Hence by i n d u c t i o n  the lemma w i l l be t r u e .  cAy+D)!  =  • (i+P°V)- ... -(y+D"  (P°V)!  = (P°V)I * n (i+P°V) 1=1 By lemma 3.11 N  p  (i+p°V)  = N (i)  and  N  then  N ((p°(y+l)!) P  p  for i=l,2  p  (p'-l)  (p^+p^y) = <* + N (y+1) = N ( p ° ) p  p  + N (y+1)  = N ((p°V)!) + N (p*!) P P  p  + N (y+1) P  ( u s i n g the i n d u c t i o n assumption) - y N ( p ! ) + N ( y ! ) + N (p*!) a  p  = (y+1) [ n o t i n g t h a t N ((y+1)!) = N (y!) P P  p  + N (y+1)  N ( p ! ) + -N ((y+1)!) a  p  + N (y+1)] P  QED Lemma  3.14 If  k = p x, where p 1 x,  x > 1 and p i s  \  prime,  then P ^ g, .  16. Proof;  g  = g.c.d{(J)}  k  1=1,2  (k-1).  To show p ^ g^ we need o n l y f i n d one i such t h a t p \  (^).  • cc  C o n s i d e r the case i n which i = p . P x us e v a l u a t e N (( )) P P a  Let  Since  (?cc ) -  (p x!) P « ! (( x - l ) p « ) ! g  x  V  '  . CC we have N  (<f- )) ^  tr  but  - N (( p ' x ) ! )  X  - N (p*!)  - N  Jr  r  (((x-l)p!)  tr  then N ((p P  x)!)  OC  N (p^!)  " 1-1 E p + N J-l ?  E pi""  =  CC  N (((x-l)p")!)  E p  j  E p  = x  X  j  -  -  1  =  N (x!)  J  -  1  1  (x-1)  J-l  + N ((x-1)!)  1  P  + N (x!) P  E p^" j - l  1  - N ((x-1)!) P  - N ( ( x - 1 ) ! ) + (x-1 - ( x - 1 ) )  P  N (x) p  ^  g  - N ((x-1)!) P =0  E pi" J-l  P  N (x!) P  p  -  and 3 , 1 3 .  N ((?« )) P V  -  Hence  j  J-l  from lemmas 3.12  =  E p  = (x-1)  P  Then  (x!)  1  J-l  P  and  = x  as p |  x  k QED  1  17. With the p r o o f of  t h i s lemma the d e s i r e d r e s u l t  follows  easily. Theorem  3.1 k I f k ^ p , g,  are r e l a t i v e l y  = 1,  or the elements o f  {(.)}  i=l,2,...(k-1)  prime.  Proof: k =  k  k C {( )}» i  hence g  | k.  fc  Then f o r every prime p which d i v i d e s factor of k i s  a f a c t o r of g^..  k , a p p l y lemma 3 . 1 4 .  Then, s i n c e g^ | k ,  Hence, no  g^ = 1.  QED cc  L e t us now c o n s i d e r s i z e of  the alphabet  the case i n which k = p  permitted i n generating  l e n g t h k by Waksman's method.  and determine  the  c o n t i n u a l l y a s t r i n g of  We can see by the f o l l o w i n g Theorem t h a t  i n t h i s case g^ = p. Theorem  3.2 I f k = p , where p i s prime and « >_ 1,  then g^ = p .  Proof: By the d e f i n i t i o n of  g^,  it  must be a f a c t o r of k .  Hence,  cc  this case,  g^ = p , where 0 <_ 3 <_ We s h a l l show t h a t  secondly  that 1)  g^ = p by showing f i r s t  that  3 >_ 1 and  3 <_ 1. We a r e to show 3 >_ 1, Consider f i r s t (P -i)*(p -i+l) a  of the  a  the ...  that  i s , ,p |  g^.  term (P^-l)  form of the product of i  which consecutive  is integers  in  18. d i v i d e d by i ! . i!  d i v i d e s the product o f any i  integers.  (p - i ) ( p  (  P is  consecutive  cc  -  -i+1) i!  d e f i n e d and  I f we r e p l a c e  ...  (p -1)  positive  )  0. cc  (p - i ) ,  cc  i n the term, by p , c l e a r l y cc  v a l u e of N w i l l be i n c r e a s e d as N (p - i ) P P 1 < i  (1945),  Hence  cc  N  By Theorem 74 o f Hardy and Wright  <  the  cc  < N (p ) P  for  < p".  Then N ((?")) - N p i p  >  N  p  (  -(p"-i+l)- ;--(p^l)'p") l! :  ( (p'-D (p'-l+D  '(p'-l) \  i!  > 0. Thus  N ((?))> P  1. QED  1  We s h a l l now show t h a t  6 <_ 1 and so t h a t  C o n s i d e r now the case i n which i = p ,  1  g^ = p . and so the member  p (P  )  p !  =  (P  ) ! (p - P  )!  Therefore,  N  P  [(  ,)] p^-l  P  - N (p"l) P  - N (P"" !) P 1  - N ((p"P  P"" )!) 1  19. N  where  (P !)  Pj - 1  Z  =  J-1  P  cc_l N (p" !) _ 1  Z  =  P  j  -  1  J-1  P  N ((P."- p" ) ! ) P  - N ((P™ P  X  ( P - l ) ) !)  - 1  cc—2. = (P-l)  cc P  Z  j  _  + N  1  j-1 as P ^  (P-l)  = (P-l)  p  Z  j  -  1  j-1  P  (P-l)  Therefore . cc  N  [( P  a  )]  P  P "  =  Z  cc— 2_  P  j  _  1  -  j-1  1  cc—J_  P  Z  j  _  1  -  (P-l)  j=l  P  j  _  1  j=l «-l  = l + ( P - l -(P-D)  Z  s  . ,  p  J  _  1  j-1  = 1 cc  Hence  = P where k = P QED  We can now see  the f u l l  c o n t i n u a l r e p l i c a t i o n of  strings.  k,  is  i m p l i c a t i o n s o f Waksman's method o f If  the l e n g t h o f the d e s i r e d s t r i n g ,  a p r i m e , P , or a power of P ; then the a l p h a b e t from which the  elements o f k may be chosen i s b i j e c t i v e c o n s i s t s of a s i n g l e  to Z^.  Otherwise the  alphabet  c h a r a c t e r and hence no meaningful s t r i n g can be  generated. As an example, note  that t h i s  let  us generate  the s t r i n g (120222101).  can be done u s i n g Waksman's technique as k=9 hence  We 8^-3.  The c a l c u l a t i o n  of  {b.}  is  c a r r i e d out i n T a b l e  TABLE 3 Pascal's  Triangle  The b i n o m i a l c o e f f i c i e n t s j  -*•  0  1  2  3  k  5  6  ("!")  7  0  1  1  1  1  2  1  2  1  3  1  3  3  1  1  4  6  4  1  5  1  5 10 10  5  1  6  1  6 15 20 15  6  1  7  1  7 21 35 35 21  7  1  8  1  8 28 56 70 56 28  8  4.  21. TABLE 4 Calculation of  {b.} 1  R e f e r to TABLE 3 f o r {a }  b-i  =  l  =  1  b  2  b  3  b, b  4l  5  1  = {1,2,0,2,2,2,1,0,1}  ±  b  C^"" )  ~E j=i  ) ( - 1 ) ? a. J 1 +  J  x  a r i t h m e t i c i s mod;g, °k  1  =2-1=1 = 0 -2(2)  + 1 = 0  = 2 - 3 ( 0 ) + 3(2) - 1 = 1 =2  - 4 ( 2 ) + 6(0) - 4(2) +1 = 2  b,, b  = 2 - 5 ( 2 ) + 10(2) - 10(0) + 5(2) - 1 = 0  b  ?  = 1 - 6 ( 2 ) + 15(2) - 20(2) + 15(0) - 6(2) + 1 = 1  b  g ;  = 0 - 7 ( 1 ) + 21(2) - 35(2) + 35(2) - 21(0) + 7(2) - 1 = 0 = 1 - 8 ( 0 ) + 28(1) - 56(2) + 70(2) - 56(2) + 28(0) - 8(2)  With (b^} determined we may proceed w i t h the c o n t i n u a l of  the sequence under the r u l e s o f TABLE 1.  + 1 = 2  generation  22. TABLE 5 G e n e r a t i o n of the sequence cell  (120222101)  i -»•  0  1  2  3  4  5  6  7  -8  9  <!°  P  1  1  0  1  2  0  1  0  2  Q  Q  Q  1  P  2  1  1  0  2  1  1  2  2  Q  Q  2  1  2  P  0  2  1  2  0  2  0  1  2  Q  Q  3  1  2  0  P  2  0  0  2  2  2  1  0  2  Q  Q  1  2  0  2  P  2  0  2  1  1  0  1  2  2  Q  Q  5  1  2  0  2  2  P  2  2  0  2  1  1  0  1  2  Q  Q  -  - —' -  6  1  2  0  2  2  2  P  1  2  2  0  2  1  1  0  2  Q  Q  -  -  -  7  1  2  0  2  2  2  1  P  0  1  2  2  0  2  1  2  2  Q  Q  -  -  8  1.  2  0  2  2  2  1  0  P  1  0  1  2  2  0  0  1  2  Q  Q  -  9  1  2  0  2  2  2  1  0  1  P  1  1  0  1  2  0  1  0  2  Q  Q  10  1  2  0  2  2  2  1  0  1  1  P  2  1  1  0  2  1  1  2  2  Q  0  1  After  12  the 9th time step we n o t i c e  been generated once and t h a t c e l l s 10-18.  11  At t h i s  13  14  15  16  that  18  t h a t the p a t t e r n  the i n i t i a l c o n f i g u r a t i o n  p o i n t we see  17  the p r o c e s s w i l l  b_^  19  a^  20  has  i s now i n  clearly  generate the d e s i r e d sequence c o n t i n u a l l y .  IV  An A l t e r n a t i v e Method of C o n t i n u a l R e p l i c a t i o n of L i n e a r P a t t e r n s  -  The Wheel A l g o r i t h m  It  is  c l e a r t h a t Waksman's method i s v e r y r e s t r i c t i v e  with  r e g a r d s to the a l p h a b e t p e r m i t t e d i n c o n t i n u a l g e n e r a t i o n o f a sequence  23. of  arbitrary length.  of  his  It  is  a l s o q u i t e c l e a r t h a t no simple m o d i f i c a t i o n  "modulo a r i t h m e t i c scheme" can be g e n e r a l i z e d  degree.  For t h i s  to any  significant  reason we now t u r n to a more g e n e r a l method of  repli-  2 cation.  T h i s method, i n i t s  however,  r a t h e r than 0(n)  of  the a l p h a b e t  elementary  form,  r e q u i r e s 0(n )  as d i d Waksman's method, where n i s  from which the c h a r a c t e r s are chosen.  be m o d i f i e d somewhat  states,  so t h a t  the  size  T h i s method may  the number o f s t a t e s r e q u i r e d i s  about  n + 4 log2 n and so l e s s than the 2 n+2 r e q u i r e d i n Waksman's method for  reasonably large n . The  idea behind t h i s  g e n e r a l scheme i s  quite simple.  the s t a t e of each c e l l as a p a i r of elements o f the d e s i r e d 3. C e a l p h a b e t — say as p o s i t i o n s  [^]  [^]  [^].  Then t h i n k of t h i s  six-tuple  ID  p o s i t i o n of the wheel w i l l be [^] position(initially  that  output  of  states  on a wheel r o l l i n g to the r i g h t , and so c l o c k w i s e .  the a l g o r i t h m may be r e f e r r e d to as the wheel a l g o r i t h m .  behind i t  Write  as i t  o c c u p i e d by [^],  rolls,  Hence  The next  C  EL  [^]  [ ]•  that i s ,  Now suppose b i s  left  i n the  the wheel l e a v e s a t r a c k  the image o f the bottom p a r t which was l a s t  in  position. a [^]  Using  c e [^] [^]  as an i n i t i a l c o n f i g u r a t i o n we have TABLE TABLE 6  Q b  #  [*]  [  ]  [fl  b d [ ]  *Q [°J Q  [\]  d  f  b d f  f  [] e f  []  Q  a  [] c d  [ ] a b  Q  6.  24. From t h i s i t  can be seen the sequence  generated c o n t i n u a l l y . initial  Thus to generate  a,b,c,d,e,f  manner around the wheel —  noted t h a t t h i s method i s  f e d [ ] [ , ] [ ] • a b c  is  to be r e p l i c a t e d  a sequence of even l e n g t h .  it  The g e n e r a l  and the of  the  the c e l l  The top h a l f  to i t s  except at the ends.  the  right  The lower h a l f  does not move two  but moves to occupy the bottom h a l f of the c e l l  occupied  time  but a l s o moves to occupy  occupied c e l l  r i g h t which was p r e v i o u s l y  right-most  at  the  r i g h t , which then becomes the l e f t m o s t  of the r i g h t - m o s t  to the r i g h t ,  the  stays i n p o s i t i o n ,  twice  c b a [ ] [ , ] [ ]. a. D c  moves two p o s i t i o n s to  left-most p a i r stays i n p o s i t i o n ,  top h a l f o f  to i t s  the c e l l  length.  continually  r u l e f o r d e t e r m i n i n g the s t a t e of a c e l l  t h a t the upper h a l f o f lower h a l f  I t may be  may be w r i t t e n  Thus to generate  [abcj the a p p r o p r i a t e i n i t i a l c o n f i g u r a t i o n would be  is  appropriate  d i r e c t l y a p p l i c a b l e to sequences of even  a sequence of odd l e n g t h  and c o n s i d e r e d  t+1  the  w i l l be  c o n f i g u r a t i o n would be o b t a i n e d by w r i t i n g t h i s sequence i n a  counter-clockwise  If  b,d,f,e,c,a  cell.  positions immediately  i n the q u i e s c e n t s t a t e , but now becomes  cell.  T h i s p r o c e s s v i o l a t e s one o f the r u l e s which Waksman had s t a t e d . That i s w i t h the wheel a l g o r i t h m the depend,  i n general,  on the  moves two p l a c e s to the t h i s problem r e q u i r e s  s t a t e of c e l l  state of c e l l  right)  at  i-2  time t .  (the  at time t+1  will  top h a l f of the  cell  To modify the scheme and a v o i d  the i n t r o d u c t i o n of a time f l i p - f l o p  e s s e n t i a l l y d o u b l i n g the number o f s t a t e s .  and so  This f l i p - f l o p w i l l  b e i n g 0 at even time s t e p s and 1 at odd t i m e s . pair representation  i  alternate,  The upper h a l f o f  o f a c e l l w i l l move 1 p o s i t i o n  to the r i g h t at  the each  25. time s t e p . time.  The ends w i l l be handled by a p p r o p r i a t e  TABLE 7 f o r m a l l y d e s c r i b e s the  means  function.  TABLE 7 a,b,c  output  0 -  an a r b i t r a r y  Q  -  quiescent  [] b  -  generating  $  -  —  X  -  _  a  L  J  -  -  no  characters character  state pairs  c e l l present  any  character  R i g h t Neighbour Present State  X(t=0)  X(t=l) [] b 6  L  Left Neighbour  'Si  J  g  b  $  b  a  X  $  a  b  a  Q  Q  a  a  -  t=l  ;.Q  t=G  depending on  26. To i l l u s t r a t e t h i s , It i s  c o n s i d e r the f o l l o w i n g example:  d e s i r e d to generate  c o n t i n u a l l y the p a t t e r n febcbj. Then  we have:  t=0  V a  c b  0  0  I n i t i a l configuration (the bottom symbol i s a time  Q  flip-flop)  t=l  a  t=2  a  b  c  w  \\  a b  V c  a  fo]  a c  b  b  W a  w  f -\ a b  b c  t=4  b  substituted  Q  loj loj t=3  Note t h a t any s t a t e c o u l d be f o r the dummy s t a t e 0  Q  0 t=5 a  b  c  0" a 1  w b w f  t-6 a l'/b  c  c b  '  b a  Loj loj t  t=7 a  b  c  b  i c a  w  One s l i g h t  f  0 b  \  w  drawback to t h i s method i s  r e q u i r e d to generate each new output c h a r a c t e r . 2 r e q u i r e d can be seen t o be 0(n )  as:  t h a t 2 time s t e p s are The number o f  states  s t a t e s are r e q u i r e d f o r a l l p o s s i b l e p a i r s of outputs and time  flip-flop.  n  output  1  Q, the q u i e s c e n t  2 2n +n+l  states  states is  state  the t o t a l number r e q u i r e d .  I t s h o u l d be noted t h a t the number o f s t a t e s r e q u i r e d totally  is  independent o f the l e n g t h of the s t r i n g to be r e p l i c a t e d . The next q u e s t i o n to be asked i s  can the number of s t a t e s r e -  2 q u i r e d be reduced from 0(n ) to 0 ( n ) ,  perhaps at the expense o f the  time  r e q u i r e d f o r g e n e r a t i o n o f each output c h a r a c t e r ? The b a s i c schemexof  this algorithm is  to r e p r e s e n t each output  s t a t e as a b i n a r y number and so o n l y p a i r s of b i n a r y d i g i t s lated.  T h i s mapping i s  to ]L^.  As i t  takes  a r e manipu-  an a r b i t r a r y b i j e c t i o n from the output alphabet  l o g n* b i t s  to r e p r e s e n t u n i q u e l y the i n t e g e r s  of  a time c o u n t e r r u n n i n g from 0 to l o g n w i l l be r e q u i r e d as w e l l .  Hence  4 ( l o g n) + 1 s t a t e s are r e q u i r e d to r e p r e s e n t t h i s .  states  and the q u i e s c e n t  s t a t e are a l s o r e q u i r e d .  The n output  This gives a t o t a l of  n + 4 ( l o g n) + 5 s t a t e s which are needed f o r t h i s method. L e t F denote the mapping from the output alphabet to Z^. example, F(a)=0,  if  the output alphabet i s  F(b)=l,F(c)=2.  (a,b,c),  TABLE 8 i n d i c a t e s  For  then n=3 and we c o u l d d e f i n e  f o r m a l l y the workings o f  b i n a r y wheel a l g o r i t h m . * l o g n w i l l be used to denote the l e a s t i n t e g e r >_log- n .  the  28. TABLE 8 a,b,c  binary d i g i t s  i f in pairs,  Q  quiescent  0  0 state  X  any a r b i t r a r y c e l l  alone  state  At each s t e p the time co u n ter i s ( ( l o g N) +1).  output s t a t e s i f  state  incremented by 1 modulo  Output s t a t e s are reached at time  (t+1).  Right Neighbour  P  1  Left Neighbour  Q  Ifl  ft  ft  $,g  b  b  Q  Q  a a  X  Q  Q  0,b  a  [ ] b  ft  a  L  J  c  t=l,2  ((log  c  n)-l)  ft  ft  Q  ft  ft  [°i  g  2" t  2  d  .  intege  . : F(g) <  4. O  —  I f r i g h t neighbour i s Q then a=0 i s the o n l y p o s s i b l e value during these i n t e r mediate time s t e p s .  29.  ft X  [F (F(a) + 2 " .d)] _ 1  t  1  t=log n  ft  ft  Q  ft  ft  ft  g  ft  -  ft X  $,b  As an example,  c o n s i d e r the g e n e r a t i o n of the sequenceC02l|>  where n=3 and so l o g n=2. Then  0 = 00  1  2  = oi  2  2 = 10 n  Initialize  at time 0 w r i t i n g 021 i n b i n a r y around the wheel  i n a counter c l o c k w i s e manner but w i t h the o r d e r o f b i t s inverted.  of each characte  S i n c e the product of l o g n and the l e n g t h o f the sequence  even o n l y one copy of the b i n a r y r e p r e s e n t a t i o n of the sequence i s quired. Thus:  t=0  0 0 This  0 0 represents  0  2  is  re-  30. t=l  f  0  t=2 0  *s 1 0  f°l  llj w  llj  fo] fo"  fo'  0  0  1  1  1  UJ t=3 0  fo' fo] fo] 0  loj  V  1 0  1  l ° J  J  fo] fo] fo]  t=4 0  0  1 w  0  2  t=6 0  2  t=7 0  2  1  0  2  1  J  fo'  Uj w  UJ  fl]  fo]  1  1  0  0  0  10J  loj loj  ff  ff  0  0  w t=8  V  0  0 0  fol  t=5  1 1  1 0  r  0 0  \  llj llj 1 0  f  0 0  \  UJ 12J 12J t=9 0  2  1  fo]  fl]  fl]  0  0  0  loj loj l°J A t t h i s p o i n t the s t r i n g has been c o m p l e t e l y generated once and the g e n e r a t i n g bud s e c t i o n  (cells  4,5,6)  is  the same as the i n i t i a l  f i g u r a t i o n of the o r i g i n a l g e n e r a t i n g bud s e c t i o n  (cells  1,2,3  at  cont=0).  31. A reminder on time c o n s i d e r a t i o n s Waksman's method i s as one c e l l  is  would appear to be i n o r d e r .  undoubtedly the f a s t e s t of the t h r e e methods  generated  at each time s t e p .  The simple wheel  requires  two time s t e p s f o r each symbol and the b i n a r y wheel  slowest,  -requiring  generated. that  ((log  The advantage  n) +1)  is  the  time s t e p s f o r each c h a r a c t e r to be is  the l e n g t h of the d e s i r e d sequence has no b e a r i n g on the s i z e of  s t r i n g are b o t h c o m p l e t e l y of a l p h a b e t is  algorithm  of the wheel and b i n a r y wheel a l g o r i t h m s  a l p h a b e t which may be u s e d .  it  discussed  is  the s i z e of alphabet  arbitrary.  determined a u t o m a t i c a l l y  only i n s p e c i a l  The advantage  In f a c t  cases t h a t  and l e n g t h  For a given s t r i n g length i n Waksman's method.  the  not  o f the b i n a r y wheel a l g o r i t h m over the simple wheel  the d r a s t i c r e d u c t i o n i n the number o f s t a t e s r e q u i r e d .  V  E x t e n s i o n of the Wheel A l g o r i t h m to the 2 - D i m e n s i o n a l  r a t h e r than j u s t  is  linear patterns.  approached i n much the same manner as the l i n e a r c a s e .  1. algorithm  Case.  The next step i n the p r e c e d i n g l i n e of thought generate r e c t a n g u l a r ,  size  Furthermore,  the s i z e of t h i s a l p h a b e t , i s  is  of  clearly  to  T h i s can be The problem can  now be formulated i n the f o l l o w i n g manner; D e f i n e a f u n c t i o n on a 2 - d i m e n s i o n a l s t a t e automata, f u n c t i o n of t (i,j),  such t h a t  the s t a t e o f c e l l  the s t a t e s o f t h a t  (i-l,j),  (i+l,j),  c e l l and i t s  (i,j-l),  (i,j+l)  a r r a y of i d e n t i c a l  (i,j)  at time  (t+1)  f o u r immediate  is  finite a  neighbours  ] and so that an a r b i t r a r y  predetermined r e c t a n g u l a r p a t t e r n of c e l l s t a t e s w i l l be  generated  32. continually  throughout  the  space.  T h i s problem may be s o l v e d by a p p l y i n g the wheel a l g o r i t h m twice.  First  the  algorithm is  used,  moving i n the h o r i z o n t a l  direction,  to produce g e n e r a t o r s s i m i l a r to those used i n the one d i m e n s i o n a l  case.  These then generate the p a t t e r n v e r t i c a l l y .  one  dimensional  case are p a i r s of output  flip-flop.  In the two d i m e n s i o n a l  p a i r s and a time  flip-flop.  C o n s i d e r the that i s ,  characters  general  t o g e t h e r w i t h a time  case we s h a l l s t a r t w i t h p a i r s  The f i r s t  generates p a i r s o f c h a r a c t e r s ,  The g e n e r a t o r s i n the  of  a p p l i c a t i o n of the wheel a l g o r i t h m  and a l s o s e t s a time  flip-flop  case of r e c t a n g u l a r p a t t e r n  to  zero.  replication,  generate  i  a  m,l  a  a .~ . m, z  .  . . . . a m,n  2,l  a,  .. . . - a - „ •  1,1 It  a,  1,2  continually.  l,n  s h o u l d be noted t h a t c e l l s are numbered as p o i n t s  in  f i r s t quadrant of the C a r t e s i a n plane and not as' m a t r i x e l e m e n t s . a.. i s i n the lower l e f t hand c o r n e r , i»i  the Hence  1  The f i r s t should be.  problem i s  To generate the  to d e c i d e what the i n i t i a l  configuration  columns i n the upward d i r e c t i o n , we r e q u i r e  t h a t a t some time column j + kn  k=0,l,2,...,  j = l , 2 , . . . , n -be o f  the  33. form 1.3 t  a  a m  »3j  2,1 -t •  m-i+1, j a. .  I  1  »J  a„  I >3 2  .  J  m>3 a. . I >3j x  w i t h a l l c e l l s above c e l l configuration  is  (m,j)  T h e r e f o r e the  m-i+1,1 a.  repeatedly.  Once t h i s  reached a s t r a i g h t f o r w a r d a p p l i c a t i o n of the wheel  a l g o r i t h m w i l l generate the  s h o u l d y i e l d as  i n the q u i e s c e n t s t a t e .  (j + k n ) t h column i n the p r o p e r manner.  g e n e r a t i o n p r o c e s s on the i t h row  i=l,2,...,  output m-;+i,2  i i,2 a  m-i+1, j a. .  I i»3  m-f+l,n a.  Thus the i n i t i a l c o n f i g u r a t i o n becomes e v i d e n t .  Cell  (i  34. i=l,2,...,m,  j=l,2,.,  w i l l be i n s t a t e m-i+1,  n-j+1  [ i,n-j+la  (5.1) m-i+1,j a. .  I  1  »3 0  initially. I t may be noted t h a t i n c e r t a i n cases o n l y p a r t o f t h i s c o n f i g u r a t i o n must be p r e s e n t ,  initial  although the i n c l u s i o n of the e n t i r e  con-  f i g u r a t i o n as s t a t e d above w i l l c e r t a i n l y produce the c o r r e c t r e s u l t . may be noted t h a t i f m i s y + 1 to m; and hence, larly  i f n is  even the  o n l y the  even only the  To i l l u s t r a t e  this  c o n t i n u a l g e n e r a t i o n of the  f i r s t — rows are i d e n t i c a l to  It  rows  f i r s t — rows need be i n i t i a l i z e d .  Simi-  f i r s t — columns need be i n i t i a l i z e d . process  more f u l l y l e t  us c o n s i d e r  the  pattern  a  b  c  d  e  f  g  h  i  j  k  m  The time f l i p - f l o p w i l l be seen to be 0 at even times and 1 at odd t i m e s . f o r h o r i z o n t a l g e n e r a t i o n and r e v e r s e d f o r v e r t i c a l  generation.  35. The  i n i t i a l configuration is  g i v e n by (5.1)aas  Q  Q  t=0  ft  '  f  t  '  Q  ft 0  ft *  ft'  '  f  t  '  ft  ft  0  . o . ft  ft'  Q  ft 0  0  The a table [^]  development  Q  of the p a t t e r n may be c a l c u l a t e d by f o l l o w i n g  s i m i l a r to TABLE 7, but i n which we c o n s i d e r p a i r s o f the form  as one symbol and produce output symbols o f the form  ft  After  0 these symbols  a r e produced we c o n t i n u e w i t h them as i n TABLE 7,  lower neighbour f o r l e f t bour.  neighbour,  reading  and upper neighbour f o r r i g h t  Thus the d e s i r e d output symbols a r e propagated i n an upward  direction.  neigh-  36. t=l  ft  '  ft  [ [°] 1 c  1  r-H  ft  l  h  Q  ft  ft  J  \  ft} ft  ft  Q  m  [ ] c  Q  Q  1  t=2  ft  Q  Q  ft  ft  ft  ft  ft  0  ft  ft  ft  ft  ft  0  ft  0  ft m  [°] 0  «  37.  The g e n e r a t i o n of the p a t t e r n ean be seen c l e a r l y from t h i s point.  The g e n e r a l form of the p a t t e r n w h i l e b e i n g generated  seen at time  t=12  t=12.  column 1  row  can be  10  2  5  6  .7  8  9  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  tt  tt  Q  tt  tt  tt  tt  tt  tt  1-  t°]  l  tt  tt  tt  tt  tt  tt  tt  [*]  1 f  Q  1  1 k  m  1  [tt  1 d  tt  1  [tt l  0  tt  ' t t  1  ' t t '  Q  tt  I °J m  ' t t ' L  k  i  ]  J  1, 0  [  { o J  Q  38. T h i s a l g o r i t h m works as q u i c k l y as can be e x p e c t e d . l e n g t h o f each column i s  i n c r e a s e d by one every second time s t e p and the  number o f columns c o n t a i n i n g f i n a l second time s t e p . tion is  fairly  output symbols i s  i n c r e a s e d every  However the number o f s t a t e s r e q u i r e d f o r t h i s  opera-  l a r g e s i n c e we a r e f o r c e d to d e a l w i t h quadruples of  put s t a t e s i n the i n i t i a l  generation process.  s t a t e s may be c a l c u l a t e d as 1  The  out-  The a c t u a l number o f  follows:  quiescent  state  4 2n  a l l p o s s i b l e quadruples o f output s t a t e s i n each o f the two p o s s i b l e time p o s i t i o n s 2  2n  a l l p o s s i b l e p a i r s i n each time p o s i t i o n  n °n4 2 2n +2n +n+l  output  Clearly this  is  q u i r e e s p e c i a l l y when n i s  states  q u i t e an u n d e s i r a b l e number o f s t a t e s to quite large.  to the one d i m e n s i o n a l case and r e c a l l  re-  A t • t h i s p o i n t we may l o o k back t h a t the c o r r e s p o n d i n g problem was  s o l v e d by mapping b i j e c t i v e l y the n output c h a r a c t e r s , i n an a r b i t r a r y manner, onto the r i n g o f i n t e g e r s need be manipulated u n t i l  modulo n , t h a t i s Z^.  Then o n l y b i t s  the a c t u a l c h a r a c t e r g e n e r a t i n g time  There must however, be a time counter r u n n i n g from 0 to l o g n w i t h the p a i r s o f b i t s  step. associated  and a time f l i p - f l o p , a s s o c i a t e d w i t h the q u a d r u p l e s .  T h e r e f o r e the number of s t a t e s f o r t h i s method may be determined as follows 1  quiescent  state  4 2:2  possible  quadruples o f b i t s  and a time  2 2 . ( ( l o g n)+l  p o s s i b l e p a i r s w i t h time counter  n n+4 l o g n+36  output s t a t e s s t a t e s are r e q u i r e d  flip-flop  39. As i n the one d i m e n s i o n a l c a s e , two drawbacks. initial  First,  it  i s more d i f f i c u l t t o w r i t e down the r e q u i r e d  c o n f i g u r a t i o n , which o c c u p i e s  l o g n times as many c e l l s i n each  d i r e c t i o n as does the n o n - b i n a r y form, are produced o n l y once i n every In g e n e r a l , however,  the b i n a r y r e p r e s e n t a t i o n has  and s e c o n d l y ,  the output  characters  ( l o g n) + 1 time s t e p s i n each column.  the column g e n e r a t i o n p r o c e s s e s w i l l be out o f  phase w i t h each o t h e r due to the  fact  t h a t column g e n e r a t i o n w i l l  on a new column at every o t h e r time s t e p .  begin  Symbols are produced i n a  " t r i a n g u l a r " form as i n the n o n - b i n a r y c a s e .  Hence the r a t e o f p r o d u c t i o n  o f a new output c e l l s i s p r o p o r t i o n a l to the time  t.  A s i m p l e example o f the use o f the b i n a r y wheel a l g o r i t h m i n two dimensions would p r o b a b l y make the workings o f the g e n e r a l  case  much c l e a r e r . Suppose we are to r e p l i c a t e c o n t i n u a l l y the square Then n=4, by  so l o g n=2.  We can d e f i n e  a «-»- 0 = 0 0  2  b -w 1 = 0 1  2  c d  fa  b ^  c  a b i s e c t i o n F from the alphabet  to  2 = 10 -M-  3 = 11  2  Then u s i n g the n o n - b i n a r y method we c o u l d i n i t i a l i z e process with c e l l  (1,1)  i n state  the  Si  [ ]  0 However, u s i n g the b i n a r y technique the p r o c e s s as easy to i n i t i a l i z e .  L e t us f i r s t  i s not  quite  l o o k at the s e t s of p a i r s which  40. must be generated by the quadruples i n o r d e r to generate the pattern.  F o r the sake o f c l a r i t y , l e t  F as d e f i n e d and F(a)  us t e m p o r a r i l y abandon the  let  = 2-a  ±  + &  F(b) = 2'b  ±  + b  2  F(c)  ±  +  c  2  + d  2  2  = 2'c  F(d) = 2 - d where  desired  1  a,, a>2 9  •••  3.ire e i t h e r  0 or  1.  Then to generate the odd numbered columns, which have a {caca ...}  form we must produce (row 2)  r  \  i 2 0 a  (row 1)  C  as the elements i n the f i r s t  two rows o f these columns.  Similarly fb. (row 2) ,0 ,  (row 1) 0 must be generated  i n the even numbered columns.  Thus the output  f o r the h o r i z o n t a l generator  i n row 1  is  function  41. a  C  l 2  and  10 J f  \  2 l 0 a  i n row 2  ,0 , fb.  C  0  must be generated  continually.  T h e r e f o r e the i n i t i a l c o n f i g u r a t i o n o f row. 1 i s  f  and  f o r row 2 2  a  , l, c  0 TABLE 10 t r a c e s the development time s t e p s a f t e r  r e p l a c i n g a^, a ^ , . . .  zontal propagation i n s t r a i g h t TABLE 8 i n Chapter I V .  of the p a t t e r n through s e v e r a l  with t h e i r defined values.  forward, v e r t i c a l propagation  Hori-  follows  42. TABLE 10 t=0 row (2)  ft ft  row(l)  ' f t '  ft  0  t=l  ft  ft-  0  [°] 0  ft ft  [°]  ft ft 0 ' f t '  ft  0  43.  [°]  f  [°]  tt  L  0  J  [°]  0  0  0  1  [°]  tt  ft ]  0  [ ]  1  tt'  0  1 J  V  ' t t  ' t t '  tt  0 V.  J  0 c  b  tt tt  0  [°]  ft  [°] f  tt  tt  ' t t '  0 I  •[°]  0  :  tt tt  44. From t h i s  VI  the g e n e r a l r e p l i c a t i o n p a t t e r n may be s e e n .  E x t e n s i o n to d - d i m e n s i o n a l space  The next step i n the development o f t h i s t e n s i o n to a r b i t r a r y  (d) d i m e n s i o n a l s p a c e .  theory i s  That i s ,  the  to d e f i n e a f u n c t i o n  on a d - d i m e n s i o n a l a r r a y o f i d e n t i c a l f i n i t e automata so t h a t , appropriate f i n i t e i n i t i a l d-space w i l l be  g i v e n the  c o n f i g u r a t i o n , the e n t i r e p o s i t i v e r e g i o n o f  f i l l e d w i t h repeated images o f an a r b i t r a r y predetermined  d-dimensional hypercuboid. of any c e l l at time its  ex-  A g a i n we have the c o n d i t i o n t h a t the  state  (t+1) be a f u n c t i o n o f the s t a t e s o f t h a t c e l l and  2^ immediate neighbours at time The t e c h n i q u e used i s  the 2 - d i m e n s i o n a l c a s e .  t.  the obvious e x t e n s i o n o f t h a t used i n  The wheel a l g o r i t h m i s  g e n e r a t o r s to form ( d - l ) s t l e v e l g e n e r a t o r s .  used on the d t h l e v e l  These i n t u r n  generate  (d-2)nd l e v e l g e n e r a t o r s i n the same way t h a t the v e r t i c a l o r f i r s t level  g e n e r a t o r s were produced by the h o r i z o n t a l , or second  g e n e r a t o r s i n the 2 - d i m e n s i o n a l c a s e .  In any c a s e , a f t e r d such t r a n s -  formations the t e r m i n a l o r output s t a t e s emerge. c a s e , when n i s Actually,  level  As i n the 2 - d i m e n s i o n a l  l a r g e the number o f s t a t e s r e q u i r e d becomes much l a r g e r .  as may be e x p e c t e d , when d i s  q u i r e d becomes a s t r o n o m i c a l .  l a r g e the number o f s t a t e s r e -  T h e r e f o r e , to keep the number o f  w i t h i n reason s i g n a l s may be sent i n b i n a r y , b i n a r y wheel method.  states  as i n the 2 - d i m e n s i o n a l  Only iiti the a c t u a l g e n e r a t i o n o f output symbols do  n o n - b i n a r y forms have to be d e a l t w i t h . p r i s i n g t h a t the e f f e c t  o f dimension s i z e  Hence, i t  s h o u l d not be s u r -  (d) and alphabet s i z e  (n) upon  45. number o f s t a t e s r e q u i r e d are t o t a l l y  independent.  That  is  number s t a t e s = F(d) + G ( n ) . L e t us now determine continually alphabet  the number o f s t a t e s r e q u i r e d to  an a r b i t r a r y d - d i m e n s i o n a l h y p e r c u b o i d o f elements o f an  of c a r d i n a l i t y n.  F i r s t consider  the n o n - b i n a r y  To apply the wheel a l g o r i t h m and move from 1 d i m e n s i o n a l the output  generate  s t a t e we r e q u i r e the q u i e s c e n t s t a t e ,  representation. generators  to  the n output s t a t e s and 2  a l l p o s s i b l e p a i r s of outputs t o g e t h e r w i t h a time states.  To generate the p a i r s ,  2^ t u p l e s .  = 1 + n +  E  or 2n  quadruples are needed, and so on up to  Thus the number of s t a t e s S ( d , n ) d S(d,n)  flip-flop,  r e q u i r e d w i l l be g i v e n by (6.1)  n  j-1 a large  number f o r s u r p r i s i n g l y s m a l l d . In the b i n a r y wheel r e p r e s e n t a t i o n ,  The q u i e s c e n t s t a t e and n output 4 ( ( l o g n)+l) output  2  i  J  of 2  s t a t e s are r e q u i r e d as are  much l o w e r . the  s t a t e s which are needed i n moving from b i n a r y p a i r s  states.  transfer  the number i s  2  At h i g h e r tuples.  l e v e l s , however,  In g e n e r a l  t u p l e s at both time p o s i t i o n s ,  the j t h l e v e l o r 2«,2  of s t a t e s r e q u i r e d i n the d - d i m e n s i o n a l a l g o r i t h m (S, ( d , n ) ) S, (d,n) b  is  the p r o c e s s i s  2  requires  to  a simple all  possible  j  states.  T h e r e f o r e the number  a p p l i c a t i o n of the b i n a r y wheel  g i v e n by  = 1 + n + 4 ( ( l o g n)+l)  = n + 41og n +  d E j=l  2  + 2  -  E 2 . „ J=2  3.  (6.3)  46. As was mentioned b e f o r e ,  t h i s can be viewed as the sum o f a f u n c t i o n o f  n and a f u n c t i o n o f d .  VII  Conclusion  The r e s t r i c t i o n s  inherent  i n Waksman's method o f c o n t i n u a l  r e p l i c a t i o n o f a l i n e a r s t r i n g have been shown.  I f the l e n g t h of the  CC d e s i r e d s t r i n g i s not of the form P may be p r o d u c e d .  T h i s means t h a t no meaningful s t r i n g may be  Furthermore i f the characters  string length  are permitted.  alphabet  cannot be overcome u s i n g a  F o r t h i s r e a s o n the wheel a l g o r i t h m was  U s i n g t h i s a l g o r i t h m t h e number o f c h a r a c t e r s  i s completely  both are a r b i t r a r y .  independent  i n the output  o f the l e n g t h o f the s t r i n g ,  The b i n a r y wheel a l g o r i t h m was developed  the number o f s t a t e s r e q u i r e d t o produce a s t r i n g c o n t a i n i n g n characters  to 0 ( n ) .  d-dimensional hypercuboid.  alphabet  to  fact,  reduce  different  where Z  )  G(n) = n + 41og. n .  t o produce c o n t i n u a l l y a  i t s h o u l d a g a i n be noted t h a t  o f c a r d i n a l i t y n i s o f the form F(d) + G(S)  and  Finally,  r e q u i r e d to generate p a t t e r n s  F(d) = 0 ( 2  and i n  I t was shown a l s o t h a t b o t h the wheel a l g o r i t h m and  the b i n a r y wheel a l g o r i t h m can be g e n e r a l i z e d  number o f s t a t e s  generated.  i s o f the form P , o n l y P output  These r e s t r i c t i o n s  modulo a r i t h m e t i c a l g o r i t h m . developed.  where P i s a p r i m e , o n l y one c h a r a c t e r  i n d-space u s i n g an  the  BIBLIOGRAPHY  Hardy, G . H . and W r i g h t , E . M. Numbers. Waksman, A .  An I n t r o d u c t i o n  Oxford U n i v e r s i t y  P r e s s , London, 1945.  A Model o f R e p l i c a t i o n .  f o r Computing Machinery 16,1  to the Theory o f  J o u r n a l o f the A s s o c i a t i o n (January 1969), p p . 178-188.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0052022/manifest

Comment

Related Items