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 i n the Department of Computer Science We accept t h i s thes i s as conforming to the required standard. The U n i v e r s i t y of B r i t i s h Columbia August, 1969 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h C o lumbia, I agre e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r 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 the Head o f my Department o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f Computer S c i e n c e The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada Date September, 1969 ABSTRACT This thes i s continues the studies of A . Waksman (1969) i n the repeated generation of f i n i t e s t r i n g s i n a one dimensional array of f i -n i t e automata. Waksman handles thispproblem by the use of a "modulo ar i thmet ic" a lgor i thm. This i s shown to be very r e s t r i c t i v e with regard to the number of characters permitted i n the output s t r i n g . In f a c t , i t i s shown that unless the length of the s t r i n g which i s to be repeated i s oc of the form p , where p i s prime, only one output character i s permit ted . This of course makes the process qu i t e meaningless. For t h i s reason, a new algor i thm i s developed. This i s r e -f e r r e d to as the wheel a lgor i thm, s ince there i s an obvious analpgy between i t and a wheel, with the output s t r i n g on i t s circumference r o l l i n g alonggthe array and l eav ing the imprint of the characters i n the s t r i n g behind i t i n the same way that a wheel leaves t i r e t r a c k s . The number of s tates required for such an a lgor i thm i s large and so the b i -nary wheel a lgor i thm i s in troduced. By us ing t h i s a lgor i thm, i n which an output s ta te i s represented as a s t r i n g of b i t s i n s evera l c e l l s , the number of s tates r e q u i r e d , i n a d d i t i o n to the n output s ta tes , can be reduced to about 4 n . Both the wheel and b inary wheel algorithms are then extended to the two dimensional and f i n a l l y the d-dimensional cases. i i TABLE OF CONTENTS Page I In troduct ion 1 II A More D i r e c t Method of Determining {bO 7 I I I The Value of ^ . . . 12 IV An A l t e r n a t i v e Method of Cont inual R e p l i c a t i o n of L i n e a r Patterns — The Wheel Algor i thm . . . . 22 V Extension of the Wheel Algor i thm to the 2-dimensional Case . 31 VI Extension to the d-dimensional Space . . . . . . . 44 VII Conclus ion 46 i i i ACKNOWLEDGEMENTS I wish to thank D r . R. S. Rosenberg for the guidance and ass i s tance which he extended to me i n the preparat ion of t h i s thes i s and Dr. A. Mowshowitz for h i s h e l p f u l remarks i n prepar ing the f i n a l manuscript . The f i n a n c i a l ass i s tance of the Nat iona l Research Counc i l of Canada i s a lso g r a t e f u l l y acknowledged. 1. I INTRODUCTION In a recent paper, Waksman (1969) uses a one-dimensional array of f i n i t e s tate machines to model the cont inua l r e p l i c a t i o n of a sequence of k symbols represented by the states of the c e l l s of the a r r a y . By cont inua l r e p l i c a t i o n of a sequence of length k we mean that a f ter an appropriate length of t ime, dependent on m, the subsets of c e l l s {ik+1, i k + 2 , . . . ( i + l ) k } for i = l , 2 , . . . , m w i l l each be r e p l i c a s of the de-s i r e d sequence of k symbols. Thus i f our alphabet were {0,1} and we wanted to reproduce the s t r i n g of length 4 (0111) c o n t i n u a l l y , a f t e r an appropriate length 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 transformation to be performed i s that the s tate of any c e l l at time (t+1) i s a funct ion of the states of that c e l l and i t s two immediate neighbours at time t . Waksman shows a method of generating- c o n t i n u a l l y s t r i n g s of length k i n the prev ious ly described manner provided the characters from which the s t r i n g i s con-s truc ted are chosen from the r i n g of integers mod g^, ^§k> where g k = gcd{(^)} i - l , 2 k - 1 . (1.1) That i s , g^ i s the greatest common d i v i s i o n of the set of b inomial co-k e f f i c i e n t s (^) other than those which are 1. The problem i s formulated by Waksman as fo l lows: Suppose we want to generate c o n t i n u a l l y the s t r i n g (a^} i = l , 2 , . . . , k ; then, we s t a r t with the i n i t i a l conf igurat ion c o n s i s t i n g of c e l l 0 i n a t r a n s i t i o n s t a t e , P, the next k c e l l s i n s tates b^ i = l , 2 , . . . , k and a l l other c e l l s i n the quiescent s ta t e , Q. I t can be seen that the r e l a t i o n 2. between the s t r i n g s and b^ i s given by a. = I (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^} w i l l be ex-p la ined l a t e r . I t i s to be understood that a l l ar i thmet ic w i l l be modulo At each time step one and only one c e l l i s i n the t r a n s i t i o n s t a t e , P . At time t , c e l l t only w i l l be i n s tate P. The process for any c e l l i s b a s i c a l l y broken i n t o two segments, the' time before i t enters s ta te P and the time a f t e r i t enters statePP. At each time step the c e l l i n s tate P and i t s r i g h t hand neighbour exchange s ta te s . A f t e r t h i s has happened to a c e l l , i t r e ta ins th i s s t a t e . The i n t e r e s t i n g part of the process i s , then, what happens before a c e l l enters the t r a n s i t i o n s t a t e . I f c e l l i i s i n s ta te a . at time t , with the i n i t i a l cond i t ion a„ .=b. t , i o , i 1 for i=l,2,...^kY we def ine a , . by -' C T J , J X a t + l , i = a t , i + a t , i - l , (1.3) where a c e l l i n the quiescent s tate i s considered to be i n s tate 0. To redef ine the funct ion i n a more formal manner we may fol low Table 1 which i n d i c a t e s the transformation up to the time of entry in to the terminal s ta te . To r i g o r o u s l y define the funct ion we may th ink of the c e l l s as having an a d d i t i o n a l f l i p f lop which i s o f f u n t i l the r i g h t neighbour of a c e l l enters s tate P. aAt that time the f l i p f lop i s turned on and no fur ther change can occur i n the s tate of the c e l l . 3. •TABLE 1* F l i p f lop i n p o s i t i o n 0 Q = quiescent s ta te P = t r a n s i t i o n s tate $ = no c e l l present ( l e f t neighbour of c e l l 0) a. = an element of Ze, * The output given i n t h i s and a l l s i m i l a r tables i s at time t+1. c e l l s ta te at time t a. l Right neighbour L e f t a k a i + a k a i + \ neighbour P P P L e f t neighbour Q a. Right neighbour Q Q L e f t neighbour Right neighbour a. No other conf igurat ions can occur . Thus i f we i n i t i a l i z e the array as prev ious ly mentioned and fol low the t r a n s i t i o n of Table 1, c e l l 0 w i l l enter the terminal s tate a^, c e l l 1, h^+b2 = a^ and i n general c e l l i-1 enters terminal s tate i E (. ^) b . = a_^ (by equation 1.2) j = l 2 ~ 3 1 at time t = i . Out problem i s now to c a l c u l a t e { b } for a given set { a} . Waksman found that { b .} could be generated from { a.} i n the fo l lowing manner. Let a, .=a. i=l.,2 , . . . ,k and wr i t e a l T . a . „ . . . a 1 7 . Then l i I ' ' 11 12 l k 4. complete a k x k matrix by l e t t i n g a . = a + a m = 2 , 3 , . . . , k mj m-l,jv- m - l , j + l . , * ' * 1 and a , = a, , = a, (1.4) mk l k k The ar i thmet ic i s of course mod g^. Waksman shows that the process i s continued for m = k+1, k + 2 , . . . , and that the matrix i s r e -peated, or that a m ^ o c ] c j = a m j a = a n y tue p o s i t i v e i n t e g e r . Thi$ property i s due to the fact that the ar i thmet ic i s done modulo g^. This process i s e s s e n t i a l l y what happens i n the ac tua l generating machine before the P s tate i s entered. The only d i f f erence i s that the k - tup le remains s t a t i o n a r y instead of moving to the r i g h t . A f t e r the k x k matrix has been formed the f i r s t column w i l l be c a l l e d the f i r s t t r a n s p o s i t i o n column. This column i s taken as an i n i -t i a l i z i n g row for a second matrix formed i n the same manner, and hence the f i r s t column of t h i s matrix i s c a l l e d the second t r a n s p o s i t i o n column. Waksman shows that i f g^ such matrices are formed the g^th t r a n s p o s i t i o n column w i l l be the set {a.}. Therefore the f i r s t row of the g, th matr ix , X K. or the ( g , - l ) s t t r a n s p o s i t i o n column generates {a.} i n a manner c o r r e s -ponding to that of the generating f u n c t i o n . Hence the (g^- l )s t t r a n s -p o s i t i o n column may be taken as {b_^ }. A numerical example may make t h i s process somewhat c l e a r e r * Suppose we are fo generate {021} c o n t i n u a l l y , so k=3 and Then wr i t e 0 2 1 and fol low formula (1.4) 3-1=2 times 5. (1) 0 2 1 2 0 1 0 2 2 i s the f i r s t t ransposition column 2 1 1 0 2 0 i s the second transposition column and so 0,2,0 = b. ' ' l To check that {0,2,0} w i l l indeed produce {0,2,1} we s h a l l form the or t h i r d matrix. (3) 0 2 0 2 2 0 1 2 0 We see then, that the desired sequence {0,2,1} i s produced. To i l l u s t r a t e the previously mentioned fac t that i f t h i s process i s continued the e n t i r e matrix w i l l be repeated, and so the g^th transposition column w i l l be re-peated we s h a l l continue a few more time steps. • 1 2 0 0 2 0 2 2 0 1 2 0 0 2 0 2 2 0 1 2 0 02.2 0 2 2 0 (2) 0 2 2 2 1 2 0 0 2 6. We s h a l l now s t a r t the generating funct ion with {b^}={0,2,0} TABLE 2 0 1 2 3 4 5 6 7 8 9 10 0 P 0 2 0 Q Q 1 0 P 2 2 0 Q 2 0 2 P 1 2 0 Q - - - -3 0 2 1 P 0 2 0 Q - - -4 0 2 1 0 P 2 2 0 Q - -5 0 2 1 0 2 P 1 2 0 Q -6 0 2 1 0 2 1 P 0 2 0 Q 7 0 2 1 0 2 1 0 P 2 2 0 A f t e r time step 3 we note that the des ired sequence has been generated once and that the "generating bud" i s the same as i t was when i n i t i a l i z e d . Thus we see that the process w i l l work. An important cons iderat ion i n judging the merit of such a scheme i s the number of states r e q u i r e d . Waksman requires the fo l lowing s ta tes : 1 Q the quiescent s tate 1 P the t r a n s i t i o n s tate 2.g^ the integers from 0 to (g^-1) and a lso a f l i p f lop to i n d i c a t e whether a c e l l has entered i t s terminal s tate or not . This gives a t o t a l of 2(g^+l) s ta te s , that i s about twice as many states as output charac ters . Another method of cont inua l generation of se-quences w i l l be introduced i n Chapter 4 and at that 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 function has been i n i t i a l i z e d the generation of a^'s is straight forward. The process occurs as fast as can be expected for 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^ is f a i r l y large. Fortunately i t turns out that the method is somewhat inefficient and that {b_^ } may be determined directly, rather than by iterative procedures, from {a_^ }. Consider the following discussion: Recall equation 1.2 i . , a. = S (T~:) b . . 1 • 1 J-1 3 J=l J J Rewriting this in vector-matrix notation, we have: a l i o 1 (2.1) or a = A b We want to express b in terms of a. 2.1 to yield This may be done by rewriting equation 8. Our problem i s now simply to i n v e r t A . We s h a l l show that: A " 1 = A 1 = 1 0 ... -1 1 1 1 u j : i ) ( - D 1 + j } ( - l ) k + 1 k ( - l ) k + 2 -1 0 k ( - l ) 2 k _ 1 1 To express t h i s simply i n words, A has the same elements as A , however the ( k , j ) t h element has the s ign of (-1)"''+ .^ A more use fu l 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. Theorem 2.1 b . = E d " h ( - l ) i + J a , . 1 j-1 j To prove t h i s theorem we need the fo l lowing lemma: Lemma 2.11 m=j l E ( i - l ) ! (m-1) ! m=j (m- l ) ! ( i -m) ! ( j - l ) ! ( m - j ) ! ( - D 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" 1) S ( h ( - D k J " i k=0 K By expanding (1-1) we note that h . 2 C ) ( - l ) = 0 k=0 K and hence QED We are now ready to prove the theorem. Proof of Theorem 2.1 f 1-1 (. n) for i=l,2,...,k j=l,2,...,l Let a. . ="S 0 for 1=1,2,...,k j=l+l,...,k This defines the matrix A = {a..}. S i m i l a r l y we define f / i - l w _ i N i + : J <;_?<-i>-a'.. H l — l y 2 j • i«jk 2™* 1*^*1 > • • • >k and so define A v = {a1;.} 13 10. Then from the d e f i n i t i o n of {b }. i n equation 1.2, we have shown that a = A b . What we are to prove i s that b . = Z d " h ( - l ) i + j a . 1 j-1 2 2 or that b = A ' a . That means A - 1 = A ' or that AA'=I. Let AA' = { « . . } k then « . . = Z a. a ' . i i i im mi J m=l J We s h a l l show that <*.. =1 and that « . . = 0 i f i ; ^ j , by i i i j cons ider ing the three cases ( i ) i < j ( i i ) 1 = j ( i i i ) i > j ( i ) i < j A i s t r i a n g u l a r , therefore a. =0 for m = i + l , . . . , k • im A 1 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 for m=l,2 (j-1) im mj and for m=(i+1) , . . . ,k and as i < j a. a . =-0 for m=l,2, . . . ,k J im mj ' ' ' Hence « . . = 0 for i < j . ( i i ) i = j Again we have a. =0 for m = i + l , . . . , k im a ' . = 0 for m=l,2,...(j-1) 11, but as i = j we have a. a ' . = 0 for m ^ i im mj therefore . = a . , a ! . 1 1 i i i i but a . . - ( ? - b - l i i l - l a i i = ( i : i ) ( - D 2 i = i therefore <=. . = 1 f o r i = j ( i i i ) i > j again a. =0 for m=(i+1) , . . . ,k im a ' . = 0 for m = l , . . . , ( j - l ) therefore = 0 for m = l , . . . , j - l ' m m - ' and m= (i+1) , . . . ,k Hence « . . = E a. a . = E a. a . i i , ". im mi . im mi-J m=l J m=j • • m=j m _ 1 2 ~ 1 ( - D d E c b e ' i ^ - 1 ) 1 1 1 m—1 i-1 m=j 0 by lemma 2.11 Therefore . = 0 f or i > j . u j-l i f i = j Hence . . = { n i j 0 otherwise So AA' = I or A' = A - 1 thus b . = E ( T " b ( - l ) i + j a . 1 J - l J " 1 J QED 12. R e c a l l i n g the example at the end of chapter I we s h a l l now r e c a l c u l a t e {b.} given {a.} = {0,2,1} k=3 Su=^ By theorem 2.1 h - l ( J i i x - i ) 1 * . , 3 —1 so b l * a l - ° b 2 = a 2 - & 1 = 2 b 3 = a 3 - 2 a 2 + a 1 = 1 - 2(2) + 0 = 0 (mod 3) Hence we have {b^} = {0,2,0} which agrees with the value c a l c u l a t e d by Waksman's method. I t i s easy to see that when k i s f a i r l y large Waksman's method involves a great deal of c a l c u l a t i o n — (g, - l ) k ( k - l ) a d d i t i o n s . The method which we have j u s t developed i s k k much more d i r e c t , r e q u i r i n g l ess than E 2 ( i - l ) ar i thmet ic operat ions . i = l That i s less than 2* 1 * k = k ( k - l ) - ar i thmet ic operat ions . The method i s b e t t e r by a fac tor g^. For the e n t i r e process to have any meaning g^ must be at l eas t 2. I l l The Value of ^ g.^ i s e s s e n t i a l l y the number of characters permitted i n the alphabet over which the s t r i n g i s generated by the Waksman technique, s ince there are g^ elements i n ^g^* Waksman says nothing more about the s i ze of the alphabet , from which the characters to be generated may be chosen, other than to define g, as g .c .d{ ( k ) } i = l , 2 , . . . , k - l . As i t turns out , upon c l o s e r rC X 13. i n v e s t i g a t i o n , g^ i s 1 unless k i s a prime or a power of a prime. To put i t even more s imply , g^ i s i n general 1 and so the Waksman technique of generating sequences c o n t i n u a l l y i s meaningless except i n s p e c i a l cases of k. For to generate a s t r i n g of any length with only one character c o n t i n u a l l y i s merely to generate t h i s one character 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 tated we must f i r s t prove severa l lemmas. F i r s t , define Np'(x) as the number of times the prime p i s a f a c t o r of x. Hence N2(12)=2, N,-(17)=0 et c e t era , I t i s qui te c l e a r N p (xq)=N p (x)+N p (y) when x#), y#). Lemma 3.11 N (i+kp e)=N ( i ) for 1=1,2 ( p 3 - l ) P P or i f i = p 3 and p ^(k+l) . Proof Let i = mp p^m then 0<_a<3 so N (i+kp 3 ) = N ( p a ( m + k p e " ° C ) ) = <*+N (m+kp3"") P P P But as pVi» P^On+kp^ ) then N p ( i+kp 3 ) = cc = N p ( i ) for 1=1,2 (pS-l) I f on the other hand, i - p 3 and p. ^(k+1) we have N (i+kp B ) = N ( (k+l )p e ) = 3 + N (k+1) P P P But , as J?Vk+l) N ( i+kp 3 ) = 6 = N ( i ) P P QED 14. Lemma 3.12 cc N (ps!) = Z p j _ 1 P J-1 Proof: We s h a l l prove t h i s lemma by induc t ion on F i r s t , i t i s obvious ly true for «=0 and f o r r : a = l . We s h a l l assume the lemma i s true for " ^ B and prove i t for <*=8+l. Hence by induct ion the lemma w i l l be t r u e . 8 3 i — 1 8+1 Assuming N (p !) = E (p- ) wr i te out (p 1) i n f u l l and P j - 1 d i v i d e i t in to p sect ions as shown. p ^ + D , . 1 f 2 . m m t P ^ I (p.B+l) . . . 2 p 6 | . . . | ( ( p ' - l ) p e + l ) ' . . . p -Now by lemma 3.11 we know that N p ( i+kp B ) = N p ( i ) for i = l , 2 , . . . , p e when k = 0 , 1 , . . . <p -2) and a lso for i = l , 2 , . . . (p --1) when k=p- l . - 8 Furthermore when i=p and k=p-l N (i+kp B ) = N ( ( p - l + l ) p B ) = N ( p B + 1 ) = 8+1 = N(p P ) +1 P P P Thus p i s a fac tor of each of the sect ions shown, except the l a s t , the same number of times; and i s a f a c t o r of the l a s t one more time than of g the o thers . However, the f i r s t s ec t ion i s p ! , and so p i s a fac tor 3 1-1 E (p J ) t imes. j = l Thus N ( p ( 3 + 1 ) ! ) = P E ( p J _ 1 ) + 1 P j - 1 15. This lemma may be extended to give the value of N p ( r ! ) where r i s not n e c e s s a r i l y a power of p. Lemma 3.13 N ( (p 'x) ! ) = xN (p"!) + N (x!) P P P Proof : C l e a r l y the lemma i s true for x=l . We s h a l l therefore assume the lemma i s true for x=y and prove i t for x=y+l. Hence by induct ion the lemma w i l l be t r u e . cAy+D)! = (P°V)! • (i+P°V)- ... -(y+D" = (P°V)I * n (i+P°V) 1=1 By lemma 3.11 N p (i+p°V) = N p ( i ) for i = l , 2 ( p ' - l ) and N p (p^+p^y) = <* + N p(y+1) = N p ( p ° ) + N p(y+1) then N ( ( p ° ( y + l ) ! ) = N ((p°V)!) + N (p*!) + N (y+1) P P P P (using the i n d u c t i o n assumption) - y N p ( p a ! ) + N p ( y ! ) + N (p*!) + N (y+1) = (y+1) N p ( p a ! ) + -N ((y+1)!) [noting that N ((y+1)!) = N (y!) + N (y+1)] P P P QED Lemma 3.14 I f k = p x, where p 1 x, x > 1 and p i s prime, then P ^ g, . \ 16. Proof ; g k = g.c.d{(J)} 1=1,2 (k-1) . To show p ^ g^ we need only f i n d one i such that p \ (^). • cc Consider the case i n which i = p . P a x Let us evaluate N (( )) P P Since ( ? c c x ) - (p g x! ) V P « ! (( x - l ) p « ) ! ' . C we have N (<f- X )) - N (( p ' x ) ! ) - N (p*!) - N ( ( ( x - l ) p ! ) tr ^ r Jr tr but then " 1-1 N ((p x)! ) = x E p + N (x!) P J - l ? OC N (p^!) = E p i"" 1 P J - l C and N ( ( (x - l )p") ! ) = (x-1) E p j - 1 + N ((x-1)!) P J - l P from lemmas 3.12 and 3,13. Then N ( ( ? « X ) ) = x E p J - 1 + N (x!) P V j = 1 P - E p j - 1 - (x-1) E p ^ " 1 - N ((x-1)!) J - l j - l P N (x!) - N ((x-1)!) + (x-1 - (x -1) ) E p i " 1 P P J - l = N (x!) - N ((x-1)!) P P N p (x ) = 0 as p | x Hence p ^ g k QED 17. With the proof of t h i s lemma the des ired r e s u l t fol lows e a s i l y . Theorem 3.1 k I f k ^ p , g, = 1, or the elements of {(.)} i = l , 2 , . . . ( k - 1 ) are r e l a t i v e l y prime. Proof : k k k = C { ( i ) } » hence g f c | k. Then for every prime p which d iv ides k, apply lemma 3.14. Hence, no f a c t o r of k i s a fac tor of g^.. Then, s ince g^ | k , g^ = 1. QED cc Let us now consider the case i n which k = p and determine the s i z e of the alphabet permitted i n generating c o n t i n u a l l y a s t r i n g of length k by Waksman's method. We can see by the fo l lowing Theorem that 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^, i t must be a fac tor of k. Hence, i n cc t h i s case, g^ = p , where 0 <_ 3 <_ We s h a l l show that g^ = p by showing f i r s t that 3 >_ 1 and secondly that 3 <_ 1. 1) We are to show 3 >_ 1, that i s , ,p | g^. Consider f i r s t the term ( P a - i ) * ( p a - i + l ) . . . (P^-l) which i s of the form of the product of i consecutive integers 18. d iv ided by i ! . By Theorem 74 of Hardy and Wright (1945), i ! d iv ides the product of any i consecutive p o s i t i v e i n t e g e r s . Hence cc cc N ( (p - i ) ( p -i+1) . . . (p -1) ) P - i ! i s defined and 0. cc cc I f we replace (p - i ) , i n the term, by p , c l e a r l y the cc < cc value of N w i l l be increased as N (p - i ) < N (p ) for P P P 1 < i < p". Then N ((?")) - N ( - ( p " - i + l ) - : ; - - ( p ^ l ) ' p " ) p i p l ! > N ( (p'-D (p'-l+D ' ( p ' - l ) \ p i ! > 0. Thus N ( ( ? ) ) > 1. P 1 QED We s h a l l now show that 6 <_ 1 and so that g^ = p. Consider now the case i n which i = p , 1 and so the member p (P ) = p ! (P ) ! (p - P ) ! Therefore , N [ ( P , ) ] - N (p " l ) - N (P"" 1 !) - N ((p"- P"" 1 ) ! ) P p ^ - l P P P 19. j - 1 where N (P !) = Z P P J - 1 cc_ l N ( p " _ 1 ! ) = Z P j - 1 P J - 1 N ((P."- p" X ) ! ) - N ( ( P ™ - 1 (P - l ) ) !) P P cc—2. cc = (P- l ) Z P j _ 1 + N (P- l ) = (P- l ) Z p j - 1 j - 1 P j - 1 as P ^ (P- l ) Therefore . cc a cc— 2_ cc—J_ N [ ( P )] = Z P j _ 1 - Z P j _ 1 - (P- l ) Z P j _ 1 P P " 1 j - 1 j = l j = l « - l . , = l + ( P - l -(P-D) s p J _ 1 j - 1 = 1 cc Hence = P where k = P QED We can now see the f u l l impl i ca t ions of Waksman's method of c o n t i n u a l r e p l i c a t i o n of s t r i n g s . I f the length of the des ired s t r i n g , k, i s a prime, P , or a power of P; then the alphabet from which the elements of k may be chosen i s b i j e c t i v e to Z^. Otherwise the alphabet cons i s t s of a s i n g l e character and hence no meaningful s t r i n g can be generated. As an example, l e t us generate the s t r i n g (120222101). We note that t h i s can be done using Waksman's technique as k=9 hence 8^-3. The c a l c u l a t i o n of {b.} i s c a r r i e d out i n Table 4. TABLE 3 Pasca l ' s T r i a n g l e The b inomial 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 21. TABLE 4 C a l c u l a t i o n of {b.} 1 Refer to TABLE 3 for C^""1) {a±} = {1 ,2 ,0 ,2 ,2 ,2 ,1 ,0 ,1} b-i = ~E ) ( - 1 ) 1 + ? a. ar i thmet ic i s mod;g, 1 j = i J x J ° k b l = 1 b 2 = 2 - 1 = 1 b 3 = 0 -2(2) + 1 = 0 b,4 l = 2 -3(0) + 3(2) -1 = 1 b 5 = 2 -4(2) + 6(0) - 4(2) +1 = 2 b,, = 2 -5(2) + 10(2) - 10(0) + 5(2) - 1 = 0 b 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) + 1 = 2 With (b^} determined we may proceed with the cont inua l generation of the sequence under the ru le s of TABLE 1. 22. TABLE 5 Generation of the sequence (120222101) c e l l i -»• 0 1 2 3 4 5 6 7 -8 9 <!° 11 12 13 14 15 16 17 18 19 20 0 P 1 1 0 1 2 0 1 0 2 Q Q Q 1 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 A f t e r the 9th time step we not ice that the pa t t ern a^ has been generated once and that the i n i t i a l conf igura t ion b_^ i s now i n c e l l s 10-18. At t h i s point we see that the process w i l l c l e a r l y generate the des i red 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 Cont inual R e p l i c a t i o n of L i n e a r Patterns - The Wheel Algor i thm I t i s c l e a r that Waksman's method i s very r e s t r i c t i v e with regards to the alphabet permitted i n cont inua l generation of a sequence 23. of a r b i t r a r y l ength . It i s a lso qui te c l ear that no simple modi f i ca t ion of h i s "modulo ar i thmet ic scheme" can be general ized to any s i g n i f i c a n t degree. For t h i s reason we now turn to a more general method of r e p l i -2 c a t i o n . This method, i n i t s elementary form, requires 0(n ) s ta te s , however, ra ther than 0(n) as d i d Waksman's method, where n i s the s i ze of the alphabet from which the characters are chosen. This method may be modified somewhat so that the number of states required i s about n + 4 log2 n and so l e ss than the 2 n+2 required i n Waksman's method for reasonably large n . The idea behind t h i s general scheme i s qui te s imple . Write the s ta te of each c e l l as a p a i r of elements of the des ired output 3. C e alphabet — say [^ ] [^ ] [^]. Then th ink of t h i s s i x - t u p l e of states as p o s i t i o n s on a wheel r o l l i n g to the r i g h t , and so c lockwise . Hence the a lgor i thm may be r e f e r r e d to as the wheel a lgor i thm. The next ID EL C p o s i t i o n of the wheel w i l l be [^ ] [^ ] [ ]• Now suppose b i s l e f t i n the p o s i t i o n ( i n i t i a l l y occupied by [^], that i s , the wheel leaves a track behind i t as i t r o l l s , the image of the bottom part which was l a s t i n that p o s i t i o n . a c e Using [^ ] [^ ] [^ ] as an i n i t i a l conf igura t ion we have TABLE 6. TABLE 6 Q # [ f ] * Q b [*] [ f l [°J Q b d [df] [\] [ a] Q b d f [ f ] [ d] [ b] Q e c a 24. From t h i s i t can be seen the sequence b , d , f , e , c , a w i l l be generated c o n t i n u a l l y . Thus to generate a , b , c , d , e , f the appropriate i n i t i a l conf igurat ion would be obtained by w r i t i n g t h i s sequence i n a f e d counter-c lockwise manner around the wheel — [ ] [ , ] [ ] • I t may be a b c noted that t h i s method i s d i r e c t l y a p p l i c a b l e to sequences of even l ength . I f a sequence of odd length i s to be r e p l i c a t e d i t may be w r i t t e n twice and considered a sequence of even l ength . Thus to generate c o n t i n u a l l y c b a [abcj the appropriate i n i t i a l conf igura t ion would be [ ] [ , ] [ ] . a. D c The general r u l e for determining the s tate of a c e l l at time t+1 i s that the upper h a l f of the c e l l moves two pos i t i ons to the r i g h t and the lower h a l f stays i n p o s i t i o n , except at the ends. The lower h a l f of the le f t -most p a i r stays i n p o s i t i o n , but a l so moves to occupy the top h a l f of the c e l l to i t s r i g h t , which then becomes the leftmost c e l l . The top h a l f of the r ight-most occupied c e l l does not move two pos i t ions to the r i g h t , but moves to occupy the bottom h a l f of the c e l l immediately to i t s r i g h t which was prev ious ly i n the quiescent s t a t e , but now becomes the right-most occupied c e l l . This process v i o l a t e s one of the ru les which Waksman had s ta ted . That i s wi th the wheel a lgor i thm the s tate of c e l l i at time t+1 w i l l depend, i n genera l , on the s tate of c e l l i - 2 (the top h a l f of the c e l l moves two places to the r i g h t ) at time t . To modify the scheme and avoid t h i s problem requires the i n t r o d u c t i o n of a time f l i p - f l o p and so e s s e n t i a l l y doubl ing the number of s ta t e s . This f l i p - f l o p w i l l a l t e r n a t e , being 0 at even time steps and 1 at odd t imes. The upper h a l f of the p a i r representat ion of 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 each 25. time s tep . The ends w i l l be handled by appropriate means depending on t ime. TABLE 7 formal ly describes the func t ion . TABLE 7 a , b , c 0 -Q -[ a] -L b J Present State L e f t Neighbour output characters an a r b i t r a r y character quiescent s tate generating p a i r s $ - — - - no c e l l present X - _ any character Right Neighbour X(t=l) X(t=0) [ 6] L b J 'Si g b $ b -a X $ a b a Q Q a a t=l ; .Q t=G 26. we have: V c t=0 a b Q 0 0 t= l a b c Q w \\ t=2 a V a b c Q loj loj t=3 a fo] a b c b W w t=4 b f -\ a a b c b 0 To i l l u s t r a t e t h i s , consider the fo l lowing example: It i s des ired to generate c o n t i n u a l l y the pat tern febcbj. Then I n i t i a l conf igurat ion (the bottom symbol i s a time f l i p - f l o p ) t=5 t-6 t=7 w 0" a b c b a w 1 f ' c b a l'/b c b a Loj loj t i c f \ 0 a b c b a b w w Note that any s ta te could be subst i tu ted for the dummy state 0 One s l i g h t drawback to t h i s method i s that 2 time steps are required to generate each new output charac ter . The number of states 2 requ ired can be seen to be 0(n ) as: states are required for a l l poss ib le p a i r s of outputs and time f l i p - f l o p . n output s tates 1 Q, the quiescent s tate 2 2n +n+l s tates i s the t o t a l number r e q u i r e d . I t should be noted that the number of states required i s t o t a l l y independent of the length of the s t r i n g to be r e p l i c a t e d . The next quest ion to be asked i s can the number of states r e -2 quired be reduced from 0(n ) to 0(n) , perhaps at the expense of the time required for generation of each output character? The b a s i c schemexof t h i s a lgor i thm i s to represent each output s tate as a b inary number and so only p a i r s of b inary d i g i t s are manipu-l a t e d . This mapping i s an a r b i t r a r y b i j e c t i o n from the output alphabet to ]L^. As i t takes l og n* b i t s to represent uniquely the integers of a time counter running from 0 to l og n w i l l be required as w e l l . Hence 4 ( log n) + 1 s tates are required to represent t h i s . The n output states and the quiescent s ta te are a l so r e q u i r e d . This gives a t o t a l of n + 4 ( log n) + 5 s tates which are needed for th i s method. Let F denote the mapping from the output alphabet to Z^. For example, i f the output alphabet i s ( a , b , c ) , then n=3 and we could define F(a)=0, F(b)=l ,F(c)=2 . TABLE 8 ind ica te s formal ly the workings of the b inary wheel a lgor i thm. * log n w i l l be used to denote the l eas t integer >_log- n . 28. TABLE 8 a , b , c b inary d i g i t s i f i n p a i r s , output s tates i f alone Q quiescent s tate 0 0 s tate X any a r b i t r a r y c e l l s tate At each step the time counter i s incremented by 1 modulo ( ( log N) +1). Output s tates are reached at time (t+1). Right Neighbour L e f t Neighbour 1P Q I f l ft ft $,g b b Q Q a X a Q [ a] L b J c Q ft c 0,b a t=l ,2 ( ( log 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 only pos s ib l e value during these i n t e r -mediate time s teps . t=log n X X $,b 29. ft [ F _ 1 ( F ( a ) + 2 t " 1 . d ) ] ft ft Q ft ft ft g ft -ft As an example, consider the generation of the sequenceC02l|> where n=3 and so l og n=2. Then 0 = 00 2 1 = o i 2 2 = 10 nI n i t i a l i z e at time 0 w r i t i n g 021 i n b inary around the wheel i n a counter clockwise manner but with the order of b i t s of each characte i n v e r t e d . Since the product of l og n and the length of the sequence i s even only one copy of the b inary representat ion of the sequence i s r e -q u i r e d . Thus: t=0 0 0 0 0 This represents 0 2 30. t=l f *s 1 f°l 0 0 0 1 llj w llj t=2 fo] fo" fo' 0 0 1 1 UJ t=3 fo' fo] fo] 0 0 1 1 loj 0 V J l ° J t=4 fo] fo] fo] 0 0 1 1 0 w 1 V J t=5 fol 0 fo' 0 2 1 0 0 Uj w UJ t=6 fl] fo] 0 2 1 0 0 10J loj loj t=7 f f f f r \ 0 0 2 1 0 0 0 w llj l l j t=8 1 1 f \ 0 0 2 1 0 0 0 UJ 12J 12J t=9 fo] fl] f l] 0 2 1 0 0 0 loj loj l°J At t h i s point the s t r i n g has been completely generated once and the generating bud sec t ion ( c e l l s 4 ,5,6) i s the same as the i n i t i a l con-f i g u r a t i o n of the o r i g i n a l generating bud sec t ion ( c e l l s 1,2,3 at t=0). 31. A reminder on time considerat ions would appear to be i n order . Waksman's method i s undoubtedly the fas tes t of the three methods discussed as one c e l l i s generated at each time s tep . The simple wheel a lgor i thm requires two time steps for each symbol and the b inary wheel i s the s lowest , -requiring ( ( log n) +1) time steps for each character to be generated. The advantage of the wheel and b inary wheel algorithms i s that the length of the des ired sequence has no bear ing on the s i ze of alphabet which may be used. In fact the s i z e of alphabet and length of s t r i n g are both completely a r b i t r a r y . For a given s t r i n g length the s i z e of alphabet i s determined automat ica l ly i n Waksman's method. Furthermore, i t i s only i n s p e c i a l cases that the s i z e of t h i s a l p h a b e t , i s not 1. The advantage of the b inary wheel a lgor i thm over the simple wheel a lgor i thm i s the d r a s t i c reduct ion i n the number of s tates r e q u i r e d . V Extension of the Wheel Algor i thm to the 2-Dimensional Case. The next step i n the preceding l i n e of thought i s c l e a r l y to generate rec tangu lar , rather than j u s t l i n e a r pat terns . This can be approached i n much the same manner as the l i n e a r case. The problem can now be formulated i n the fo l lowing manner; Define a funct ion on a 2-dimensional array of i d e n t i c a l f i n i t e s tate automata, such that the s tate of c e l l ( i , j ) at time (t+1) i s a func t ion of the states of that c e l l and i t s four immediate neighbours t ( i , j ) , ( i - l , j ) , ( i + l , j ) , ( i , j - l ) , ( i , j + l ) ] and so that an a r b i t r a r y predetermined rectangular pat tern of c e l l s tates w i l l be generated 32. c o n t i n u a l l y throughout the space. This problem may be solved by apply ing the wheel a lgor i thm twice . F i r s t the a lgor i thm i s used, moving i n the h o r i z o n t a l d i r e c t i o n , to produce generators s i m i l a r to those used i n the one dimensional case. These then generate the pat tern v e r t i c a l l y . The generators i n the one dimensional case are p a i r s of output characters together with a time f l i p - f l o p . In the two dimensional case we s h a l l s t a r t with p a i r s of p a i r s and a time f l i p - f l o p . The f i r s t a p p l i c a t i o n of the wheel a lgori thm generates p a i r s of charac ters , and a l so sets a time f l i p - f l o p to zero . Consider the general case of rectangular pat tern r e p l i c a t i o n , that i s , generate a i a . ~ . . . . . . a m, l m, z m,n a 2 , l a, .. . . -a- „ • a, c o n t i n u a l l y . 1,1 1,2 l , n I t should be noted that c e l l s are numbered as points i n the f i r s t quadrant of the Cartes ian plane and not as' matrix elements. Hence a.. 1 i s i n the lower l e f t hand corner , i » i The f i r s t problem i s to decide what the i n i t i a l conf igura t ion should be. To generate the columns i n the upward d i r e c t i o n , we require that at some time column j + kn k = 0 , l , 2 , . . . , j = l , 2 , . . . , n -be of the 33. form 1.3 a t m » 3 j 2,1 a -t • m-i+1, j a. . I 1»J a„ . I 2>3 J m>3 a. . I x>3j with a l l c e l l s above c e l l (m,j) i n the quiescent s t a t e . Once t h i s conf igura t ion i s reached a s tra ight forward a p p l i c a t i o n of the wheel a lgor i thm w i l l generate the (j + kn)th column i n the proper manner. Therefore the generation process on the i t h row i=l,2,..., should y i e l d as output m-i+1,1 a. m-;+i,2 i a i,2 m-i+1, j a. . I i»3 m-f+l,n a. repeated ly . Thus the i n i t i a l conf igurat ion becomes ev ident . C e l l ( i 34. i = l , 2 , . . . , m , j = l , 2 , . , w i l l be i n s tate m-i+1, n-j+1 [ a i , n - j + l -m-i+1,j a. . I 1»3 0 (5.1) i n i t i a l l y . I t may be noted that i n c e r t a i n cases only part of t h i s i n i t i a l c o n f i g u r a t i o n must be present , 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 ta ted above w i l l c e r t a i n l y produce the correc t r e s u l t . I t may be noted that i f m i s even the f i r s t — rows are i d e n t i c a l to rows y + 1 to m; and hence, only the f i r s t — rows need be i n i t i a l i z e d . S i m i -l a r l y i f n i s even only the f i r s t — columns need be i n i t i a l i z e d . To i l l u s t r a t e t h i s process more f u l l y l e t us consider the c o n t i n u a l generation of the pat tern 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 generation and reversed for v e r t i c a l generat ion. 35. The i n i t i a l conf igura t ion i s given by (5.1)aas t=0 Q Q ft ' f t ' ft ft Q 0 * ft' ' f t ' ft ft Q 0 . o . ft' ft ft Q 0 0 The development of the pa t t ern may be c a l c u l a t e d by fo l lowing a tab le s i m i l a r to TABLE 7, but i n which we consider p a i r s of the form [^ ] as one symbol and produce output symbols of the form ft 0 Af ter these symbols are produced we continue with them as i n TABLE 7, reading lower neighbour for l e f t neighbour, and upper neighbour for r i g h t ne igh-bour. Thus the des ired output symbols are propagated i n an upward d i r e c t i o n . 36. t=l t=2 ft ft ft ft ' ft ft [ [°] 1 ft c Q r-H 1 l h J \ ft} ft Q m [ c ] Q 1 Q Q Q ft ft ft ft ft 0 ft ft ft 0 ft ft ft 0 ft m [°] 0 « 37. The generation of the pat tern ean be seen c l e a r l y from t h i s p o i n t . The general form of the pat tern whi le being generated can be seen at time t=12. t=12 column 1 2 row 10 tt tt Q Q tt 1-tt l tt 1 f Q Q t°] tt tt 1 k Q Q tt tt tt m 1 d m 5 Q Q 6 Q Q tt Q 1 [*] [tt 1 tt [tt 1 l tt .7 8 9 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 0 ' t t 1 ' t t ' Q tt I ° J ' t t ' [ i ] Q L k J 10, { o J 38. This a lgor i thm works as qu ick ly as can be expected. The length of each column i s increased by one every second time step and the number of columns conta in ing f i n a l output symbols i s increased every second time s tep . However the number of states required for th i s opera-t i o n i s f a i r l y large s ince we are forced to deal with quadruples of out-put s tates i n the i n i t i a l generation process . The a c t u a l number of s tates may be c a l c u l a t e d as fo l lows: 1 quiescent s tate 4 2n a l l p o s s i b l e quadruples of output s tates i n each of the two poss ib le time pos i t ions 2 2n a l l pos s ib l e p a i r s i n each time p o s i t i o n n output s tates ° n 4 2 2n +2n +n+l C l e a r l y th i s i s qu i te an undes irable number of s tates to r e -quire e s p e c i a l l y when n i s qu i te l a r g e . A t • t h i s point we may look back to the one dimensional case and r e c a l l that the corresponding problem was solved by mapping b i j e c t i v e l y the n output charac ters , i n an a r b i t r a r y manner, onto the r i n g of integers modulo n , that i s Z^. Then only b i t s need be manipulated u n t i l the ac tua l character generating time s tep . There must however, be a time counter running from 0 to l og n assoc iated with the p a i r s of b i t s and a time f l i p - f l o p , associated with the quadruples. Therefore the number of states for t h i s method may be determined as fol lows 1 quiescent s ta te 4 2:2 poss ib le quadruples of b i t s and a time f l i p - f l o p 2 2 . ( ( l o g n)+l pos s ib l e p a i r s with time counter n output states n+4 log n+36 states are required 39. As i n the one dimensional case, the b inary representat ion has two drawbacks. F i r s t , i t i s more d i f f i c u l t to wr i t e down the required i n i t i a l c o n f i g u r a t i o n , which occupies log n times as many c e l l s i n each d i r e c t i o n as does the non-binary form, and secondly, the output characters are produced only once i n every ( log n) + 1 time steps i n each column. In genera l , however, the column generation processes w i l l be out of phase with each other due to the fact that column generation w i l l begin on a new column at every other time s tep . Symbols are produced i n a " t r i a n g u l a r " form as i n the non-binary case. Hence the rate of product ion of a new output ce l l s i s p r o p o r t i o n a l to the time t . A simple example of the use of the b inary wheel a lgor i thm i n two dimensions would probably make the workings of the general case much c l e a r e r . fa b 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 c ^ Then n=4, so log n=2. We can define a b i s e c t i o n F from the alphabet to by a «-»- 0 = 00 2 b -w 1 = 0 1 2 c 2 = 10 d -M- 3 = 1 1 2 Then using the non-binary method we could i n i t i a l i z e the Si process with c e l l (1,1) i n s tate [ ] 0 However, us ing the b inary technique the process i s not qui te as easy to i n i t i a l i z e . Let us f i r s t look at the sets of p a i r s which 40. must be generated by the quadruples i n order to generate the des ired p a t t e r n . For the sake of c l a r i t y , l e t us temporari ly abandon the funct ion F as defined and l e t F(a) = 2-a± + &2 F(b) = 2'b± + b 2 F(c) = 2'c± + c 2 F(d) = 2 - d 1 + d 2 where a , , a>2 9 • • • 3. ire e i ther 0 or 1. Then to generate the odd numbered columns, which have a {caca ...} form we must produce (row 2) (row 1) r \ a i C 2 0 as the elements i n the f i r s t two rows of these columns. S i m i l a r l y fb. (row 2) (row 1) ,0 , 0 must be generated i n the even numbered columns. Thus the output for the h o r i z o n t a l generator i n row 1 i s 41. a l C 2 10 J f \ a 2 C l and i n row 2 0 ,0 , fb. 0 must be generated c o n t i n u a l l y . Therefore the i n i t i a l conf igurat ion of row. 1 i s f and for row 2 a 2 , c l , 0 TABLE 10 traces the development of the pat tern through severa l time steps a f t er r e p l a c i n g a^, a ^ , . . . with t h e i r defined va lues . H o r i -zonta l propagation i n s t r a i g h t forward, v e r t i c a l propagation follows TABLE 8 i n Chapter IV . t=0 row (2) row(l) ft ft ' f t ' ft 0 t= l ft 0 ft-[°] 0 ft ft [°] ft ft 0 ' f t ' ft 0 42. TABLE 10 43. [°] [°] tt 0 tt 0 f0 1 [ ] L0 J [°] [°] f t 0 ] 1 tt' 0 1 V J ' t t ' t t ' 0 V. J c b tt 0 tt tt 0 [°] ft [°] tt ' t t ' f 0 •[°] 0 tt I : t t tt 44. From t h i s the general r e p l i c a t i o n pat tern may be seen. VI Extension to d-dimensional space The next step i n the development of t h i s theory i s the ex-tens ion to a r b i t r a r y (d) dimensional space. That i s , to def ine a funct ion on a d-dimensional array of i d e n t i c a l f i n i t e automata so tha t , given the appropriate f i n i t e i n i t i a l 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 region of d-space w i l l be f i l l e d with repeated images of an a r b i t r a r y predetermined d-dimensional hypercuboid . Again we have the condi t ion that the s tate of any c e l l at time (t+1) be a funct ion of the states of that c e l l and i t s 2^ immediate neighbours at time t . The technique used i s the obvious extension of that used i n the 2-dimensional case. The wheel a lgor i thm i s used on the dth l e v e l generators to form ( d - l ) s t l e v e l generators . These i n turn generate (d-2)nd l e v e l generators i n the same way that the v e r t i c a l or f i r s t l e v e l generators were produced by the h o r i z o n t a l , or second l e v e l generators i n the 2-dimensional case. In any case, a f t er d such t r a n s -formations the terminal or output s tates emerge. As i n the 2-dimensional case, when n i s large the number of s tates required becomes much l a r g e r . A c t u a l l y , as may be expected, when d i s large the number of states r e -quired becomes as tronomica l . Therefore , to keep the number of states w i t h i n reason s igna l s may be sent i n b i n a r y , as i n the 2-dimensional b inary wheel method. Only iiti the ac tua l generation of output symbols do non-binary forms have to be deal t w i th . Hence, i t should not be sur -p r i s i n g that the e f f ec t of dimension s i z e (d) and alphabet s i z e (n) upon 45. number of s tates required are t o t a l l y independent. That i s number states = F(d) + G(n) . Let us now determine the number of states required to generate c o n t i n u a l l y an a r b i t r a r y d-dimensional hypercuboid of elements of an alphabet of c a r d i n a l i t y n . F i r s t consider the non-binary representat ion . To apply the wheel a lgor i thm and move from 1 dimensional generators to the output s ta te we require the quiescent s ta t e , the n output states and 2 a l l pos s ib l e p a i r s of outputs together with a time f l i p - f l o p , or 2n s ta te s . To generate the p a i r s , quadruples are needed, and so on up to 2^ t u p l e s . Thus the number of s tates S(d,n) required w i l l be given by The quiescent s tate and n output s tates are required as are the 4 ( ( l og n)+l) states which are needed i n moving from binary p a i r s to output s t a t e s . At higher l e v e l s , however, the process i s a simple t r a n s f e r of 22 tup le s . In general the j t h l e v e l requires a l l poss ib le i 2 j 2 J tuples at both time p o s i t i o n s , or 2«,2 s ta t e s . Therefore the number of s tates required i n the d-dimensional a p p l i c a t i o n of the b inary wheel a lgor i thm (S, (d,n)) i s given by d S(d,n) = 1 + n + E n j - 1 (6.1) a large number for s u r p r i s i n g l y small d . In the b inary wheel representa t ion , the number i s much lower. S, (d,n) = 1 + n + 4 ( ( l og n)+l) + 2 E 2 b . „ J=2 d = n + 41og n + E 2 j = l - 3. (6.3) 46. As was mentioned be fore , t h i s can be viewed as the sum of a funct ion of n and a funct ion of d . VII Conclus ion The r e s t r i c t i o n s inherent i n Waksman's method of c o n t i n u a l r e p l i c a t i o n of a l i n e a r s t r i n g have been shown. I f the length of the C des ired s t r i n g i s not of the form P where P i s a prime, only one character may be produced. This means that no meaningful s t r i n g may be generated. Furthermore i f the s tr ing length i s of the form P , only P output characters are permit ted . These r e s t r i c t i o n s cannot be overcome us ing a modulo a r i t h m e t i c a lgor i thm. For t h i s reason the wheel a lgor i thm was developed. Using t h i s a lgor i thm the number of characters i n the output alphabet i s completely independent of the length of the s t r i n g , and i n f a c t , both are a r b i t r a r y . The b inary wheel a lgor i thm was developed to reduce the number of s tates requ ired to produce a s t r i n g conta in ing n d i f f e r e n t characters to 0 (n) . I t was shown a l so that both the wheel a lgor i thm and the b inary wheel a lgor i thm can be general ized to produce c o n t i n u a l l y a d-dimensional hypercuboid . F i n a l l y , i t should again be noted that the number of s tates requ ired to generate patterns i n d-space us ing an alphabet of c a r d i n a l i t y n i s of the form F(d) + G(S) where F(d) = 0(2 Z ) and G(n) = n + 41og. n . BIBLIOGRAPHY Hardy, G. H . and Wright , E . M. An Introduct ion to the Theory of Numbers. Oxford U n i v e r s i t y Press , London, 1945. Waksman, A . A Model of R e p l i c a t i o n . Journal of the A s s o c i a t i o n f o r Computing Machinery 16,1 (January 1969), pp. 178-188.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Continual pattern replication
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Continual pattern replication Munro, James Ian 1969
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Continual pattern replication |
Creator |
Munro, James Ian |
Publisher | University of British Columbia |
Date Issued | 1969 |
Description | This thesis continues the studies of A. Waksman (1969) in the repeated generation of finite strings in a one dimensional array of finite automata. Waksman handles this problem by the use of a "modulo arithmetic" algorithm. This is shown to be very restrictive with regard to the number of characters permitted in the output string. In fact, it is shown that unless the length of the string which is to be repeated is of the form p(formula omitted) where p is prime, only one output character is permitted. This of course makes the process quite meaningless. For this reason, a new algorithm is developed. This is referred to as the wheel algorithm, since there is an obvious analogy between it and a wheel, with the output string on its circumference rolling along the array and leaving the imprint of the characters in the string behind it in the same way that a wheel leaves tire tracks. The number of states required for such an algorithm is large and so the binary wheel algorithm is introduced. By using this algorithm, in which an output state is represented as a string of bits in several cells, the number of states required, in addition to the n output states, can be reduced to about 4 log₂ n. Both the wheel and binary wheel algorithms are then extended to the two dimensional and finally the d-dimensional cases. |
Subject |
Algorithms Number theory |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-06-05 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0052022 |
URI | http://hdl.handle.net/2429/35131 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
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
Cite
Citation Scheme:
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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0052022/manifest