UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Computation by one-way multihead marker automata Gorlick, Michael Martin 1978

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

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

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

Full Text

COMPUTATION BY ONE-WAY MULTIHEAD MARKER AUTOMATA BY MICHAEL MARTIN GORLICK A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE IN THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept t h i s thesis as conforming to the required standard. THE UNIVERSITY OF BRITISH COLUMBIA October, 1978 1978 (c) Michael Martin Gorlick, In p r e s e n t i n g t h i s t h e s i s in 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 l u m b i a , I a g r e e that the 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 a g r e e t h a t 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 . It i s u n d e r s t o o d that 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 . Michael Martin Gorlick Department o f rnmpnter Sr.iflnr.fi The U n i v e r s i t y o f B r i t i s h Co lumbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 D a t e Qctmbgr 11, iq78 i i A b s t r a c t A new f a m i l y o f automata, one-way mul t ihead marker automata, i s i n t r o d u c e d . I n t u i t i v e l y these dev i ces c o n s i s t o f one or more read heads t r a v e l l i n g i n a s i n g l e d i r e c t i o n on a bounded tape and a f i n i t e f i x e d pool of markers which may be depos i ted on the t a p e , sensed , and l a t e r removed. The major r e s u l t s obta ined a r e : ( i ) A one-way n-head k-marker automaton w i t h d i s t i n g u i s h e d markers (each marker i s r e c o g n i z a b l y d i s t i n c t ) may be s imulated by a one-way n-head (k+1)-marker automaton w i t h un i form markers (one marker cannot be t o l d from a n o t h e r ) ; ( i i ) Minor r e s t r i c t i o n s i n pebble use and head movement do not s i g n i f i c a n t l y a f f e c t the r e c o g n i t i o n power o f these d e v i c e s , consequent ly i t i s p o s s i b l e to o b t a i n normal forms f o r dev i ces w i t h e i t h e r d i s t i n g u i s h e d or un i form markers ; ( i i i ) I f p(x) i s a po lynomia l w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s o f degree k>0 then the language { 0 P ^ in e {0,1,2, . . . }} i s recogn ized by a d e t e r m i n i s t i c s.one-way k-head ( k - 1 ) - m a r k e r automaton; ( i v ) There e x i s t s a c l a s s o f o n e - l e t t e r languages , c h a r a c t e r i z e d by f i n i t e l i n e a r d i f f e r e n c e e q u a t i o n s , which are recogn ized by a d e t e r m i n i s t i c one-way n-head 2 -marker automaton. Members o f t h i s c l a s s i n c l u d e the f i b o n a c c i numbers and a l l languages {Cr ; j n 6 {0 ,1,2, . . . } } , k a f i x e d n a t u r a l number. Th is c l a s s i s o f p a r t i c u l a r i n t e r e s t s i n c e i t c o n t a i n s languages not generable by any p o l y n o m i a l , p rov ing that a complete c h a r a c t e r i z a t i o n o f the o n e - l e t t e r languages recogn ized by one-way mul t ihead marker automata can not r e s t upon the po lynomia l languages a l o n e . i Table of Contents i i i Chapter I N o t a t i o n and d e f i n i t i o n s 1 S e c t i o n 0 I n t r o d u c t i o n 1 S e c t i o n 1 Elementary n o t a t i o n 3 S e c t i o n 2 Programs, dev i ces and products o f dev i ces 5 S e c t i o n 3 R e d u c i b i l i t y and s i m u l a t i o n s 9 S e c t i o n 4 Machines 15 S e c t i o n 5 C l a s s i c a l d e v i c e s 17 Chapter I I One-way mul t ihead marker automata 19 S e c t i o n 0 I n t r o d u c t i o n 19 S e c t i o n 1 P r e l i m i n a r y d e f i n i t i o n s 20 S e c t i o n 2 Equ iva lence o f dev i ces w i t h d i s t i n g u i s h e d markers 25 S e c t i o n 3 The equ iva lence of un i form and d i s t i n g u i s h e d markers 33 S e c t i o n 4 Normal forms 42 Chapter I I O n e - l e t t e r languages 54 S e c t i o n 0 I n t r o d u c t i o n 54 S e c t i o n 1 N o n d e t e r m i n i s t i c o n e - l e t t e r languages 56 S e c t i o n 2 D e t e r m i n i s t i c o n e - l e t t e r languages 64 S e c t i o n 3 Other o n e - l e t t e r languages . 76 B i b l i o g r a p h y 84 List of Figures iv Figure II.2.3 32 Figure II.3-4 41 Figure II.4.9 53 Figure III.2.1 64 V Acknowledgement My g r a t e f u l thanks t o : The i n d i v i d u a l s who prov ided f i n a n c i a l support d u r i n g my long a s s o c i a t i o n w i t h the department. They a r e : John L. Baker , W i l f r e d Hansen, F r e i d e r Nake, J . L. P a r k e r , J . E. L. Peck and Ray R e i t e r ; Pau l Gi lmore and David K i r k p a t r i c k f o r t h e i r a i d and understanding d u r i n g the d i f f i c u l t l a s t months; John Baker , my t h e s i s a d v i s o r , f o r h i s p a t i e n c e , wise c o u n s e l , and u n f l a g g i n g i n t e r e s t i n my work; Tom Rushworth f o r h i s a s s i s t a n c e i n the e d i t i n g and f o r m a t t i n g of chapter I I I ; Da l ton Cameron f o r h i s company d u r i n g the wee hours of the n i g h t ; My p a r e n t s , who had the good sense to l e t me do p r e t t y much as I damn w e l l p l e a s e d . Th is t h e s i s i s ded icated to Robbi Oake f o r whom s imple thanks are complete ly inadequate . Chapter I 0 I n t r o d u c t i o n , The s i m p l e s t c l a s s o f automata u s u a l l y c o n s i d e r e d c o n s i s t s o f a d e v i c e w i t h a s i n g l e r ead head t r a v e l l i n g i n a f i x e d d i r e c t i o n a l o n g a f i n i t e t a p e . The head may examine, but no t a l t e r , t he c o n t e n t s o f the tape squa re under s c a n . The l anguages a c c e p t e d by d e v i c e s o f t h i s d e s c r i p t i o n a r e known as t he r e g u l a r l a n g u a g e s . G e n e r a l i z a t i o n s o f t h e s e d e v i c e s have been c o n s i d e r e d by s e v e r a l w o r k e r s . Rosenberg [Rosenberg 64, 66, 67a , 67b] i n v e s t i g a t e d the powers o f r e c o g n i t i o n o f one-way i n p u t d e v i c e s w i t h more than one h e a d . Sudborough [Sudborough 71 , 76], m o t i v a t e d by l i n e a r bounded automata ( d e v i c e s w i t h a s i n g l e head c a p a b l e o f mot i on i n e i t h e r d i r e c t i o n which may r e p e a t e d l y i n s p e c t and o v e r w r i t e the c o n t e n t s o f any t a p e s q u a r e ) , s t u d i e d one-way m u l t i h e a d w r i t i n g f i n i t e au tomata , d e v i c e s w h i c h , though r e s t r i c t e d t o one-way t a p e m o t i o n , a r e a l l o w e d t o w r i t e on the t a p e . In an e f f o r t t o g e n e r a l i z e pushdown au tomata , I b a r r a [ H a r r i s o n and I b a r r a 68] c o n s i d e r e d o n e - and two-way m u l t i h e a d d e v i c e s w i t h o u t powers o f w r i t i n g , bu t accompan ied by a pushdown s t o r e . To c a p t u r e the n o t i o n o f f i n i t e w r i t i n g , S p r i n g s t e e l [ S p r i n g s t e e l 67 , R i t c h i e and S p r i n g s t e e l 72] found i t p r o f i t a b l e t o d e f i n e two-way m u l t i h e a d d e v i c e s c a s t i n t he f i g u r e o f "bounded c o u n t e r " au tomata . In one f o rm, such a d e v i c e has a s i n g l e two-way read head and a f i x e d number o f marker s wh ich may be d e p o s i t e d on the t a p e , s e n s e d , and l a t e r removed. We s h a l l cons ide r a dev i ce which stands midway between the g e n e r a l i z a t i o n s o f Rosenberg and Sudborough, and bears some resemblance to the dev i ces o f S p r i n g s t e e l o u t l i n e d above. One-way mul t ihead marker automata are obta ined from Rosenberg 's d e v i c e s by a l l o w i n g the heads to l a y down and p i c k up markers obta ined from a f i n i t e f i x e d pool ( thus are ab le to perform a l i m i t e d amount of w r i t i n g ) as they pass a long the input t a p e . Why study such dev i ces? In p r a c t i c a l terms, our aim i s to o b t a i n e f f i c i e n t r e c o g n i z e r s o f l a r g e c l a s s e s o f i n t e r e s t i n g languages. The d e t e r m i n i s t i c pushdown automata which correspond to the c l a s s o f d e t e r m i n i s t i c c o n t e x t - f r e e languages are one example, f i n i t e s t a t e acceptors and the r e g u l a r languages another . I f we r e s t r i c t our a t t e n t i o n to d e t e r m i n i s t i c Chapter I 2 computat ions , the appeal o f one-way head motion i s o b v i o u s , f o r i t i m p l i e s the abscence of backup. We s h a l l see t h a t , w i t h respec t to o n e - l e t t e r languages, one-way mul t ihead marker automata are s u r p r i s i n g l y p o w e r f u l , ab le to recogn ize such languages as the f i b o n a c c i numbers, the range o f any po lynomia l w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s whose domain i s r e s t r i c t e d to the n a t u r a l numbers, and a l l s e t s o f numbers o f the form {k n } , where k i s a f i x e d n a t u r a l number and n v a r i e s over the n a t u r a l numbers. Mu l t ihead d e v i c e s have the f l a v o r of m u l t i p a s s a l g o r i t h m s w i t h s e v e r a l passes (heads) p o s s i b l y runn ing c o n c u r r e n t l y , each pass t a k i n g advantage of the i n f o r m a t i o n obta ined by the p r e v i o u s . Rosenberg's d e v i c e s t r a n s m i t i n f o r m a t i o n from one head to another s imply by t r a n s f e r s i n the f l ow o f the f i n i t e s t a t e c o n t r o l . One-way mul t ihead marker automata i n a d d i t i o n to t h i s method use markers as a means o f " i n t e r h e a d " communicat ion, so these dev i ces may be used to c o n s i d e r the e f f e c t i v e n e s s and u t i l i t y o f markers as a programming t e c h n i q u e . Th is t h e s i s has th ree c h a p t e r s . The f i r s t chapter i s devoted to i n t r o d u c i n g the n o t a t i o n and b a s i c d e f i n i t i o n s employed i n the f o l l o w i n g two. I make heavy use of a n o t a t i o n [Baker 77b] which bears l i t t l e resemblance to the forms o f c l a s s i c a l automata t h e o r y ; s e c t i o n s 1-3 of chapter I t h e r e f o r e r e q u i r e c a r e f u l r e a d i n g . Chapter I I c o n t a i n s the formal d e f i n i t i o n s o f a v a r i e t y o f one-way mul t ihead marker automata. There i t i s shown t h a t a one-way n-head k-marker automaton w i t h d i s t i n g u i s h e d markers (each marker i s r e c o g n i z a b l y d i s t i n c t ) may be s imula ted by a one-way n-head (k+1)-marker automaton w i t h un i form markers (one marker can not be t o l d from a n o t h e r ) . In a d d i t i o n I s h a l l o b t a i n s e v e r a l normal forms which correspond to those d e r i v e d by Sudborough [Sudborough 71] fo r one-way mul t ihead w r i t i n g f i n i t e automata. Chapter I I I e x h i b i t s two l a r g e and v a r i e d c l a s s e s o f o n e - l e t t e r languages - the f i r s t c h a r a c t e r i z e d by po lynomia ls w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s , the second by f i n i t e l i n e a r d i f f e r e n c e equat ions - acceptab le by d e t e r m i n i s t i c one-way mul t ihead marker automata. These c l a s s e s y i e l d languages which are not a c c e p t a b l e by any one-way mul t ihead automaton, bounded r e v e r s a l mul t ihead automaton, n-head pushdown automaton or one-way s t a c k automaton. Chapter I 1 Elementary notation. 3 The following notation i s used here: card X denotes the c a r d i n a l i t y of the set X. X\Y denotes the differ e n c e {x6X!x0Y}. XUY and X f!Y denote set union and i n t e r s e c t i o n r e s p e c t i v e l y . X e Y i f and only i f x 6X implies x 6 Y . X<=Y means Xs=Y where y eY and y 8X for some y. P(X) = {S|S^X}, the powerset of X. D denotes the empty set, 1 the set {0} and 2 the set {0,1} (where convenient), N the set {0,1,2, ...} of natural numbers, N + the set N\{0}, and R the set of r e a l numbers. The word " p o s i t i v e " when used i n reference to the integers means "greater than or equal to zero". I f 0 i s to be excluded I s h a l l say " s t r i c t l y p o s i t i v e " . Members of cartesian products are expressed as ordered tuples or as functions defined on an index set, according to convenience. However i t i s assumed that cartesian products are defined by a universal construction so that, f o r example, cartesian product as an operation on sets i s asso c i a t i v e and commutative. X+Y denotes the d i s j o i n t union of sets X and Y, s i m i l a r l y assumed to be defined by a universal construction. Members of X+Y are usually expressed as i f they were members of XUY, with X("]Y=D. "Function", here, unless e x p l i c i t l y stated otherwise, means " p a r t i a l function". S p e c i f i c a l l y f:X->Y means that f i s a function (single-valued r e l a t i o n ) defined for some elements of the set X and taking values i n Y. dom f={x!y=f(x) f or some y eY}; codom f={y!y=f(x) for some x6X}. As usual the barred arrow s p e c i f i e s a function by i t s action on an element. f:x|->y means (in the proper context) y=f(x). I f X i s a set, I d x denotes the i d e n t i t y r e l a t i o n (or function) on X. o denotes composition of ( p a r t i a l ) functions and i s always defined. z=[gOf](x) i f and only i f there i s some y such that y=f(x) and z=g(y). Thus dom(gOf)={x!f(x) edom g} and codom(gOf)={g(y)!y ecodom f}. If A i s a set then A denotes the set of st r i n g s over A as an alphabet (the free monoid generated by A). A + i s the set of nonempty s t r i n g s over A. For x 6 A , |x| denotes the length of x (number of components), (x] denotes the s t r i n g obtained by deleting the f i r s t component, i f any, of x. [x) Chapter I 4 denotes the s t r i n g obta ined by d e l e t i n g the l a s t component, i f any, o f x . S denotes the empty s t r i n g (the i d e n t i t y o f A*) . Thus |3|=0, (B]=[3)=*. The symbol j_ w i l l mark the end of a p r o o f . I t a l i c [ s c r i p t ] w i l l be i n d i c a t e d by the presence of a - [~] beneath a l e t t e r ; to i l l u s t r a t e , "D" and " L " are i t a l i c "D" and s c r i p t " L " r e s p e c t i v e l y . Uppercase gamma, p i , s igma, ph i and p s i w i l l be represented by l - , u , "J, 0 , and Ij r e s p e c t i v e l y . The b o l d f a c e l e t t e r s a , i , x , z denote lower case a l p h a , i o t a , x i and ze ta r e s p e c t i v e l y . E and V a re the e x i s t e n t i a l and u n i v e r s a l q u a n t i f i e r s r e s p e c t i v e l y . The m a j o r i t y o f s e c t i o n s 2-4 i s excerpted from [Baker 76 , 77a , 7 7 b ] . The reader i s r e f e r e d t o [Baker 77b] i n p a r t i c u l a r f o r a d e t a i l e d d i s c u s s i o n o f the m a t e r i a l summarized h e r e , and f o r p roofs o f 2 . 8 , 3-5, 3 - 8 , 3-9, 3-16, 3 . 1 7 , 4 . 6 , 4 .7 and 4 . 8 . Chapter I 2 Programs, d e v i c e s and products o f d e v i c e s . 5 2.0 D e f i n i t i o n . A program [7 comprises the f o l l o w i n g : T|Q, a f i n i t e set - the nodes. i~[g BTTQ - the s t a r t node. n A , a p a r t i a l f u n c t i o n w i t h dom M£^MQ - the a c t i o n f u n c t i o n . n B , a p a r t i a l f u n c t i o n w i t h dom Tlg^dom n A X U f o r some f i n i t e set U and w i t h codom Mg^MQ - the branch ing f u n c t i o n . I t i s a l s o convenient to d e f i n e Up = nqNCdom u A ) - the t e r m i n a l nodes. MQ = codom ["[A - the commands. uy (z )={ ii<z , i> edom ng) - the va lence o f z , de f ined f o r each z SMQ. -u = u z e u - Q { [ V z ) } -The usua l d o t s - a n d - a r r o w s n o t a t i o n f o r d i r e c t e d graphs i s convenient f o r s p e c i f y i n g programs. For a node z i n a program T]: to s p e c i f y t h a t [T A(z)=a w r i t e " z : a " (or j u s t " a " i f no r e f e r e n c e to z i s needed) near the dot r e p r e s e n t i n g z ; to s p e c i f y t h a t z i s a t e r m i n a l node, w r i t e " z : " or noth ing near i t s d o t ; to s p e c i f y tha t M g ( z , i ) = z ' , w r i t e " i " near the arrow r e p r e s e n t i n g the a p p r o p r i a t e edge < z , z ' > . Designate M S by p u t t i n g i t s dot at the head o f an arrow w i t h n o t h i n g a t i t s t a i l . To avo id g r a p h i c i n c o n v e n i e n c e , use an arrow w i t h " z " but no dot at i t s head to i n d i c a t e tha t the arrow i s to be taken as ending at the dot f o r node z . 2.1 D e f i n i t i o n . A dev i ce D comprises the f o l l o w i n g : DQ , Dg, Drj,, s e t s - the memory, i n p u t , and output s e t s . D-pDg-^Dq, DQ:DQ->D,J,, p a r t i a l f u n c t i o n s - the input and output f u n c t i o n s . DQ , a se t - the commands. DQ , a p a r t i a l f u n c t i o n w i t h dom D Q ^ D Q X D Q and codom DQ<=DQXU f o r some set U - the g e n e r a l i n t e r p r e t a t i o n . Chapter I 6 I t i s a l s o convenient to d e f i n e , f o r each a S D ^ , Dy(a)={i!D(a,m)=<m',i> f o r some m, m'} - the va lence o f a . - a : D - Q ~*-Q X P - V ^ -nir>DQ(a,m) - the i n t e r p r e t a t i o n of a . Remark. By convent ion pure commands ( those a e D ^ f o r which card Dy(a) = 1) have va lence {0}. 2.2 D e f i n i t i o n . I f " i s a program and D a d e v i c e , then C ( u , D ) , the set of computat ions by n on D, i s the set o f sequences < Z Q , I I ] Q > . . . <z n ,m n > i n ]~IQ X DQ i n wh ich , f o r a l l j e {1,2, . . . ,n} , Drj ( 2 . \_ (mj_i ) = <irij , i> and n B ( Z j _ 1 , i ) = Z j f o r some i e{~} v(Zj_.,). Crj . (n,D), the set of t e r m i n a t i n g computat ions by TT on D, i s the set o f sequences < Z Q , I I1Q > . . . <z n ,m n > as above i n which z n eTCj,. The l e n g t h o f a computat ion of the above form i s n . 2.3 Lemma. I f " i s a program, D a d e v i c e , and <zQ,mQ> 6{~IQXDQ, then there i s a t most one sequence <ZQ,U\Q> . . . <Zj c ,mj c > i n C^([j,D). 2.4 D e f i n i t i o n . I f " i s a program and D a d e v i c e , then Drr, the f u n c t i o n computed by IT on D, i s a p a r t i a l f u n c t i o n d e f i n e d t h u s : Drr :D s ->D T :xr>D 0(m) where <U s ,D T (x)> . . . <z,m> e C T(1T,D). The e f f e c t o f ( 2 . 5 ) , which f o l l o w s , i s to d e f i n e the product o f a f a m i l y F of d e v i c e s to be a dev i ce whose memory, input and output s e t s are the c a r t e s i a n products o f the cor responding s e t s i n F, and whose command set i s the d i s j o i n t union o f the command s e t s i n F. Def ine the input and output f u n c t i o n s to operate componentwise, and each command i n t e r p r e t a t i o n to respond to and to a f f e c t on ly the component (of a memory set element) to which i t a p p l i e s . In the f o l l o w i n g , the c a r t e s i a n product o f a f a m i l y { X j ! j 6J} of s e t s ( indexed by a se t J) i s taken to be the set o f f u n c t i o n s f : J - > U j g j X j f o r which f ( j ) ex.; f o r a l l j e j . Chapter I 7 2 . 5 D e f i n i t i o n . I f J i s a set and f o r each j 6 J D. i s a d e v i c e , then a dev i ce Xj g j Dj i s de f ined thus ( w r i t i n g P fo r the product Xj g j D j ) : £Q = x j e J ( D - j V Is - x j ej (P-j)s> £T = x j ej ( P . j V P j . - x b m , where m(j) = (Dj) j (x(j)) f o r a l l j 6 J . P 0 :mr>y, where y(j) = (Dj)n(m(j)) f o r a l l j 6 J . PQ i s the d i s j o i n t un ion +j g j (DJ)Q. For each a6PQ, i f a e ( D j )Q then P a :mr><m', i> where m'=m except t h a t m'(j) i s such t h a t (Dj) a(m(j)) = <m ' ( j ) , i> . A l l p roducts o c c u r r i n g i n t h i s paper have f i n i t e index set J . For these d e v i c e s and f o r t h e i r i n p u t s e t s , e t c . I use the u s u a l n o t a t i o n s D X E X D^, l e a v i n g the s p e c i f i c a t i o n o f index set i m p l i c i t . In case o f repeated f a c t o r s or where o therwise necessary , I d i s t i n g u i s h commands by n a t u r a l number or o ther a p p r o p r i a t e s u b s c r i p t s . When a product i s be ing denoted D X E X . . . or D^, elements o f i t s i n p u t , ou tput , and memory s e t s may be denoted by ordered t u p l e s , the order cor respond ing to t h a t o f the n o t a t i o n f o r the product , but p o s s i b l y w i t h s i n g l e t o n f a c t o r s o m i t t e d . 2 .5 D e f i n i t i o n . I f IT i s a program and D a d e v i c e , then IT i s f o r D i f and o n l y i f ITC?=DC and ITv(z) eD v(IT A(z)) f o r a l l z eJTQ. 2.6 Lemma. I f IT i s a program and D a dev i ce w i t h DQ^-Q, then there i s a program IT' f o r D such tha t JTj[ = Y\± f o r i 6 {Q ,S ,T } and C(|T',D) = C(TT,D). The f o l l o w i n g development f o r m a l i z e s the o b s e r v a t i o n tha t f i n i t e data s t r u c t u r e s are i n d i s t i n g u i s h a b l e from c o n t r o l s t r u c t u r e s . 2 .7 D e f i n i t i o n . A d e v i c e D has t r i v i a l i n p u t [ r e s p e c t i v e l y output ] i f and on ly i f card Dg=1 [ r e s p e c t i v e l y card DIJ.= 1] and dom D T = Dg [ r e s p e c t i v e l y dom DQ = DQ]. A d e v i c e i s t r i v i a l i f and on ly i f i t has t r i v i a l input and output and DQ i s f i n i t e . Chapter I 8 2 .8 Theorem. I f D i s a d e v i c e , E i s a t r i v i a l dev ice and ["[ i s a program then there i s a program IT such that Drr'(x)=y i f and on ly i f (D X E ) r j(x , s ) = <y,t> where E s={s} and E T ={t } . N o t a t i o n . By v i r t u e o f 2 . 8 we may i n c l u d e use o f variables over f i n i t e s e t s i n any program. Where a p p r o p r i a t e , we s p e c i f y i n i t i a l values f o r such v a r i a b l e s . The commands to be employed a r e : x<-a , x<-y : assignment o f constant or c u r r e n t v a r i a b l e v a l u e s , valence={0}; x= : t e s t o f c u r r e n t v a l u e , va lence i s the set over which x v a r i e s . These n o t i o n s are to be understood i n t h e i r usua l programming language senses , assuming s t a t i c s torage a l l o c a t i o n f o r v a r i a b l e s . Chapter I 3 R e d u c i b i l i t y and s i m u l a t i o n s . 9 3.0 D e f i n i t i o n . I f D and E are d e v i c e s , then D<E (D i s r e d u c i b l e to E) i f and on ly i f , whenever U i s a program, there i s a program If' such tha t Err' = Drr. _ i i D«E (D i s e q u i v a l e n t t o E) i f and o n l y i f EKE and E<D as above. 3.1 C o r o l l a r y . < as above i s r e f l e x i v e and t r a n s i t i v e . = as above i s an equ iva lence r e l a t i o n . 3.2 D e f i n i t i o n . I f D and D' are d e v i c e s , then D<<D' (D i s s t a b l y r e d u c i b l e to D') i f and on ly i f D X E<D' XE fo r a l l d e v i c e s E. D « « D ' (D i s s t a b l y e q u i v a l e n t to D') i f and on ly i f D<<D' and D'<<D as above. 3-3 C o r o l l a r y . << as above i s r e f l e x i v e and t r a n s i t i v e . » « as above i s an equ i va lence r e l a t i o n . 3.4 C o r o l l a r y . I f D and D' are dev i ces then D=«D' i f and on ly i f D X E = D ' X E fo r a l l d e v i c e s E. 3.5 Theorem. I f G i s a se t o f programs and D a d e v i c e , then D « D ' where D r r ^ f o r i 6 {Q ,S ,T , I,0} , D£=D C+G, D^=Da i f aeD c, and f o r each V GG Df-(m) = <m',z> i f f <r s ,m> . . . <z,m'> eC T ( r , D ) . N o t a t i o n . I f G, D, D' are as i n 3-5 we c a l l the elements o f G programmable o p e r a t i o n s f o r D. We may d e f i n e programs under tha t name and use them i n programs f o r D wi thout f u r t h e r apo logy . 3.6 D e f i n i t i o n . For any dev ice D, No i s the programmable o p e r a t i o n s p e c i f i e d by - >®0 : . Remark. As a matter o f s t y l e , programmable o p e r a t i o n s whose va lence set i s {0,1} should be i n t e r p r e t e d as boolean p r e d i c a t e s w i t h 0 denot ing " t r u e " and 1 " f a l s e " . Chapter I 10 3.7 D e f i n i t i o n . I f D and E are d e v i c e s , then a s i m u l a t i o n o f D by E comprises f u n c t i o n s fq :Dq->Eq, f s : D s - > E g , f . j , :D T ->E T , f-j- and fQ:Eq->Eg, and f o r each a e D c f g :EQ ->EQ X Dy (a ) , a l l s a t i s f y i n g dom fq=Dq. fqODj = f I ° E I o f s , f T O D Q = E 0 o f 0 o f q . ^ Q X I d D v ( a ) ) ° e a = f a ° f Q f o r e a c h a e 2 C " There are programs Tj and {~Q such t h a t f o r i 6 { 1 , 0 } , m'=f^(m) i f f <(r^ )g,m> . . . <0,m'> 6 C T ( r i ( E ) . For each aep_Q and each f i n i t e subset V ^ D y ( a ) there i s a program i ~ a ^ such tha t ( f a (m) = <m',i> and i e v ) i f f <(raV))s,m> . . . <i ,m'> 6 C T ( ] ~ a V ) , E ) . The s t r i c t l y a l g e b r a i c requirements o f t h i s d e f i n i t i o n are s imply tha t the f o l l o w i n g diagrams commute: D s i ->DQ f I I f S I I Q I I S s — - - — » 5 Q - - — » E Q D Q y 4 D T 1 1 , I l f T § Q — ; — — ; — * £ T to ^0 D Q :S 4 D Q X Dv(a) 1 f 1 f Q X = Eq ->EQ*XD v(a) a The computat iona l requirement i s that E be microprogrammable to s i m u l a t e D i n the sense t h a t f T , f q and the f be computable on E. S ince Hp must be f i n i t e f o r any program ]~f, but Dy(a) may be i n f i n i t e , some strategem l i k e the i n c l u s i o n o f V as a parameter i n the requirement tha t Chapter I 11 the i ~ a ^ ( suppor t ing f a ) e x i s t i s n e c e s s a r y . I f Dy(a) i s f i n i t e , i t i s c l e a r l y s u f f i c i e n t to s p e c i f y X=D v ( a ) , which we denote s imply J~ a . 3.8 Theorem. I f D and D' are d e v i c e s and f i s a s i m u l a t i o n o f D by D', then whenever E i s a dev i ce and IT a program, there i s a program IT such tha t (D ' X E )n'0( f o X Idc- ) = ( f T X I d j , )0 ( D X E ) r r . - - 11 o 1 tip — - 11 3.9 C o r o l l a r y ( S i m u l a t i o n theorem). I f D and D' are d e v i c e s and there i s a s i m u l a t i o n f o f D by D' w i t h f"s= I ddom D£ a n d f T = I d c o d o m DQ T H E N 2 < < : 2 ' -With r e s p e c t to s i m u l a t i o n s , the f o l l o w i n g n o t a t i o n i s conven ien t . 3.10 D e f i n i t i o n . Let D be a d e v i c e , a6D c, w i t h Dy(a) = { i 1 , . . . , i s } f i n i t e ; d e f i n e UJJ a to be the program To show how the s i m u l a t i o n theorem i s used , I w i l l prove the f o l l o w i n g two d e v i c e s s t a b l y e q u i v a l e n t . 3.11 D e f i n i t i o n . I f A i s a f i n i t e s e t , the one-way i n p u t dev ice I n 1 ^ i s s p e c i f i e d thus ( o m i t t i n g the s u p e r s c r i p t ) : In1Q=A*XN, In1 s =A*, In1 T =1. In1j :x r><x,0>, In1 Q :<x ,n> h>0. In1 c ={I=,R} . I n 1 R : < x , k>K> « x , k + 1 > , 0 > i f and on ly i f 0<k<!x|. In1-j-_:<x,k>r><<x,k>,a> where, f o r some u,v e (A+{|-,H)) |-xH=uav, iu '=k , a eA+{h,-|}. 3.12 D e f i n i t i o n . I f A i s a f i n i t e s e t , the t i d y one-way i n p u t dev i ce t i d y I n 1 ^ A ^ i s s p e c i f i e d thus ( w r i t i n g D f o r t i d y I n 1 ^ ) : ( ¥ i 6 {Q ,S ,T , I ,C } ) D ± = I n l £ A ) . Chapter I 12 DQ.<X,|xi+1>r>0 (undef ined o t h e r w i s e ) . (¥a 6 D C ) D A = i n 1 a A ) 3.13 Example. I n 1 ( A ) •« t i d y I n 1 ( A ) . P r o o f . To see tha t D=In1^A^ « E=tidy I n 1 ^ A \ c o n s t r u c t a s i m u l a t i o n f by d e f i n i n g f Q = I d D , f s = I d A * , f T = I d 1 , f j = I d E , . <x,!x|+1> i f n<|x!+1 f 0 :<x ,n>r> < 1 undef ined otherwise , ( V a 6 D c ) f a = D a . The microprograms to support f a r e : T -' I " $No (vaeD c) ra = nn>a. Converse l y , to prove that t i d y I n l ^ << I n l ^ , l e t f Q , f g , f T , f T , f a , I ~ T > Va be as g i v e n b e f o r e , ( <x,n> i f n=|x!+1 f 0 :<x ,n>r> < (^undefined otherwise Let i~Q be the program i h 1 3 .13 3.14 D e f i n i t i o n . I f D i s a d e v i c e , then a dev i ce Rec(D) , the r e c o r d i n g v e r s i o n o f D, i s s p e c i f i e d thus ( w r i t i n g R f o r Rec(D) ) : RQ = {<<m0,a0> . . . < m k _ 1 , a k _ 1 > , mk> [ fo r each j , 1<j<k, there i s some i such Chapter I 1 t h a t D a (mj_ 1 ) = <mj, i>}= ( D Q X D C ) * X D Q . — j R'p — Dip. R T : x r><*,D T ( x )> . R Q: <w,m> r>D 0(m). 5c = 2 c For each a eD^, Ra:<w,m> |-><<w<m,a> ,m'> , i> , where D a (m)=<m',i>. Comparison o f t h i s d e f i n i t i o n w i t h 2 .2 shows tha t <<mg,aQ> ... <mk_i ,a k _. j > ,mk> eRQ i f and on ly i f the re i s some program IT such tha t <ZQ,mg> . . . <z k,m k> eC(TT,D) and n A(Zj )=aj f o r a l l j , 0<j<k. 3.15 C o r o l l a r y . I f D and E are d e v i c e s and IT a program, then D X Err = Rec(D)XErf . Thus D « « R e c ( D ) . 3.16 Theorem. I f D and D' are d e v i c e s and f a s i m u l a t i o n o f Rec(D) by D ' , t h e n , whenever E i s a dev ice and Y] a program, there i s a program T]' such tha t (D' X E ) T T ' 0 ( f g x Idg ) = ( f T X I d E ) o ( D X E ) n . 3.17 C o r o l l a r y . I f D and D' are dev i ces and there i s a s i m u l a t i o n f o f Rec(D) by D' w i t h f g = I d d o m ^ and f T = I d c o d o m 5 q , then D « D ' . Nondeterminism comes i n t o the theory o u t l i n e d i n s e c t i o n 1 as a matter o i n t e r p r e t a t i o n . S p e c i f i c a l l y , a r e l a t i o n ( n o n d e t e r m i n i s t i c a l l y ) computed by ; program IT on a d e v i c e D w i l l be d e f i n e d as the p r o j e c t i o n o f the f u n c t i o n Dr-r obta ined by o m i t t i n g a s p e c i f i e d f a c t o r o f Dg (presumed to be a p r o d u c t ) , the omit ted component be ing thereby regarded as a a u x i l i a r y input s e l e c t i n g a p a r t i c u l a r path i n the t r e e o f computations by IT on D determined by the components not o m i t t e d . We w i l l use the f o l l o w i n g as a standard a u x i l i a r y i n p u t d e v i c e i n t h i s sense . 3.18 D e f i n i t i o n . The a u x i l i a r y i n p u t dev ice Aux i s s p e c i f i e d t h u s : AuXq=AuXg=2 , Aux^.= 1. Auxj=Id2#, AuxQ:Xr>0 (undef ined on nonempty s t r i n g s ) . Aux c={A}. A u x A : i x r > < x , i > f o r 1Q2 (undef ined on M):. Chapter I 14 Remark. For any set X, l e t R(X) denote the r e g u l a r languages over X (as a l p h a b e t ) . I t i s easy to show, u s i n g f a m i l a r t e c h n i q u e s , tha t {dom(In1 ^ VT) !M i s a program}=R(A) f o r any f i n i t e se t A. Programs f o r I n 1 ^ are i n t h i s sense d e t e r m i n i s t i c f i n i t e - s t a t e a c c e p t o r s . Programs f o r A u x X I n l ^ are l i k e w i s e n o n d e t e r m i n i s t i c f i n i t e - s t a t e accepto rs i n the sense tha t {L 'L={x !<w,x> e dom(Aux X In1 ^ )rr f o r some w62*} and some program ri} i s a l s o R(A) . S i m i l a r l y , A u x X O u t ^ i s a programmable n o n d e t e r m i n i s t i c g e n e r a t o r , and we have {L|L={x!<0,x> 6codom(Aux X Out^ A^ )rr} f o r some program l-,} = R(A) . Chapter I 4 Machines . 15 4.0 D e f i n i t i o n . A machine M comprises the f o l l o w i n g : Mp - an i n d e x i n g f u n c t i o n w i t h Mp(j) a dev ice f o r a l l j 6dom M^ ; M^, M^edom M D - the i n d i c e s a c t i v e f o r input and o u t p u t , r e s p e c t i v e l y . I t i s a l s o convenient t o d e f i n e Mj = dom MD - the index s e t . ~D = X j e j ~ D ^ - t h e u n d e r l y i n g d e v i c e . ~S = X j 6 M K ^ ~ D ^ ^ S _ t h e i n P u t s e t -~T = X j 6M ^ M D ( J ) ) T _ t h e o u t P u t s e t -4.1 D e f i n i t i o n . I f M i s a machine and 17 a program, then the r e l a t i o n computed by 17 on M, R(u,M), i s {<x,y> 6 M S XMT! (MD)rr(x)=y f o r some x e (M n) s and y e ( M n ) T w i t h x ( j ) = x ( j ) f o r a l l j eM R and y ( j ) = y ( j ) f o r a l l j 6M^}. N o t a t i o n . A machine M i s o r d i n a r i l y t o be s p e c i f i e d by e x h i b i t i n g Mp, s p e c i f y i n g the index set Mj and the f u n c t i o n Mp i m p l i c i t l y . The s e t s M^ and M^ may a l s o be s p e c i f i e d i m p l i c i t l y by r e f e r i n g to dev i ces which are f a c t o r s i n the product M D as a c t i v e f o r input or o u t p u t . The dev i ces I n 1 ^ are a c t i v e f o r input i n a l l machines and none o f I n 1 ^ or Aux i s o therwise a c t i v e f o r i n p u t or o u t p u t . In p a r t i c u l a r Aux i s not a c t i v e f o r i n p u t or output i n any machine. The f o l l o w i n g i s conven ien t . 4.2 D e f i n i t i o n . I f M i s a machine then X^Mg i s M-acceptab le i f and on ly i f there i s a program 77 such tha t X = dom R(77,M). 4.3 D e f i n i t i o n . I f M i s a machine then L(M) = {X'X i s M -acceptab le } . 4.4 D e f i n i t i o n . I f M and N are machines then M<mN (M i s r e d u c i b l e (as a machine) to N) i f and on ly i f , whenever [7 i s a program, there i s a program 17' such t h a t R(77 ' ,N) = R(n ,M) . Chapter I 16 M=mN (M i s e q u i v a l e n t (as a machine) to N) i f and on ly i f M<mN and N<mM. 4.5 Lemma. I f M i s a machine and D a dev i ce such t h a t Dg(Dj (s ) ) i s d e f i n e d f o r some seDg, then M<fflM XD, where D i s not a c t i v e f o r input or output i n t h i s p roduc t . 4.6 Theorem. I f M i s a machine then M< f f lAuxXM. 4.7 Lemma. I f M i s a machine then Aux 2 X M^Aux XM. 4 .8 Theorem. I f M i s a machine and n6N +, then Aux1 1 X M« Aux X M. Chapter I 5 C l a s s i c a l d e v i c e s . 17 5 .0 D e f i n i t i o n . I f B i s a f i n i t e s e t , the t u r i n g dev i ce T u r ^ i s s p e c i f i e d thus (denot ing Tur v ' by D) : DQ=B* X ( B U { £ } ) X B*, D S=D T=1. D I : 0 r > < » , « , « > , D o :<x,a,y>K>0. D C={L,R,T=} U {T<-b|b 6 B } . Dj j :<x,a,y> |-><<[x) , a ' , a y > ,0> where x = [ x ) a ' . D R :<x,a,y>r><<xa,a' , (y]>,0> where y = a ' ( y ] . D T = : < x , a , y>K> « x , a , y > , a > . (DV(T=)=B U {*}). 2 T < _ b : < x , a , y > ! - X < x , b , y > , 0 > . Tur^ ; i s normal l y not a c t i v e f o r input or o u t p u t . The memory element <x,a,y> rep resents the s t r i n g xay over B scanned at the i n d i c a t e d occurrence o f a . P o s s i b l y x=a=B, so tha t the scan po in t may be beyond the l e f t end of the s t r i n g . A l s o p o s s i b l y a=y=S, so tha t the scan po in t may be beyond the r i g h t end. The T= command r e p o r t s the symbol (or S) scanned. New i n f o r m a t i o n can be recorded by execut ion o f a T<-b command. In p a r t i c u l a r , execut ion o f 1<r b on <3,S,y> or <x,B,S> lengthens the s t r i n g . I n i t i a l l y , the s t r i n g i s empty. Execut ion o f L l e a v e s <3,S,y> unchanged, and execut ion o f R l e a v e s <x ,£ ,5> unchanged. (You might say the unrecorded par t o f the i n f i n i t e tape i s s l i p p e r y . ) By i t s e l f , Tur v ' can on ly compute two f u n c t i o n s : 0h>0 and the empty f u n c t i o n . I n t e r e s t l i e s i n i t s r o l e i n products such as I n 1 ^ X T u r ^ . 5 .1 D e f i n i t i o n . I f B i s a f i n i t e s e t , a dev i ce P d s ^ , (the pushdown s t o r e dev ice ) i s d e f i n e d thus ( w r i t i n g D f o r P d s ^ ) : DQ=B*, D S=D T=1. D-j-:0 h>3«, D o :X|-»0 (undef ined on B + ) . D c = {^-P} U {P<-b|b 6 B } . D^ _ p:xar><x,a> (undef ined on B ) . Chapter I 18 D p < _ b : x h><xb ,0>. Pds v ' i s normal l y not a c t i v e f o r e i t h e r input or o u t p u t . The memory element x , x 6 B , rep resents a pushdown s t o r e whose top i s the r i g h t - h a n d end of x . The command 4-P s i m u l t a n e o u s l y r e p o r t s the symbol on the top o f the s t o r e and pops i t o f f . A d d i t i o n a l elements may be pushed onto the s t o r e by execut ion of a P<-b command. I n i t i a l l y the s t o r e i s empty. 5.2 D e f i n i t i o n . I f B i s a f i n i t e s e t , a d e v i c e S t ^ , (the s t a c k dev ice ) i s d e f i n e d thus ( w r i t i n g D fo r S t ^ ) : DQ = B* X (B U {8}) X B* , D S=D T=1. D T :0r><*,5,5>, DQ:<S,S,S>|->0 (undef ined o t h e r w i s e ) . D c = ( L , R , f S,S=} U { S < - b ! b 6 B } . Dj j:<x,a,y>r><<[x) ,b,ay>,0> where x=[x)b. D R : < x , a , y > H K < x a , b , (y]> ,0> where y=b(y] . D^ _ g : <x,b ,3> (-7><<x,S ,S>, 0> where b eB (undef ined o t h e r w i s e ) . Dg_:<x,a,y>|-X<x,a,y>,a> where aeBU{!f}. Dg^_ j ):<x,$1,5>r><<x,b,X>,0> (undef ined o t h e r w i s e ) . S t v ; i s normal l y not a c t i v e f o r input or ou tput . The memory element <x,a,y> r e p r e s e n t s the s t r i n g xay over B at the i n d i c a t e d occurrence o f a . P o s s i b l y x=a=S, so tha t the scan po in t may be below the bottom of the s t a c k . A l s o p o s s i b l y a=y=S, so tha t the scan po in t may be beyond the top o f the s t a c k . The S= command r e p o r t s the symbol (or X) scanned. A d d i t i o n a l symbols may be pushed onto the s t a c k by execut ion o f a S<r b command, de f ined on ly i f memory has the form, <x,S,S>. Symbols are removed from the top o f the s t a c k by the command, <-S, d e f i n e d o n l y i f memory has the form <x,b,B>. Execut ion o f L l e a v e s <B,3,y> unchanged and execut ion of R l e a v e s <x,B,S> unchanged. Chapter I I 0 I n t r o d u c t i o n . 19 A v a i l a b l e to each s p e c i e s o f marker automaton i s a f i x e d f i n i t e number, say k, o f p e b b l e s . Each head has f r e e access to t h e s e , and may l a y pebbles down upon or remove pebbles from the tape square under s c a n . There i s noth ing t o prevent a head from l e a v i n g a pebble behind as i t moves t o the a d j o i n i n g tape square . N a t u r a l l y , at most k pebbles may appear on the tape at any one t i m e . Marker automata e x h i b i t a c l e a n and l i m i t e d form of w r i t i n g , a tape square be ing m o d i f i e d on ly to the extent o f the presence or absence o f markers . The f a m i l y o f one-way mul t ihead marker automata may be roughly d i v i d e d i n t o two c l a s s e s , those whose i n d i v i d u a l markers are i n d i s t i n g u i s h a b l e from one another and those f o r which each marker may be un ique l y i d e n t i f i e d ; f o r the l a t t e r , we say the markers are d i s t i n g u i s h e d . Fu r ther d i s t i n c t i o n s are based on the number o f markers permi t ted per tape square . The fundamental c h o i c e s a re z e r o , one, and many - ze ro l e a v i n g us w i t h Rosenberg 's one-way mul t ihead f i n i t e automata. The sys temat i c e x p l o r a t i o n o f the taxonomy j u s t o u t l i n e d w i l l beg in i n s e c t i o n 1 of t h i s chapter w i t h the formal d e f i n i t i o n s o f the c l a s s e s o f d e v i c e s made p o s s i b l e by v a r i a t i o n s i n marker s t r u c t u r e and u s e . S e c t i o n s 2 and 3 are devoted to demonstrat ing the computat iona l equ iva lence o f the d e v i c e s enumerated i n s e c t i o n 1. In s e c t i o n 4 , I show t h a t s imple r e s t r i c t i o n s on head movement and pebble use do not s u b s t a n t i a l l y a f f e c t the r e c o g n i t i o n powers o f these d e v i c e s . Consequent ly , we may content o u r s e l v e s w i t h a few s imple types d i f f e r i n g on ly i n programming convenience . Chapter I I 1 P r e l i m i n a r y d e f i n i t i o n s . 20 The f o l l o w i n g two d e f i n i t i o n s g i v e the pr imary forms o f one-way mul t ihead marker automata. A l l f u r t h e r d e f i n i t i o n s w i l l be v a r i a t i o n s on these two themes. 1.0 D e f i n i t i o n . Let A be a f i n i t e s e t , n,k 6 N . Then an n-head one-way i n p u t d e v i c e w i t h k markers , I n l ^ ' 0 ' ^ , i s s p e c i f i e d thus ( w r i t i n g D f o r I n 1 ( A ; n ; k ) ) ; D q = A * X 2 * X N n . An element m of DQ i s denoted < i n p u t , m a r k s , h ^ , . . . , h n > . DS=A*, D T =1. D j i x r X x . y . O , . . . ,0> where y 6 { 0 } * , !y! = !x|. D g K i n p u t , m a r k s , h ^ , . . . ,h n >r>0. D c = {Rj|1<j<n} U { I j = ! K j < n } U{Tj! 1<j<n} D {jj ! 1<j<n} U {MJ= j 1<j<n}. R.= :< input , marks, . . . ,h .= , . . .>r><<input, marks, . . . , h - + 1 , . . •>, 0> i f f h^<j input! • J O J J (no head may move past the r i g h t endmarker) . I j= :mr><m,b m ^ )> where | -m( inputH = t>Q. . .b r , b i6A+{h,H} f o r a l l i . 3 |j : < i n p u t , m a r k s , , h j , . . .>( -><<input,u1v, . . . , h j , . . .>,0> i f f count(marks)<k & K h X ! input I & ( (Eu ,v ) marks=u0v, |u'=h.j-1) (no more than k pebbles may appear on the t a p e , no pebble may share a square w i th another o f i t s k i n d and no pebble may be p laced on an endmarker) . [ count :2* ->N :XK»0 : txK>t+count(x) , t 6 2 . ] T j : <±nput,marks, . . . , h j , . . . > !-><<input , u 0 v , h j , . . . > ,0> i f f 1<hj<|input| & ( (Eu ,v ) marks=u1v, | u ' = h j - 1 ) . Mj= :mr><m,t> i f f 1<m(hj)<|m(input)! & ( (Eu ,v ) m(marks)=utv, !u !=m(h j ) -1 , t 6 2 ) ( the endmarkers may not be i n s p e c t e d f o r p e b b l e s ) . j n ^ ( A , n , k ) ^ g n o r m a i i y a c t i v e f o r input but not f o r ou tput . N o t a t i o n . I n 1 ^ denotes I n 1 ^ A ' 1 ' 0 ^ and I n 1 ^ A ; n ^ i s shorthand f o r I n l U ; n ; ° ) . i n i ( A ) has a l r e a d y been mentioned i n chapter I, I n 1 ^ A ; n ^ corresponds to Rosenberg's n-head one-way f i n i t e automaton. Chapter I I 21 1.1 D e f i n i t i o n . Let A and M be f i n i t e s e t s (a lphabet and markers r e s p e c t i v e l y ) and l e t n eN; then an n-head one-way i n p u t dev i ce w i t h d i s t i n g u i s h e d markers M, D I n 1 ^ A ; n ' M \ i s s p e c i f i e d thus ( w r i t i n g D f o r D I n 1 ( A ; n ; M ) ) : DQ=A* XP* X N n where P=M+{-}. An element m of D Q i s denoted < i n pu t , marks, h.|,. . . >hn>. Dg=A*, D T =1. D-r r><x ,y ,0 , . . . ,0> where y 6 { - } * , ! y != ix| . D0:m|->0. D c = {Rj! l<j<n}TI{I j=i1<j<n} U{^jp| 1<j<n, p 6 M} U U j ! 1< j<n} U { M j = 11< j<n}. :< input ,marks , . . . , h ^ , . . .>f -><<input,marks, . . . , h ^ + 1 , . . •>, 0> i f f h j<| input| . I j= :mr-><m,bm^ )> where !~m(input)-{ = b Q . . . b r , b^eA+{h,H} f o r a l l i . 3 |jP :< input ,marks , . . . ,h j , . . .>r><<input ,upv ,...,hj,...>,0> i f f p 6M\{s ! (Eu ,v ) marks=usv, s 6M} & 1<hj<'input! & ( (Eu ,v ) marks=u-v, |u i=hj -1 ) . 1 j :< input ,marks , . . . , h j , . . . > |-><<input , u - v , h j , . . . > ,0> i f f 1<j<!input| & (Eu ,p , v marks=upv, l u ! = h . - 1 , p 6 M ) . Mj= :mr><m,p> i f f 1<m(hj)<im(input)i & ( (Eu ,v ) m(marks)=upv, |u!=m(hj ) -1 , pep). ( A•n• DIn1 v ' ' ' i s no rmal l y a c t i v e f o r input but not f o r ou tput . Remark. Markers and input symbols appear on separate but p a r a l l e l tapes f o r p u r e l y t e c h n i c a l r e a s o n s . The proofs to f o l l o w f r e q u e n t l y r e f e r e n c e the marker tape wi thout concern f o r the symbol on the cor responding input tape square . L i k e w i s e , the input tape can be inspec ted wi thout n o t i c e o f the d i s t r i b u t i o n o f the markers . I s h a l l o f t e n speak as i f markers and input symbols are on the same t a p e . The n o t i o n o f a l l o w i n g more than one uni form marker to appear on a square i s captured i n the f o l l o w i n g . 1.2 D e f i n i t i o n . Let A be a f i n i t e s e t . Let n,k 6 N . Then an n-head one-way i n p u t dev i ce w i t h subsets o f k markers s I n 1 ^ A ' n ' ^ , i s s p e c i f i e d thus Chapter I I 22 ( w r i t i n g D f o r s l n 1 ^ A ; n ; k ^ ) : DQ=A* XN* X N n . An element m of DQ i s denoted < i n p u t , m a r k s , h ^ , . . . , h n > . Dg=A*, D T =1. D p X p X x . y ^ , . . . ,0> where y 6 { 0 } * , |y! = |x! . D Q :mr>0. Dc=imcA;n;k). (¥a 6 {R,! 1<j<n} U {I,= ! 1<j<n}) D a i s de f ined ana logous ly to I^iA'n'kK J — — J — — — a. a |j : < i n p u t , m a r k s , h j , . . . > r > < < i n p u t , u ( i + 1 ) v , . . . , h j , . . .> ,0> i f f count(marks)<k & K h X l i n p u t ! & ( (Eu ,v ) marks=u( i )v , |u! = h i - 1 ) . x ~ J [countrN ->N :Xh>0 : ( i ) xh> i+count ( x ) . ] T ^ :< input ,marks , . . . , h i , . . . > r > « i n p u t , u ( i - 1 ) v , . . . , h i , . . .> ,0> i f f K h ^ l i n p u t j & ( (Eu ,v ) marks=u( i )v , ! u | = h i - 1 , i > 1 ) . M i = :mr><m,t> i f f 1<m(h i )< |m( input ) i & ( (Eu ,v ) m(marks)=u( i )v , !u| =m(h.j)-1) where t = m i n {1 , i } . s I n 1 ^ A ' n ' k ^ i s normal l y a c t i v e f o r input but not f o r o u t p u t . With d i s t i n g u i s h e d markers a v a r i e t y o f memory s t r u c t u r e s are p o s s i b l e i f we permit s e v e r a l markers to a square . M u l t i p l e markers may, f o r example, be o rgan ized on each square as a pushdown s t a c k , a queue, or an unordered s e t ; the hope be ing tha t each d i s t i n c t data s t r u c t u r e w i l l g i v e r i s e to a s u b c l a s s o f marker automata whose computat iona l powers r e f l e c t t h e i r w r i t i n g a b i l i t i e s . 1.3 D e f i n i t i o n . Let A and M be f i n i t e s e t s . Let n 6 N . Then an n-head one-way i n p u t dev i ce w i t h pushdown d i s t i n g u i s h e d markers M, p d D I n l ( A » n > M ) f ± s s p e c i f i e d thus ( w r i t i n g D fo r p d D I n l ^ A ' n ; M ^ ) : DQ=A* X(M*)* X N n . An element m of DQ i s denoted < i n p u t , m a r k s , h ^ , . . . , h n > . Remark. A marker tape i s a s t r i n g whose components are a l s o s t r i n g s . To denote members o f a set o f t h i s fo rm, I w i l l use <,> to d e l i m i t components, X X X thus a s t r i n g over (M ) i s w r i t t e n <x1 ><x 2>.. • <x r >, where x i 6 M f o r a l l i . For example {<8>} i s the set c o n s i s t i n g o f the empty s t r i n g and a l l s t r i n g s whose components are the empty s t r i n g . Chapter I I 23 DS=A*, D T=1. D I : x r > < x , y , 0 , . . . , 0 > where y e { « > } * , !y !=!x! D o :mr>0. D c = D m i £ A ; n ; M ) . (¥a e{Rj!1<j<n} U{Ij=|1<j<n}) D a is defined analogously to D I n 1 a A ; n ; M ) |jP:<input,marks,... ,hj ,.. .>K>«input,u<xp>v,... ,hj , . . .> ,0> i f f 1<hj<!input| & p 6M\unpack(marks) & ((Eu,v) marks=u<x>v, !u!=hj-1) (the right hand of x is the top of the. pushdown store). [unpack:(M ) ->P(M) :&r>0 :<&>yr>unpack(y) :<xp>yhMp} Uunpack(<x>y), where p 6 M . ] T ^  :< input ,marks , . . . ,h^ , . . .>r><<input ,u<[x )>v , . . . , h - , . . .> ,0> i f f K h X ! input i & ( (Eu ,v ) marks=u<x>v, |u|=hj -1, x=[x)p, p 6 M ) . M =^ :mr><m,p> i f f 1<m(h i )<im(input) ! & ( (Eu ,v ) m(marks)=u<x>v, x=[x)p, peM+{*}, !u !=ra(h j ) -1 ) . pdDInl(A;n;M) ^ g n o r f f l a i i y a c t i v e f o r input but not f o r o u t p u t . 1.4 D e f i n i t i o n . Let A and M be f i n i t e s e t s . Let n 6 N . An n-head one-way i n p u t d e v i c e w i t h subsets o f d i s t i n g u i s h e d markers M, s D I n l ^ A ; n ; M ^ , i s s p e c i f i e d thus ( w r i t i n g D fo r s D I n l ^ A ' n ' M ^ ) : DQ=A* XB* X N n where B=P(M). An element m of D Q i s denoted < i n p u t , m a r k s , h ^ , . . . , h n > . DS=A*, D T =1. D j i x h X x j ^ , . . .0> where y 6{D}*, !y!=!x|. D Q : m ^ 0 . D c = {Rj ! 1<j<n} U {Ij=! 1<j<n} U {|jp! 1<j<n, p 6M} U {j j p i 1<j<n, peM}U {peMj ! p 6 M , 1<j<n}. Rj :< input ,marks , . . . , h j , . . .>|-><<input,marks, . . . ,h j+1 , . . .> ,0> i f f h j<! input I j= :mr><m,bm(h )> where (-m(input)H = b0...br, b i 6A+{[-,-{} f o r a l l i . 3 | j p : < i n p u t , m a r k s , . . . , h j , . . . >|-><<input,u(R U {p} )v , . . . , h j , . . .>,0> i f f 1<hj<|input! & ( (Eu ,v ) marks=uRv, |ui=hj -1) & p 6MXunpack(marks). Chapter I I [ unpack :B*->P(M) :*r>D :Sxh>S Uunpack(x) where seP(M).] T j P : < i n p u t . m a r k s , . . . , h j , . . .>r><<input ,u(R\{p} )v , . . . , h j , . . .> ,0> i f f K h ^ j i n p u t ! & ( (Eu ,v ) marks=uRv, !u!=h,-1, peRsM). ~* J — J peMj :mHKm,t> i f f 1<m(hj )< !m( i n p u t ) ! & ( (Eu ,v ) m(marks)=uSv, |u|=m(hj)-1, S eP(M)) where CO i f p es 1^1 o therwise ( A • n • P ) s D I n l v " ' u ' r y i s normal l y a c t i v e f o r input but not f o r o u t p u t . The above d e f i n i t i o n s do not exhaust the p o s s i b l e memory s t r u c t u r e s , s top here because, as the f o l l o w i n g arguments show, d i s t i n c t subc lasses o f marker languages cannot be obta ined based upon v a r i a t i o n s i n the use of d i s t i n g u i s h e d markers by the d e f i n i n g automata. Chapter I I 2 Equ iva lence o f dev i ces w i th d i s t i n g u i s h e d markers . 25 2.0 Lemma. s D I n 1 ( A ; n ; P ) « D I n 1 ( A ' n 5 P ) . P r o o f . Let D = s D I n 1 ( A 5 n 5 p ) , E = D I n 1 ( A ; n ; P ) . We assume, wi thout l o s s o f g e n e r a l i t y , tha t P = { 1 , . . . , k } . Augment E w i t h k elements o f f i n i t e memory S 1 , S k where ¥ k _ 1 d o m ( S i ) = P { 1 , . . . , k } . S t a b l e r e d u c i b i l i t y w i l l be obta ined v i a the c o n s t r u c t i o n o f a s i m u l a t i o n . E w i l l represent the s e t s X«=P, X nonempty, o f D by the strategem of a l l o w i n g on ly a s i n g l e r e p r e s e n t a t i v e , x = min X, to appear on the tape square cor responding to the p o s i t i o n o f X i n D w h i l e r e t a i n i n g X i n i t s e n t i r e t y as the va lue o f S x . Def ine fg.Dg->Eg :mr>m' where ( i ) m' ( input)=m(input) ( i i ) i f m(marks)=T^ . . . T r then m ' ( m a r k s ) = x 1 . . . x r where f m i n 7L i f T ^ Q 1 1^ - o therwise ( i i i ) ¥ n = 1 m' (h j )=m(hj ) . ( i v ) (¥peP) m ' (S p ) = ( s | ( E T e P ) T>-D, m(marks)=uTv, p=min T, & s 6 T } . (Example. I f m(marks)=uTv, T={3,5} then m'(S3)={3,5} and m'(S5)=0.) Def ine f T : E g - > E g :m->m' where m'=m except tha t ¥ k _ 1 S ^ D ; and fg= Id E . Def ine the f o l l o w i n g programs T -1 I " V Chapter I I 1 0 " i ©No ( ¥ J = I ¥ P E P ) R ; J P ®using(p) p - 1 ^ S p _ 1 U { p } ? S « - { p } 5 I lo: ( ¥ J = 1 ¥ P E P ) r T j P Itransfer^k, ! J i ^transferj(p+1,p) f s p ^ s p \ { P } f s ^ S l \ { p } f S p . ^ S p ^ X C p } |1 3p+1 e s p ?j—>©transferj(p,p+1) 5 Ik e S P Q—>®transf er j (p, k) Chapter I I 27 (vp ep v n = 1) P 6 M , IM .= {-.P+1. ! J ->©1 (¥p eP) us ing (p ) : 0:©<-1 1 0<-P e s k 1 «1: ( ¥ n = 1 -¥p,q eP) t r a n s f e r ^ p,q) = i S q ^ S p U { q } (¥a 6 {I l S|1<j<n} U {R.j!l<j<n}) a = 1 'D, a ' The d e s i r e d r e s u l t f o l l o w s from an a p p l i c a t i o n o f the s i m u l a t i o n theorem. 1 2 .0 2.1 Lemma. D I n 1 ( A ; n ; P ) « p d D I n l ( A 5 n 5 p ) P r o o f . Let D = D I n 1 ( A 5 n 5 p ) , E = p d D I n 1 ( A 5 n 5 p ) . Def ine f Q : D Q - > E Q :mh>m' where ( i ) m' ( input)=m(input) Chapter I I 28 ( i i ) i f m ( m a r k s ) = b 1 . . . b r then m'(marks)=<c,>. . .<c r > where ¥ £ = 1 fb± i f b± 6 P 1 \_B otherwise ( i i i ) ¥ n = 1 m' (h j )=m(hj ) . Let f j -z fQzIdg . ( ¥ a e (D c \{| jP l 1<j<n, pep})) l e t j ~ a = TCD>a. F i n a l l y ( ¥ n -i ¥ p 6 P ) l e t T i n be the program l M j = A p p l i c a t i o n o f the s i m u l a t i o n theorem completes the p r o o f . 1 2 .1 2 .2 Lemma. p d D I n l ( A ' n ' P ) « s D I n l ( A 5 n ; p ) . P r o o f . Let D=pdDIn1 ^ A ; . n ; P \ E=sDIn1 ^ A ; n 5 p ) . We assume, wi thout l o s s of g e n e r a l i t y , t h a t P = { 1 , . . . , k } . Augment E by k+1 elements o f f i n i t e memory: ( i ) s ^ , s k where dom s ^ t x eP ! |x|<k}; ( i i ) top whose domain i s P+{-} . To s i m u l a t e D, E models the contents o f a s tack S = < c 1 . . . c m > , c ^ P , as an unordered set { o ^ , . , . , o } and the o r d e r i n g o f the s t a c k ' s c o n s t i t u e n t s as a s t r i n g c . | . . . c m bound to the elements o f f i n i t e memory s c , s indexed by 1 m the i n d i v i d u a l components o^, c m . Def ine fg:DQ->Eg :m|->m' where ( i ) m ' ( input )=m( input ) ; ( i i ) Let m(marks)=<x^>.. .<x r>. I f ( ( E i , j ) i^ j x ^ u p v , Xj= u ' p v ' , and p 6 P ) v ( ( E i ) x ^ u p y p w , and p 6 P ) then m'(marks)=S and ¥ k _ 1 m'(s^)=S, o therwise m'(marks) = T .| . . .T p where = u n p a c k ( x i ) and Chapter I I (¥peP) m ' ( s p ) = 29 i f (E j ) 1<j<r, and ( E u , v 6 P * ) m(marks)=<x^>. . .<Xj>. . ,<x r >, and Xj=upv 8 otherwise [unpack: P*->P(P) :5r>D : px hHp} U unpack(x) , p 6 P ] . ( i i i ) V^ = 1 m' (h j )=m(hj ) . Let f j - :EQ^EQ :mr>m' where m'=m except t h a t ¥^_^ m' ( s i )=X ; and fQ=Id E -Q Def ine the programs I " £s..<-X i l I SNC (••5=1 vP ep) • J 1 >©push.j(p) >®push k (p ) Chapter I I 1 . . . k (¥a 6{I j=!1<j<n} U{Rj ! l< j<n} ) Chapter I I (•Vi,j eP) p u s h i ( j ) i I s ^ ( S i ) j ©s,<- s. ! J 1 ( V k = 1 ) poP i = [ S i ) k top<- k ( V k = 1 ) t o P i = * i i Is.- = j [ S i ) 1 ] [ S i ) k Ik: A p p l i c a t i o n of the s i m u l a t i o n theorem completes the p roo f . 1 2 . 2 F i g u r e 2 .3 summarizes the r e s u l t s obta ined so f a r . The g r a p h i c a l n o t a t i o n , D->E, where D and E are dev i ces should be taken to mean D << sDIni(A;n;P) i I t DInt(A;n;P) i I I 2 . 3 F i g u r e . Chapter I I 32 In r e t r o s p e c t i t i s easy to see why memory s t r u c t u r e s f a i l to i n f l u e n c e the computat iona l power o f marker automata. S ince the t o t a l number of a v a i l a b l e pebbles i s f i n i t e , each memory s t r u c t u r e , no matter how complex, can be s imula ted w i t h an element of f i n i t e memory (one f o r each m a r k e r ) . One-way mul t ihead marker automata w i th memory s t r u c t u r e s may t h e r e f o r e be f r e e l y employed f o r reasons o f programming or pedagogica l convenience wi thout f e a r tha t the computat iona l power o f the dev i ce i s be ing compromised or enhanced. Chapter I I 3 The equ iva lence o f un i form and d i s t i n g u i s h e d markers . 33 I next show t h a t the pr imary d i s t i n c t i o n among marker automata, hav ing d i s t i n g u i s h e d pebbles as opposed to u n i f o r m , i s m i s l e a d i n g , s i n c e any dev i ce w i t h d i s t i n g u i s h e d markers may be s imulated by one w i t h un i form markers a t the expense of a modest i n c r e a s e i n the number o f p e b b l e s . 3 .0 Theorem. D I n 1 ( A ; n ; P ^ « I n 1 ( A ; n ; k + 1 5 where k=card P. P r o o f . Let D = D I n 1 ( A 5 n ' P ) , E = I n 1 ( A ; n ; c a r d P + 1 > , P = { p 1 , . . . , p k J . Augment E by a s i n g l e element o f f i n i t e memory, map, whose domain i s { x|xe ( P { 1 , . . . , n } X (P+{-})) , | x ' < (card P)+n}. E keeps a complete record o f the order o f heads and pebbles f o r D. The va lue <H^, t - j> . . .<H r , t r > (a s t r i n g of l e n g t h r over P { 1 , . . . , n } X(P+{ - } ) ) f o r map r e p r e s e n t s a c o n f i g u r a t i o n m of D i n which ( i ) t ^ . . . t i s a subsequence o f -m(marks ) - i n c l u d i n g a l l occurrences o f a c t u a l pebb les ; ( i i ) i f t^ 6 P then i s the set o f heads on the same square as t ^ ; ( i i i ) i f t^=- then i s the set o f a l l heads on some one square wi thout a pebb le ; ( i v ) i < i ' and j e H^, j'eH^' i m p l i e s h j < h j ' j (v) u ! [ = 1 H i = { 1 , . . . , n } ; ( v i ) vr=1 <H i,t i>^<D,->. Def ine fg iDg -^Eg :m|->m' where i f !m( input ) ! = !m(marks)! & C¥ N = 1 0<m(hj)< |m( input ) 1+1) & ( ( ¥ p 6 P , E u , u ' , v , v ' ) m(marks)=upv=u'pv' i m p l i e s u=u' , v=v') then ( i ) m' ( input)=m(input) ( i i ) m'(marks)=uniform(m(marks)) ( i i i ) ¥ n = 1 m'(hj)=m(hj) ( i v ) m'(map)=select(merge(m)) Chapter I I 34 e l s e m'( input)=m'(marks)=S, ¥ n = 1 m' (h j )=0, m'(map)=B where m e r g e : D Q ( ( A + f h , H } ) X P { 1 , . . . , n } X (P+{-}))* :<input . m a r k s , h 1 , . . . , h n > r > < x 0 , H 0 , t 0 > . . - < x r + i > H r + 1 i t r + . , > where ( i ) hinputH = x 0...x r + 1, - ¥ [ + J Xj^eA+d-.Hl ( i i ) vJ+J H i z t j l h j s i , 1<j<n} „ - f p i f (Eu,v) marks=upv, | u ! = i - 1 , p 6 P ( i i i ) ¥ [ + J t± = { u L - o therwise s e l e c t :((A+{|-,H} XP{1 n) X (P+{->) )*->(P{1,.... ,n} X(P+{ - } ) )* :S r>* f<H,t>select(w) i f UtU v ti-:<x ,H, t>Wr>< (^select(w) o therwise uniform: (P+{ - } )* ->2* :&h>* f1(uniform(x)) i f p 6 P :pxr>< LO(uniform(x)) i f p=-*I : -Q~*-Q : m r * m ' w h e r e m'=m except tha t m'(map) = <{ 1 , . . . ,n} , - > ; and f 0 = I d E Q ' Def ine the f o l l o w i n g programs T -' I " $map<-<{1, . . . ,n } ,-> $ 0 : T _ 1 o -©No i &0: Chapter I I i 35 i (*) |same s q u a r e d , j ) -°—^©map<-u<H\{j} ,t><H' U {j} , t '>v where fo rmer l y map=u<H,t><H',t'>v, J 6 H , i 6 H ' i l l j = -i^®map<- (map)<{ j} ,-> |A i l M j = - Q - > ® m a p < - u < H \ { j } , t > < { j } , - > v where fo rmer l y map=u<H,t>v, j 6H | i 4 <j»map<-u<H\{j} ,t><{ j} ,p>v where fo rmer l y map=u<H,t><D,p>v, j 6 H , p 6 P ©0: (*) a l l such nodes itj, 1<i<n, are present ¥?_^ fj^i same s q u a r e ( i , j ) i s the program Chapter I I 36 I (Eu ,v ) map=u<H,p>v h 6X i I ©map<-u<H,p>v where fo rmer l y map=u<H,->v, j 6H ®"o: i t . i J ®map<-u<H,->v where fo rmer l y map=u<H,p>v, j e H , p e p Jo: ( ¥ j = 1 J rMj= i SM.= 0 ->©-: i J I1 &(Eu,v) map= u<H,p 1>v, j e H [ ]u<H,p k>v, j e H ®PV Ip k: An a p p l i c a t i o n of the s i m u l a t i o n theorem b r i n g s us to the d e s i r e d r e s u l t . 1 3 .0 Thus d e v i c e s w i t h d i s t i n g u i s h e d markers may be s imulated by a dev i ce w i t h un i form markers a t the expense o f a f i x e d constant i n c r e a s e i n the number o f markers . I t would be i n t e r e s t i n g to know whether t h i s i n c r e a s e i s s u b s t a n t i v e or s imp ly an a r t i f a c t o f the p r o o f , t h a t i s , whether there e x i s t s a language which i s D I n 1 ^ A ; n ; M ^ - a c c e p t a b l e but not I n 1 ^ A ; n ; k ^ - a c c e p t a b l e where k=card M. Though I cannot answer t h i s q u e s t i o n , one c a n , i n some c a s e s , o b t a i n from a program {"[ f o r D I n 1 ^ A ; n ' P ^ an e q u i v a l e n t program V f o r i n 1 ^ A ; n ' k ^ where k=card P. 3 -1 Theorem. Let f l be a program f o r D=DIn1( A 5 n 5 p ) such tha t i f <z 0 ,m Q> Chapter I I 37 ... <z r,m r> e C(i~[,D), z0=ITs, (Ex) m 0 =Dj(x) , x 6 A* then ¥ [ _ 0 m i ( h 1 ) > . . . > m i ( h n ) . Then there e x i s t s a program V f o r E = I n 1 ^ A ; n ; k ^ , k=card P such tha t Drj P r o o f . (Sketch) A c a r e f u l study o f the proof tha t D I n 1 ^ A ; n 5 p ) « I n 1 ( A ; n ; ( c a r d P)+1) w i l l r e v e a l t n a t t n e a d d i t i o n a l uni form pebble i s on ly r e q u i r e d to d e t e c t head c o i n c i d e n c e - i n t h i s manner the order o f the heads on the input tape i s known to I n 1 , p e r m i t t i n g i t to i n f e r the order and d i s t r i b u t i o n o f the d i s t i n g u i s h e d markers o f DIn1, i n f o r m a t i o n tha t i s c r u c i a l to the s u c c e s s f u l s i m u l a t i o n o f D I n 1 ^ A ; n ; P ^ by I n 1 ( A ; n ; ( c a r d p ) + 1 ) . S ince i n t h i s case the o r d e r i n g of the heads o f DIn1 i s known a p r i o r i the e x t r a pebble may be d ispensed w i t h . The essence o f the c o n s t r u c t i o n i s the augmentation o f E w i t h an element ft of f i n i t e memory, map, whose domain i s {x!x 6 ( P { 1 , . . . ,n} X (P+{ - } ) ) , jx|<(card P)+n}. The va lue o f map, <H.| , t ^ > . . -<H R,t r> r e p r e s e n t s a c o n f i g u r a t i o n m of D i n which ( i ) t ^ . . . t r i s a subsequence of -m(marks ) - i n c l u d i n g a l l occur rences o f a c t u a l pebb les ; ( i i ) i f t^ eP then i s the set o f heads on the same square as t ^ ; ( i i i ) i f t^=- then i s the set o f heads which l i e between a p a i r o f pebbles p and p ' - p to the l e f t and p ' to the r i g h t - w i t h no pebble p" between the two, or H^ i s the set of heads l e f t [or r i g h t ] of a l l pebb les . I f j j j ' e t L then i t i s not n e c e s s a r i l y t r u e tha t h ^ h ^ ' . To i l l u s t r a t e , the map <H0,p><iiv-><H2,p'> i n d i c a t e s tha t HQ i s the set o f heads scanning marker p, H^ the set o f heads l y i n g somewhere between p and p ' , and H 2 the set o f heads scanning p ' . ( i v ) i < i ' , j e H i ? j ' e H ^ ' i m p l i e s h i < h i ' j (v) Ur=1 H i = { 1 , . . . , n } ; ( v i ) V[ = 1 <H i , t i >>.<D,->. The i n i t i a l v a l u e o f map i s < { 1 , . . . , n } , - > . The remainder o f the proof i s s i m i l a r to tha t o f (3 .0 ) and may e a s i l y be g i v e n . 1 3 .1 Chapter I I 38 Remark. A s i m i l a r r e s u l t , w i t h a n e a r l y i d e n t i c a l p r o o f , may be cas t f o r D=Aux X D I n 1 ( A ; n 5 p ) and E=Aux X I n 1 ( A ; n 5 k ) , k=card P. Proceeding i n the reverse d i r e c t i o n , the next two lemmas, by way o f s i n - | ( A ; n ; k ) a g a n i n t e r m e d i a r y , prove tha t In1 ^ A ; n ' k ^ « D I n 1 ^ A ; n ; P ^ where (card P)=k. 3.2 Lemma. i n 1 ( A ; n ; k ) « s I n 1 ( A 5 n ; k ) . P r o o f . Let D = I n 1 ^ A ; n ; k ) , E = s l n 1 ( A ; n ; k ^ . Let f Q = I d D n and f I = f 0 = I d Def ine the f o l l o w i n g programs T _ T _ 1 I - 1 o -®"o: « n T-•J-1 ij • I M j = 1° (Va eDc\{jj! 1<j<n}> Ta = [T D > a An appeal to the s i m u l a t i o n theorem completes the p r o o f . I 3.2 3.3 Lemma. s I n 1 ( A ; n ; k ) « p d D I n l ( A ' n 5 p ) where (card P)=k. P r o o f . Let D = s l n 1 ( A ' n ' k ) , E = p d D I n 1 ^ A ; n ; P ^ . We assume, wi thout l o s s o f g e n e r a l i t y , tha t P = { 1 , . . . , k } . Augment E by a s i n g l e element o f f i n i t e memory, a v a i l a b l e , whose domain i s P ( P ) . Def ine f Q : R e c ( D ) Q - > E Q :<S,m>r>m' where m' ( input )=m( input ) , im' (marks) ! = |m( input ) ! , m'(marks) 6{<->}*, ¥ j j = 1 m' (h j )=m(hj ) , m ' ( a v a i l a b l e ) = P . Chapter I I 3 : « m 0 , a 0 > — < m r , a r > , m r + 1 > h> i f fg (<m 0 , aQ> . . .<m r _ 1 , a r _ 1 >,m r )=m then ( i ) i f a r e{Ij=|1<j<n}'U {Mj=|1<j<n} then m ( i i ) i f a r=|j, 1<j<n then m' where m'=m except t h a t m'(marks)=u<xp>v where |u!=m(hj ) -1 , m(marks)=u<x>v, p=min (m(ava i lab le ) ) , m ' (ava i lab le )=m(ava i lab le )\ {p } ( i i i ) i f ar=Tj, 1<j<n then m' where m'=m except tha t m'(marks)=u<[x)>v where |u|=m(hj)-1, m(marks)=u<x>v, x=[x)p, p 6 P , m ' ( a v a i l a b l e ) = m ( a v a i l a b l e ) U{p} ( i v ) i f a r =R-j , 1<J< n » then m' where m'=m except t h a t m'(h.)=m(h.) + 1. f j :EQ->Eg :m|->m' where m'=m except tha t m ' ( a v a i l a b l e ) = P ; and fg=Idg . Def ine the f o l l o w i n g programs T -1 I " I ©"avai lable^-P 1 ® 0 : T 1 0 -I ©No 1 lo: 1 0 : ® < ®M.: = - 1 1 |{1,...,k} Chapter I I ®"available<-j a v a i l a b l e \ { k } 5 An appeal to the s i m u l a t i o n theorem completes the p r o o f . 1 3.3 F i g u r e 3-4 summarizes lemmas 3.0, 3.2 and 3.3. Chapter I I 4 D I n l ( A ; n ; M ) i I t I n 1 ( A ; n ; ( c a r d M)+1) i I v s I n 1 ( A ; n ; ( c a r d M)+1) i I t p d D I n 1 ( A 5 n ; M + { P } ) 3.4 F i g u r e The r e s u l t s below f o l l o w immediate ly from lemmas 2 .0 - 2 . 2 , 3 . 0 , 3 .2 and 3 - 3 . For b r e v i t y l e t D k > E n > k 6 { D I n 1 ( A i n > M k > , s D I n l ( A ' n ' M k ) , , p d D I n 1 ( A ; n ; M K ) > I n 1 ( A ; n ; k ) ( s I n 1 ( A ; n ; k ) } w h e r e MQ=[]. H ^ . , 0 { k } . 3 .5 Theorem. For n 6 N + U k = Q L ( D n > k ) = u k = 0 L ( E n > k ) . 3 .6 C o r o l l a r y . l £ = 1 U~ = 0 L ( D n > k ) = IJ~ = 1 fcCE^). 3 .7 Theorem. For n 6 N + U k = 0 t ( A u x X D n k ) = u f l 0 L ( A u x X E n > k ) . 3 . 8 C o r o l l a r y . U* = 1 U ^ 0 L ( A u x X D n > k ) = U „ = 1 U ^ Q L ( A u x X E n > k ) . Chapter I I 4 Normal fo rms. 42 The f o l l o w i n g d e v i c e s may be thought o f as normal forms f o r the two pr imary c l a s s e s o f marker automata. 4 .0 D e f i n i t i o n . Let A and P be f i n i t e s e t s . Let n G N . Then an ordered n-head one-way i n p u t dev i ce w i t h d i s t i n g u i s h e d markers P, ordered D I n 1 ^ A ' n ' P \ i s s p e c i f i e d thus ( w r i t i n g D f o r ordered D I n 1 ^ A ' n , P ^ ) : (Vi e { Q , S , T , I , 0 , C } ) D j = D I n l { A 5 n ; p > . (Va eD c\{Rj|1<j<n}) D a = D I n 1 a A 5 n 5 p ) . ¥ j = 1 Rj : < i n p u t , m a r k s , . . . , h j , . . .>'r -><<input,marks, . . . , h j + 1 , . . . > , 0 > i f f 0 < h j < ! i n p u t ! & V r < j h j < h r . ordered D I n 1 ^ A ' n ' P ^ i s no rmal l y a c t i v e f o r i n p u t , not f o r o u t p u t . ordered D I n 1 ^ A ; n ; P ^ i s i d e n t i c a l to D I n 1 ^ A ; n ; P ^ save f o r the r e s t r i c t i o n tha t no head may over take and pass another . I t may be f u r t h e r r e s t r i c t e d by i n s i s t i n g t h a t t e r m i n a t i n g computat ions end w i t h a l l heads scanning the r i g h t end marker and the tape c l e a n o f pebb les . More f o r m a l l y I o f f e r : 4 .1 D e f i n i t i o n . Let A and P be f i n i t e s e t s . Let n 6 N . Then a t i d y ordered n-head one-way i n p u t dev i ce w i t h d i s t i n g u i s h e d markers P, t i d y ordered D I n 1 ( A ; n ; P ) ? i s s p e c i f i e d thus ( w r i t i n g D f o r t i d y ordered D I n 1 ^ A ; n ; P ^ ) : (Vi 6 { Q , S , T , I , C } ) D ± = ordered D I n l { A ; n 5 P ) . D Q : < i n p u t , m a r k s , h 1 , h n > r > 0 i f f marks 6{ - }* & v"_1 h j=| input !+1 . ( V a e D c ) D a =ordered D I n 1 a A ; n 5 P ) . t i d y ordered D I n 1 ^ A ; n ; P ^ i s normal l y a c t i v e f o r i n p u t , not f o r o u t p u t . A s i m i l a r development i s p o s s i b l e f o r I n 1 ^ A ; n ' k ^ . 4 . 2 D e f i n i t i o n . Let A be a f i n i t e s e t . Let n , k 6 N . Then an ordered n-head one-way i n p u t d e v i c e w i t h k markers , ordered I n 1 ^ A ' n ' k ^ , i s s p e c i f i e d thus ( w r i t i n g D f o r ordered I n 1 ( A 5 n 5 k ) ) : (Vi e { Q , S , T , I , 0 , C } ) D± = I n l { A ; n ; k ) . Chapter I I 43 (Va eD c \ { R j i K j < n } ) D a = I n 1 a A ; n 5 k ) . V j = 1 R j : < i n p u t , m a r k s , . . . , h j , . . . > r > < < i n p u t , m a r k s , . . . , h j+1 , . . .>,0> i f f 0<hj<|input! & V j ^ j h j < h j ' . ordered i n 1 ^ A ; n ' k ^ i s normal l y a c t i v e f o r i n p u t , not f o r o u t p u t . 4.3 D e f i n i t i o n . Let A be a f i n i t e s e t , n , k e N . Then a t i d y ordered n-head one-way i n p u t d e v i c e w i t h k markers , t i d y ordered I n 1 ^ A ' n ' k ^ , i s s p e c i f i e d thus ( w r i t i n g D fo r t i d y ordered I n 1 ^ A ' n ' k ^ ) : (V i 6 { Q , S , T , I , C } ) D i = 0 r d e r e d I n l { A 5 n ; k ) . D 0 : < i n p u t , m a r k s , h 1 , . . . , h n > r > 0 i f f marks e {0}* & V n = 1 h j = ! i n p u t ! + 1 . (VaeD c) D a = ordered I n 1 a A 5 n ; k ) . t i d y ordered i n 1 ^ A ' n ' k ^ i s normal l y a c t i v e f o r i n p u t , not f o r o u t p u t . Remark. The ordered v e r s i o n s o f DIn1 and In1 are analogous to the normal mul t ihead w r i t i n g f i n i t e automata o f Sudborough [Sudborough 71] w h i l e the t i d y ordered d e v i c e s are the marker automata e q u i v a l e n t o f h i s type 2 mul t ihead w r i t i n g f i n i t e automata. The o b j e c t i v e o f lemmas 4.4 - 4 .7 i s to demonstrate tha t any language recogn ized by DIn1 v ' ' J i s accepted by the dev i ces o f 4.0 - 4.3. I beg in by showing tha t at the expense of a s i n g l e a d d i t i o n a l pebble any f u n c t i o n computable by DIn1 may be computed by an e q u i v a l e n t dev i ce whose heads never c r o s s . 4.4 Lemma. D I n 1 ^ A ; n ; M ^ « ordered D I n 1 ( A ; n ; P ^ where card P = (card M)+1. P r o o f . Let D = D I n 1 ( A ; n ; M ) , E=ordered D I n 1 ( A 5 n ; P ) where A+{|-,-|} = { a 0 , . . . , a r } , M={ m1>•••>ms) a n d P=M+{!}. Augment E by n+1 elements o f f i n i t e memory H i , . . . , H n where V " = 1 dom ^ = { 1 , 2 , . . . ^ } ( the i n t e r p r e t a t i o n be ing tha t i f H^=j then head^^ o f dev i ce E i s s i m u l a t i n g the a c t i o n s of headj o f d e v i c e D ) , and temporary , whose domain i s { 0 , 1 , . . . , n } . Device E i s s imply D w i t h the r e s t r i c t i o n tha t the heads o f E must never c r o s s ; head^ i s always a t l e a s t as f a r down the tape as head^ + ^ f o r i = 1 , n - 1 . E s i m u l a t e s D by u s i n g head^ to mimic the a c t i o n s o f the l e a d i n g head o f Chapter I I 44 D, h e a d n t o mimic the a c t i o n s o f the t r a i l i n g head o f D. When head^^ and h e a d j , i < j o f E, s i m u l a t i n g head^ ' and headj ' of D r e s p e c t i v e l y , are about to c r o s s ( tha t i s , headj i s about to over take head^) E in te rchanges the f u n c t i o n s o f the two, head^ t h e r e a f t e r s i m u l a t i n g head, : ' and head^ s i m u l a t i n g h e a d . : ' . E r e q u i r e s the e x t r a pebble to d e t e c t c r o s s i n g p o i n t s ; i t aan not r e l i a b l y depend on another pebble be ing f r e e s i n c e a l l o f the o thers may be i n a c c e s s i b l e . To c o n s t r u c t the s i m u l a t i o n d e f i n e fg.DQ->EQ :mh>m' where: (a) m' ( input )=m( input ) , m'(marks)=m(marks), m'(temporary) = 0 . (b) Let p be the pe rmuta t ion , p : { 1 , . . . , n } - > { 1 , . . . , n } de f ined by ( i ) m ( h p ( 1 ) ) > m ( h p ( 2 ) ) > . . . > m ( h p ( n ) ) and ( i i ) m ( n p ( i ) ) = m ( h p ( i + 1 ) ) i m p l i e s p ( i ) < p ( i + 1 ) . Then ¥ ? = 1 m ' ( h i ) = m ( h p ( i ) ) , m ' d L ^ p U ) . Example. Let m=<x,y ,0,5,3,3> 6 D I n 1 ^ A 5 4 ; M ) then f Q (m) = < x , y , 5 , 3 , 3 , 0 , H - j ,H 2 ,H2,Hi|,temporary> where =2, H 2=3, H3 = i*> H4=1 » temporary=0. Def ine f T :EQ->EQ :mr>m' where m'=m except tha t ¥"_^ m'(H^) = i ; and f 0 = I d E Q -Def ine the f o l l o w i n g programs: T -1 I " IH.,<- 1 ®"o: 1 o -©No i Id: Chapter I I ¥ j _ i l e t s i m u l a t i n g ( j ) be the program i 1 : ® < — i — S H 1 = J , 1 |{1, . . . ,n}\{ j } n - 1 : © <— - .—SH 1 J i n - i j {1 , . . . , n }\ { j } H - 1 = | { 1 , — ,n}\{ j} n:®<- •—IH = J n Remark, s i m u l a t i n g ( j ) r e t u r n s the index of the head o f E tha t s i m u l a t i n g the a c t i o n s o f headj o f D. « 5 . i > r i , . -s i m u l a t i n g ( j ) ¥p eM) T. n = s i m u l a t i n g ( j ) s i m u l a t i n g ( j ) Chapter II ( V n - i ) . 'j = 1 ' 1 M simulating(j) -:®4 Vj_2 l e t s a m e square(i,j) be the program I s e e s ( i , j ) I l i = i 1 I - i *1 i-1 1 V j _ 2 s e e s ( i , j ) i s the program . © < — j — I M , : J i ! i 1 |M+{-} l T . i J I-i. m1 jM+{-}\{m.,} 1 m V n _2 l e t l e a s t index(j) be 1:®<—Q—Isame square(1,j) j-1:®<—Q—Isame square(j-1,j) Chapter I I 1-1 ( ¥j= 2 s w a p ( i , j ) = i ^temporary*-temporary &temporary4- 0 !(): R -j ® <—=j—Is imul at i n g (j) l e a s t index ( 2)I swap(1,2)© swap(1 ,n)I I l e a s t index(n) n-1 K-1 47 Iswap(n -1,n) l R n 8 A p p l i c a t i o n o f the s i m u l a t i o n theorem completes the p r o o f , i 4 .4 4 . 5 Lemma, ordered D I n 1 ^ A ; n ; P ^ << t i d y ordered D I n 1 ^ A ' n ; P ^ . P r o o f . Let D=ordered D I n 1 ^ A ' n ; P \ E=tidy ordered D I n 1 ^ A ; n ' P ^ and assume that P={p-|,. . . , p k J . Augment E by one element o f f i n i t e memory, a v a i l a b l e , whose domain i s P ( P ) . Const ruc t a s i m u l a t i o n by d e f i n i n g fQ:DQ->E n :m|->m' where i f |m(input)!=!m(marks)! & (V n = 1 m(hj)<jm(input)1+1) then ( i ) m ' ( input )=m( input ) . ( i i ) V n = 1 m ' ( h j ) = m ( h j ) . ( i i i ) m'(marks)=u'v where m(marks)=uv, | u ' | = |ui=m(h ) - 1 , u ' 6 { - } * . ( i v ) m ' ( a v a i l a b l e ) = P \ { p | p 6 P , (Eu,v) such tha t m(marks)=upv}. e l s e m'( input)=m'(marks)=S, V n = 1 m' (h j )=0, m'(avai lable)=D. Chapter I I f I : - Q ~ * - Q : m r>nT where m'=m except tha t m ' ( a v a i l a b l e ) = P . f 0 : EQ ->Eg :mr>m' where m'=m except tha t V n _ 1 m ' ( h . ) = i m ' ( i n p u t ) im ' (marks ) != im(marks ) ! , m'(marks) 6 { - } . Def ine the f o l l o w i n g programs T -' I " I ©"available^- P 0 = V<—ATfFT Kt<—c ?i„= (Va 6 { R j ! K j < n - 1 } U {Ij=.1<j<n} U {Mj=|1<j<n}) J i ' R„ -_ rt a - " D , a " I l = '» n \ ©M = [ r r . n^ r n f $ 0 : Chapter I I A p p l i c a t i o n o f the s i m u l a t i o n theorem completes the p roo f . 1 4.5 The next lemma i s the c r u c i a l l i n k i n e s t a b l i s h i n g a c h a i n o f s t a b l e r e d u c i b i l i t y from D I n 1 ^ A ' n ; P ^ to I n 1 ^ A ' n ; k ^ . 4 .6 Lemma, t i d y ordered D I n 1 ^ A ' n ; M ^ << t i d y ordered i n 1 ^ A ; n ' k ^ where k=card M. A proof s i m i l a r to tha t o f theorem 3 .0 can e a s i l y be g i v e n . 4 .7 Lemma, t i d y ordered i n 1 ^ A ! n ' k ^ << ordered I n 1 ^ A ; n ' k ^ . P r o o f . Let D=tidy ordered I n 1 ( A ; n ; k ) , E=ordered I n 1 ( A ; n ; k ) . Augment E by one element o f f i n i t e memory, c l e a n , whose domain i s {0 ,1} . Def ine f 0 . D 0 - > E 0 by Chapter I I 50 m :mr>m' where m' ( input )=m( input ) , m'(marks)=m(marks), ¥ j _ 1 m' (h j )=m(hj ) , x fO i f m(h n)=0 v ( ( E u , v ) , u e{-}* m(marks)=uv, |u|=m(h n)-1) ( c lean) =< " n 1.1 o therwise f I : - Q ^ - Q : m r > m ' where m'=m except tha t m' (c lean) =0, f 0 : E . Q ^ Q , f m i f m(clean)=0 & ( ¥ n , m(h .) = |m(input)|+1) :m|-> < j - 1 j (^undefined otherwise Def ine the f o l l o w i n g programs T -1 I " I Iclean<- 0 i 0?aeg c\{Rn}) Ta = T^.a Chapter I I 51 A p p l i c a t i o n o f the s i m u l a t i o n theorem completes the p roo f . 1 4 .7 4 . 8 Lemma, ordered I n 1 ( A : n : k ) « i n 1 ( A ; n ; k + 1 ) e P r o o f . Let D=ordered I n 1 ^ A ' n ! k ^ , E = I n 1 ^ A ; n ; k + 1 ^ . Augment E by one element o f f i n i t e memory, c o u n t e r , whose domain i s { 0 , 1 , . . . , k } . Def ine f Q :DQ->Eg :mr>m' where m' ( input )=m( input ) , m'(marks)=m(marks), Vn_1 m ' ( h i ) = m ( h i ) , m'(counter)=min{count(m(marks)) ,k} [count:2*->N :*r>0 :tx|->t+count(x) where t e { 0 , 1 } ] . f I = f O = I d E Q ' Def ine the f o l l o w i n g programs _ T-I - 1 o -I ©No i lo: (¥aeD c \ ( { R j | 2 < j < n } U{|j|1<J<n} U {Tj I 1<j<n})) Va = rf D j. I ©"same s q u a r e ( i , j ) v 1 i1 ©"same s q u a r e ( j - 1 , j ) ll i J ®"o: Chapter I I cv1? , ) r . .1=1 •* Icounter= | { 0 , 1 , . . . , k - 1 } Icounter<-counter+1 52 ( ¥ j = 1 ) r T . I T . I J Icounter<-counter-1 ¥ n _2 same s q u a r e d , j ) i s the program A p p l i c a t i o n o f the s i m u l a t i o n theorem completes the p r o o f . Remark. Dur ing a computat ion , D, w i t h a l l k pebbles down on i t s tape may attempt an ^ commmand, l e a v i n g the dev i ce i n an undef ined s t a t e . E, w i t h an Chapter I I a d d i t i o n a l pebble a v a i l a b l e would execute the i n s t r u c t i o n (assuming tha t no other pebble was occupying the square scanned by head.:) thereby f a i l i n g to p r o p e r l y s i m u l a t e D. The f i n i t e memory e lement , c o u n t e r , prevents t h i s . A: i n the proof o f theorem 3.0, an e x t r a pebble i s needed to d e t e c t head c o i n c i d e n c e . 1 4.8 F i g u r e 4.9 summarizes lemmas 4.4 - 4.8. D I n 1 ( A ; n ; M ) t I t ordered D In1(A ;n ;M + { ! } ) t i d y ordered D I n 1 ( A ; n ; M + { * } ) t i d y ordered In1 ^ A ' n » ' k + 1 ) where k=(card M) I v ordered In1 (A>*n;k+1) i I v I n 1 ( A ; n ; k + 2 ) 4.9 F i g u r e Chapter I I I 0 I n t r o d u c t i o n . 54 O n e - l e t t e r languages are the i d e a l t e s t i n g ground f o r determin ing the advantages con fe r red by the l i m i t e d w r i t i n g a b i l i t i e s o f one-way mul t ihead marker automata. S ince the sentences o f a s i n g l e - l e t t e r language have no i n t e r n a l f e a t u r e s t h a t would a s s i s t i n t h e i r a n a l y s i s , we are assured tha t the r e c o g n i t i o n o f a p a r t i c u l a r language not accepted by other s t r u c t u r a l l y s i m i l a r dev i ces i s due s o l e l y to the use of markers . I t i s a l s o u s e f u l to app ly one-way mul t ihead marker automata to o n e - l e t t e r languages accepted by d e v i c e s which are g e n e r a l i z a t i o n s o f , and t h e r e f o r e i n t u i t i v e l y more powerful t h a n , one-way mul t ihead marker automata. To t h i s end I w i l l prove t h a t a number o f o n e - l e t t e r languages recogn ized by one-way mul t ihead w r i t i n g f i n i t e automata are a l s o accepted by one-way mul t ihead marker automata, thereby demonstrat ing t h a t , f o r these languages at l e a s t , the a b i l i t y to w r i t e a r b i t r a r i l y i s not r e q u i r e d . I beg in i n s e c t i o n 1 by showing tha t the languages L k = { 0 U ; i n 6 N } (k a f i x e d i n t e g e r >2) proved by Sudborough [Sudborough 71] to be acceptab le by a n o n d e t e r m i n i s t i c one-way 2-head w r i t i n g f i n i t e automaton, are Aux X In1 ' 2 ' k ^ - a c c e p t a b l e . The s i m p l e s t o f t h e s e , L g , be ing i n p a r t i c u l a r I n 1 u ' - a c c e p t a b l e . Not a s i n g l e member of t h i s c l a s s i s recogn ized by any n o n d e t e r m i n i s t i c one-way mul t ihead f i n i t e automaton [Rosenberg 6 4 ] , n o n d e t e r m i n i s t i c one-way mul t ihead pushdown automaton [ H a r r i s o n and I b a r r a 68] or any d e t e r m i n i s t i c bounded r e v e r s a l mul t ihead f i n i t e automaton [Sudborough 7 4 ] . In a d d i t i o n , i s not recognized by any n o n d e t e r m i n i s t i c one-way mul t ihead s tack automaton [ G i u l i a n o 7 0 ] . These languages are g e n e r a l i z e d i n s e c t i o n 2 to L p ( x ) = { 0 p ^ n ^ | n e N } , p(x) a po lynomia l w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s , where I show that L p ( x ) i s In1 ' k ' k - ^ - a c c e p t a b l e , k be ing the degree of p ( x ) . I t f o l l o w s there e x i s t d e t e r m i n i s t i c marker automata languages not recognized by any n o n d e t e r m i n i s t i c one-way mul t ihead f i n i t e automaton [Rosenberg 6 4 ] , n o n d e t e r m i n i s t i c one-way mul t ihead pushdown automaton [Har r i son and I b a r r a 6 8 ] , d e t e r m i n i s t i c bounded r e v e r s a l mul t ihead f i n i t e automaton [Sudborough 74] or n o n d e t e r m i n i s t i c one-way mul t ihead s tack automaton [ G i u l i a n o 7 0 ] . S e c t i o n 3 e x h i b i t s a d i f f e r e n t c l a s s o f o n e - l e t t e r languages , c h a r a c t e r i z e d by constant l i n e a r d i f f e r e n c e e q u a t i o n s , tha t are a l s o Chapter I I I 55 d e t e r m i n i s t i c a l l y a c c e p t a b l e , u s i n g a t most 2 pebb les . Desp i te t h e i r resemblance to the languages o f s e c t i o n 2 , there are members o f t h i s c l a s s not generable by any p o l y n o m i a l , p rov ing tha t a complete c h a r a c t e r i z a t i o n o f the o n e - l e t t e r languages recogn i zed by one-way mul t ihead marker automata can not r e s t upon the po lynomia l languages a l o n e . Chapter I I I 1 N o n d e t e r m i n i s t i c o n e - l e t t e r languages. 56 2 1.0 Theorem. The language L={0^ n ^|neN+} i s i n i ( { 0 } ; 2 ; 1 ) (hence Aux X I n 1 ( { 0 } > 2 > 1 > ) - a c c e p t a b l e . Proof Let D = I n 1 ^ 0 } ; 2 ; 1 ^ and l e t fT be the program z:advance where advance i s the subprogram •2 f R 1 I We a s s e r t tha t dom(Dri) = {0^ n '|neN+}. Observe tha t the d i s t a n c e between the two heads i s always odd, i n c r e a s i n g by two f o r each c y c l e o f the loop c o n t a i n i n g nodes z and z'. I t i s easy to prove by i n d u c t i o n on n , the number o f occur rences o f z i n <fig,Dj(x)>.. .<z,m><z' ,m'> e C(fT,D), tha t n+1 n m'(h.,)=(J 2 j -1)+1 and m'(h2) = ()" 2 j - 1 ) + 1, ~J=1 ~j=1 consequent ly m'(h 1)=(n+1) 2+1 and m'(h 2 )=n 2 +1. I f the l e n g t h o f the input s t r i n g i s a p e r f e c t square then headj w i l l f i n d i t s e l f scanning the r i g h t Chapter I I I 57 endmarker and by c o n s t r u c t i o n o f IT, h a l t , o therwise i t w i l l be fo rced o f f the end of the t a p e , i 1.0 We can now show t h a t one-way mul t ihead marker automata are s t r i c t l y more powerfu l than one-way mul t ihead f i n i t e automata. ft 1.1 Theorem. [ H a r r i s o n and I b a r r a 68] Let a eA be g i v e n . I f L e f a ) i s recogn i zed by A u x X I n 1 ^ A ' n ^ X P d s ^ then L i s a r e g u l a r language. ft I b a r r a ' s proof proceeds by demonstrat ing tha t L<={a} i s A u x X I n 1 ^ A ' n ^ X P d s ^ - a c c e p t a b l e i f and on ly i f L i s s e m i l i n e a r . S ince a l l s e m i l i n e a r languages over a o n e - l e t t e r a lphabet are r e g u l a r the r e s u l t f o l l o w s . Let L^{a}* be g i v e n , fT a program f o r machine M = A u x X I n 1 ^ A ' n ^ such tha t L=dom R(ff ,M). I t f o l l o w s tha t IT i s a program f o r A u x X I n 1 ( A ; n ) X P d s ( B ) i m p l y i n g 1.2 Theorem. I f L<={a}* i s recognized by A u x X I n 1 ^ A ' n ^ then L i s r e g u l a r . 1.3 C o r o l l a r y . ¥n>2, ¥k>1, L ( I n 1 ( A ; n ) ) ( _ L ( l n 1 ( A 5 n 5 k ) ) and L(Aux X I n 1 ( A ' n ) ) c=L(Aux X I n 1 ( A 5 n 5 k ) ) . P r o o f . I n c l u s i o n i n both cases f o l l o w s immediate ly from the d e f i n i t i o n 2 o f I n 1 ( A ; n ; k ) . Let a e A be g i v e n . S ince L = { a ( n ) in 6N + } e L ( I n 1 ( A ; 2 ; 1 h <= L ( I n 1 ( A ; n ; k ) )<=L(Aux X I n 1 ( A ; n ; k ) ) i s not recogn ized by A u x X I n 1 ( A ; n ) f o r any n>2, the i n c l u s i o n s are proper , i 1-3 ( A • n • \c) I t a l s o f o l l o w s tha t there are languages which are I n 1 v ' ' J [Aux X I n 1 ( A ; n ! k ) ] - a c c e p t a b l e , n>2, k>1 which are not Aux X I n 1 ( A ; m ) X P d s ( B ) - a c c e p t a b l e f o r any m or B. I t i s easy to c o n s t r u c t a program f o r I n 1 ^ X S t ^ which accepts {0^ n ^ i n e N + } . However, G i u l i a n o has proven tha t L = { 0 ( n ) i n 6 N + } i s not A u x X I n 1 ( A ) X S t ( B ) - a c c e p t a b l e [ G i u l i a n o 7 0 ] . The Chapter I I I 58 r e s u l t s which f o l l o w prove tha t L i s both Aux X In1 ; 2 ; 3 ) a n ( j I n 1 v l J , J ' - a c c e p t a b l e . Consequently there e x i s t languages recognized by a d e t e r m i n i s t i c one-way 3 -head 2-marker automaton which are not recognized by any one-way n o n d e t e r m i n i s t i c s t a c k automaton. Sudborough [Sudborough 71] a l s o demonstrates tha t {0^ n 'ineN +} i s a c c e p t a b l e by a n o n d e t e r m i n i s t i c 2-head w r i t i n g f i n i t e automaton and remarks tha t the argument may be e a s i l y g e n e r a l i z e d to show that f o r any k 6 N + / ks L k={Cr ; | n e N } i s acceptab le by a n o n d e t e r m i n i s t i c 2-head w r i t i n g f i n i t e automaton. A s i m i l a r argument may be employed to show t h a t L k i s acceptab le by Aux X i n 1 ( { 0 } ; 2 ; k ) # 1.4 Theorem. F i x k 6 N + . Then the language L k = { 0 ( n MneN +} i s Aux X I n 1 ( * ° * ; 2 ; k ) - a c c e p t a b l e . P r o o f . (Sketch) S ince s D I n 1 ^ A ; n ; P ^ « D I n 1 ^ A ; n ; P \ i t i s s u f f i c i e n t by theorem I I . 3 . 1 to p rov ide a program nk f o r D=Aux X s D I n l ( A ; n , P ) w n e r e c a r d p=k, P = { P l , . . . >Pk_i »'•) > such t h a t i n a l l computat ions by f l on D ( a c c e p t i n g or o therwise ) the heads never c r o s s . The a l g o r i t h m r e s t s upon the o b s e r v a t i o n made by Sudborough tha t there are n s t r i n g s x 6 ( 0 , 1 ) of l e n g t h n which have one and on ly one occurrence o f the symbol 1. I t f o l l o w s tha t there are n tapes o f l e n g t h n w i t h k -1 # t r a c k s such tha t each t r a c k c o n t a i n s a s t r i n g x e { 0 , 1 } o f l e n g t h n w i t h p r e c i s e l y one occurrence o f the symbol 1. By forming between two heads each o f these t a p e s , a dev i ce can measure whether the l e n g t h i s o f n k , n 6 N + . The l e n g t h o f the i n i t i a l s t r i n g between the two heads i s chosen by c o n s u l t i n g an Aux t a p e . An a l t e r n a t i v e po in t o f v iew , b e t t e r s u i t e d to s D I n l , i s to t h i n k o f the k -1 d i s t i n g u i s h e d markers l y i n g between the two heads as p l a c e h o l d e r s i n the e x p r e s s i o n o f a number i n base n , count ing from zero to n k _ ^ - 1 i n c l u s i v e w i t h the p o s i t i o n o f p^  r e p r e s e n t i n g the l e a s t s i g n i f i c a n t d i g i t , P 2 the next l e a s t s i g n i f i c a n t d i g i t and so on . Augment D w i t h an element of f i n i t e memory, t , whose domain i s P{p- j , . . . , P k _ 1}. n k i s the program Chapter I I I "guess .1*1' 1 f t 2 P l v ?v 2P k-1 J -^.©"finished where guess i s the program iA r^T^>©R 1 i 1 1 and f i n i s h e d i s the program i 1 :©<_J—| P i e M i k i « — 1 — f p 2 e M i lo 1 1 ^ - f P k - i e M i lo Jo: Chapter I I I and advance i s the program and r e s e t i s the program I> 6 M 2 1-c k u p l putdown®" Chapter I I I and p ickup i s the program ® t < - t U {p2} lo l t < ^ t u { p k _ 1 } Chapter I I I and putdown i s the program I p-i e t o f v 2 p 1 ] * P 2 e t o t / fPk -1 e t f * 2 P k - 1 and V^_2 move(p^) i s the program / ? P i e M 2 .-2Pi f t i P i I >lu: k -1 and increment(p^) i s the program i IR. i i j R 2 @ < _ L l p.eM 2 o IT. I IR. ft IPJ Chapter I I I i 1.4 63 1.5 Example. The diagram below i l l u s t r a t e s the f i r s t few s teps i n the acceptance of 0 ( 3 ) eLg by running on Aux X s D I n l ( { 0 } ; 2 ; P ) . The numerals " 1 " and " 2 " represent heads 1 and 2 r e s p e c t i v e l y and the symbols " a " and " b " represent the pebbles p 1 and p 2 mentioned i n theorem 1 . 4 . count H 0 0 0 0 0 0 0 0 0 0 o o n 0 0 1 2 00 2 a h 1 1 01 2 b a 1 i '02 2 b 1 a ! 10 2 a b 1 i 11 • • • 2 a b 1 i E n t r i e s i n the column "count" g i v e the r e l a t i v e p o s i t i o n s ( w i t h i n the tape segment o f l e n g t h n bracketed by the two heads) of the markers p 2 P i ( i n that order ) when the node " f i n i s h e d " i s reached . Regarded as a number t w r i t t e n i n base n , each "count" ent ry a l s o s p e c i f i e s the p o s i t i o n of the l e a d i n g head as n*(t+1). From t h i s , we can aga in see the s u i t a b i l i t y o f ["1^ .: i f i t h a l t s , the l a s t "count" ent ry w i l l have shown p^=p 2=..•=Pj c_i=n-1, r e p r e s e n t i n g n k - 1 - 1 i n base n and s p e c i f y i n g the l e a d i n g head p o s i t i o n (on the l a s t 0) as n k . Chapter I I I 64 2 D e t e r m i n i s t i c o n e - l e t t e r languages. The program g i ven w i t h theorem 1.4 may, wi thout d i f f i c u l t y , be r e w r i t t e n t o accept { C r a n ^ n 6 N + } f o r c o n s t a n t s a , k 6 N + . From t h e r e i t i s a s t r a i g h t f o r w a r d e x t e n s i o n to c o n s t r u c t a program f o r Aux X In1 >2>k) to recogn i ze { 0 ^ n ^ ! n eN +} where p(x) = a k x k + a K_.|X K~ 1 + ... + a^x + a.Q i s g i ven f o r c o n s t a n t s k 6 N + , a Q , a ^ , . . . , a k eN. (Paste t o g e t h e r , i n s u c c e s s i o n , programs f o r the r e c o g n i t i o n o f ( o ' a j n ^ | n eK +}, j = 0 , . . . , k , i n s e r t i n g at each j u n c t i o n the a p p r o p r i a t e i n i t i a l i z a t i o n s . ) The f o l l o w i n g development shows tha t i f p(x) i s a po lynomia l o f degree k>0 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s , then i t i s p o s s i b l e to to compute {O p^ n^|neN} d e t e r m i n i s t i c a l l y a t the expense of i n c r e a s i n g the number of heads to k (but w i t h one l e s s pebb le , on l y k - 1 ) . A s i m i l a r r e s u l t i s c i t e d by Sudborough [Sudborough 76] f o r mul t ihead w r i t i n g f i n i t e automata f o r which he c l a i m s , but does not prove , tha t Lm={Cr Mn eN } f o r m>1 i s recogn ized by a d e t e r m i n i s t i c m-headed w r i t i n g f i n i t e automaton. The arguments here are based upon an a n a l y s i s o f the d i f f e r e n c e t r i a n g l e s ( t a b l e s ) of po lynomia ls w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Perhaps t h i s i s the approach Sudborough had i n mind. 2 .0 D e f i n i t i o n . Let X={x n}^.Q be any sequence o f r e a l numbers. The backward d i f f e r e n c e o p e r a t o r , denoted by V, i s d e f i n e d by ( V X ) n = x n - x n _ ^ . I n t e g r a l powers o f the operator are d e f i n e d i n d u c t i v e l y by the r e l a t i o n V k X = V ( V k - 1 X ) , k = 2 , 3 , . . . • I t i s a l s o convenient to s p e c i f y ( V ° X ) n = x n . The v a l u e s o f s u c c e s s i v e powers o f V are c o n v e n i e n t l y arranged i n a " t r i a n g l e " , as i n f i g u r e 2 . 1 . ( V 3 X ) 3 . . . ( V 2 X ) 2 ( V 2 X ) 3 . . . (VX)j (VX ) 2 (VX) 3 . . . XQ X-J ^2 ^3 • • • 2.1 F i g u r e F i g u r e 2 .1 i s c a l l e d the d i f f e r e n c e t r i a n g l e o f the sequence X. Each ent ry i n the t a b l e i s the d i f f e r e n c e of the two e n t r i e s immediate ly below i t . Chapter I I I 65 Lemma 2 .2 shows the r e l a t i o n s h i p between the base of the d i f f e r e n c e t r i a n g l e and the row immediate ly above i t . 2 .2 Lemma. Let X={x n }^Q be any sequence of r e a l numbers. Let Y={y n} ( n°_Q where y i = ( V X ) i + 1 . Then ( V i + 1 X ) J + 1 = W1?) y n 1 P r o o f . We proceed by i n d u c t i o n on i . We have (V Y ) j = y^ = (V X ) j + ^ . Assume the r e s u l t f o r i - 1 . Then ( V i Y ) j = V ( V i _ 1 Y ) J = ( V i _ 1 Y ) j - ( V i - 1 Y ) J _ 1 [by d e f i n i t i o n o f V] = ( V 1 X ) j + 1 - ( V l X ) j [by i n d u c t i v e hypothes i s ] = V ( V i X ) j + 1 I 2.2 Lemma 2 .3 shows tha t any element x^ + ^ of a sequence X = X Q , X ^ , X 2 , . . . may be expressed as the sum of the preced ing element x^ and the l e a d i n g edge of the d i f f e r e n c e t r i a n g l e w i t h X as i t s base . 2 .3 Lemma. Let Y={y n }^Q be any sequence of r e a l numbers. Then ( f o r ieN) y i + 1 = y i + f ( | ) ( V k + 1 Y ) k + r k=0 P r o o f . .We proceed by i n d u c t i o n on i . We have 0 *i = y 0 + ^ i - y 0 ) = y 0 + < v l Y > i = y 0 +1 ( k > ( v k + l Y > k + r k=0 Assume the r e s u l t t r u e f o r i - 1 > 0 . Let X={xn}< n 3_0 where x i = ( V 1 Y ) i + 1 . Then by i n d u c t i v e hypothes i s we have tha t i - 1 x i = x i - 1 + / ^ k 1 ) ^ * ^ ) ^ k=0 i - 1 = x i _ 1 + ) ( ^ X ^ Y W [ ( V i X ) j = ( V i + 1 Y ) j + 1 by lemma 2 .2 ] k=0 Chapter I I I 66 i - 1 = ( V 1 Y ) i + J ( i k 1 ) ( v k + 2 Y ) k + 2 [ b y d e f i n i t i o n o f X i - 1 ] k=0 i = ( V 1 Y ) i ( j I i ) ( V j + 1 Y ) j + 1 where j=k+1 ~j = 1 i - 1 = ( V 1 Y ) i +) ( j l ] ) ( V j + 1 Y ) j + 1 + ( V i + 1 Y ) i + 1 j = 1 i - 1 = ( V 1 Y ) i + ) [ ( J M 1 } 1 ) ] ( V J + 1 Y ) j + 1 + ( V i + 1 Y ) i + 1 C(k) = ( n k 1 ) + (kZi)] j = 1 i - 1 i - 1 = ( V 1 Y ) i + ) ( j ) ( V J + 1 Y ) j + 1 - } ( i j 1 ) ( V J + 1 Y ) j + 1 + ( V i + 1 Y ) i + 1 j=1 j=1 i i - 1 = ( V 1 Y ) ± + [J ( j ) ( V j + 1 Y ) j + 1 - {lh), - ( V l + l Y ) i + 1 ] - [ ) ( l 3 1 ) (V J + 1 Y) j + 1 j=0 j=0 - (V 1 ! ) . , ] + ( V i + 1 Y ) i + 1 = (Vh)i+J ( j ) ( V J + 1 Y ) j + l -f 1 ( 1 J 1 ) ( V J + 1 Y ) J + 1 j=0 j=0 i - 1 i = y± - y i - 1 "I ( l j 1 ) ( v J + l Y ) j + 1 + / ( j ) ( V J + l Y ) j + 1 Cby definite" of V 1 Y ) ± ] j=0 j=0 = Y i " [Yi_1 + f 1 ( i j 1 ) ( V J + 1 ^ ) j + l ] +f ( J ) C V J - 1 Y ) J ^ 1 j=o j=o i = y± - y± + ^) (j)(V^"*'1 Y ) j + 1 [by i n d u c t i v e hypothes i s ] ~j=0 -f ( j ) ( v - J + 1 Y ) j + 1 . But = (V Y ) i + 1 = y i + *| -Y i by c o n s t r u c t i o n . Consequently y i + i = H +f < J ^ J + 1 Y > J + I as d e s i r e d . 1 2 . 3 Theorem 2 .4 s t a t e s tha t the k t h d i f f e r e n c e s o f a sequence x = f x n ] ' n 0 = o a r e i d e n t i c a l l y zero i f and on ly i f there e x i s t s a po lynomia l o f degree<k where p (n )=x n . Chapter I I I 67 2 .4 Theorem. Let the f u n c t i o n f be d e f i n e d on the whole r e a l l i n e , l e t k be a s t r i c t l y p o s i t i v e i n t e g e r and l e t h>0. I f x=f x n} rf-o» x n = f ( n h ) , a necessary and s u f f i c i e n t c o n d i t i o n i n order that (V k X) n =0 f o r a l l i n t e g e r s n i s t h a t f(nh)=p(nh) f o r a l l n , where p i s a po lynomia l o f degree<k. The reader i s r e f e r r e d to [ H e n r i c i 64 pp .143-144] f o r a proof o f t h i s fundamental f a c t o f numer ica l a n a l y s i s . We next c o n s i d e r , i n p a r t i c u l a r , the p r o p e r t i e s o f d i f f e r e n c e t r i a n g l e s o f po lynomia ls w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Our f i r s t r e s u l t shows tha t every en t r y i n such a t a b l e must be p o s i t i v e . 2 .5 Lemma. Let p(x) = a r x r + a r _^x r ~^ + . . . + a^x + aQ be a po lynomia l o f degree r w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Let X={p(n) }^.g. Then (V k X) n >0 . P r o o f . We proceed by i n d u c t i o n on r . For r=0, we have Vn e N p(n)=aQ>0. Assume the r e s u l t t r u e f o r r -1>0. Then r r p(n+1)-p(n) = y a i ( n + 1 ) i - y a ^ 1 ~i=0 - i = 0 r = ) a i [ ( n + 1 ) i - n i ] i=1 r i - 1 i i - 1 = ) a j (j )nJ ( s i n c e ( n + o W = [J ( JjnM - J ] - n 1 = J (J ) n J ) . ~i=1 ~~j=0 j=0 j=0 Observe tha t ( i ) p(x+1) -p(x) i s a po lynomia l of degree < r - 1 , tha t i s ( V X ) n = q(n) f o r some po ly lnomal q w i t h degree<r; ( i i ) the c o e f f i c i e n t f o r x m , 0<m<r-1, i s g i ven by ^ a i ^ m ^ ' —i=m+1 Thus q(x)=p(x+1)-p(x) i s a po lynomia l o f degree r - 1 w i t h p o s i t i v e c o e f f i c i e n t s . By i n d u c t i v e hypothes is i f Y={q(n)}'n 3_0 then (V k Y) n >0 f o r a l l m e a n i n g f u l k and n. S ince q(n)=p(n+1)-p(n)=(VX) n + ^ we have by lemma 2 .2 t h a t ( V k + 1 X ) n + 1 = ( v k Y ) n > 0 . S ince ( V ° X ) n = p ( n ) > 0 we have tha t (V k X) n >0. i 2 . 5 Chapter I I I 68 In a d d i t i o n , i t i s p o s s i b l e , wi thout l a b o r i o u s c a l c u l a t i o n , to determine the v a l u e s o f the r t h row o f a d i f f e r e n c e t a b l e whose base i s the sequence X mentioned i n the hypotheses o f lemma 2 .5 above. 2.6 Lemma. Let p(x) = a r x r + a r _ 1 x r ~ 1 + . . . +a^x + ag be a po lynomia l of degree r . Let X={p(n) }^_Q. Then ( v r X ) r = r ! a r -P r o o f . S ince by theorem 2.4 (v k X) n =0 f o r a l l k>r we must have that ( v r X ) n = c , a c o n s t a n t . Thus i t w i l l s u f f i c e to show that ( V r X ) r = r ! a r . We proceed by i n d u c t i o n on r . For r=0, we have (7° X ) 0 = p ( 0 ) = a 0 = 0 ! a 0 . Assume the r e s u l t f o r r -1>0. We can demonstrate , employing p r e c i s e l y the same argument as g i ven i n lemma 2 . 5 , tha t (V X) n + ^=q(n) where q i s a po lynomia l of degree < r - 1 whose c o e f f i c i e n t r f o r the term x m , 0<m<r-1 i s g i ven by ^ a i ^ n P " ^ n P a r t i c u l a r , the r —i=m+1 c o e f f i c i e n t f o r x r i s ^ a i ^ r - 1 ^ = r a r " — i = r Let Y = { q ( n ) } n = 0 . By i n d u c t i v e hypothes is (V Y ) r _ . , = ( r - 1 ) ! ( r a r ) = 2.6 r ! a r . S ince by lemma 2 .2 ( V r 1 Y ) r - 1 = ( v r X ) r the argument i s complete In what f o l l o w s , i t i s n o t a t i o n a l l y convenient to employ a v e r s i o n o f ( A • n • k) I n 1 v ' ' whose heads are numbered from 0 , . . . , n - 1 as opposed to the standard p r a c t i c e o f l a b e l i n g them 1 through n i n c l u s i v e . Thus a memory c o n f i g u r a t i o n has the form < i n p u t , m a r k s , h g , . . . > h n _ ^ > i n s t e a d of < i n p u t , m a r k s , h ^ , h f i > . 2.7 D e f i n i t i o n . Let p(x) = a k x k + . . . + a^x + ag be a po lynomia l of degree k>0 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Let fTp( x) be the f o l l o w i n g program f o r i n i ( ( 0 } ; k ; k - 1 ) . ( i ) k=1 i z 2 < — 5 — © i n i t i a l i z e g * — > ® z n a d v a n c e n | 0 0 ^ ^ © z . , :I = v ®z H 2: Chapter I I I 69 ( i i ) k>1 z 04 2^ 0 " i n i t i a l i z e 0 z-,4 2 V ~ 0 ~ ^ i n i t i a l i z e k -1 t k - 1 ? i 1 ! * 1 t f i k - 1 I >®"zQ:advanceQ ©advance^ ^ I ! z 1 : I k - 1 H where VJ_Q i n i t i a l i z e j i s the program © V > p(j)+1 t imes ®R . i ^ 0:®< _i Il,= Chapter I I I ¥ i - 0 a a v a n c e i i s the program -> i " 1 Y Y U ^ 1 ) times K - 1 Y W k i 1 ) t imes and advance k _^ i s the program k - 1 k - 1 > k ! a k t imes lO: 70 The program np(x) c o n s i s t s o f four phases: ( i ) the k heads 0 , . . . , k - 1 are moved to p o s i t i o n s p(0)+1, p(k-1)+1 r e s p e c t i v e l y . I f the input s t r i n g i s o f l e n g t h p ( i ) f o r 0<i<k-1 the program w i l l te rminate s u c c e s s f u l l y ; ( i i ) heads 1 , . . . , k - 1 each l a y down a pebble to mark t h e i r p o s i t i o n s ; k ? ( i i i ) V^_Q head^ moves to the square tagged by head^ + ^ f o r c i n g heads i + 1 , . . . , k - 1 to move ( i t 1 ) , ( k 7^) squares r e s p e c t i v e l y f o r each move o f head^. Head k _^ advances k ! a k a d d i t i o n a l squares a f t e r be ing fo rced forward by heads 0 , . . . , k - 2 . At t h i s po in t heads 0 , 1 , . . . , k - 1 are i n p o s i t i o n s p(n+0)+1, p(n+1)+1, p(n+k-1)+1 r e s p e c t i v e l y where n i s the number of t imes s tep ( i i i ) has been executed ; Chapter I I I 71 ( i v ) h e a d k _ i checks to see i f i t i s s t a n d i n g on the r i g h t endmarker. I f so the program h a l t s , o t h e r w i s e , head 0, now scanning the square fo rmer l y i n h a b i t e d by head 1, p i c k s up the pebble l y i n g beneath i t and " p a s s e s " i t to head k _^ which promptly marks the square i t o c c u p i e s . Steps ( i i i ) and ( i v ) are now r e p e a t e d . Lemmas 2.8 and 2.9 below are a fo rmal v e r i f i c a t i o n o f s teps ( i i i ) and ( i v ) . 2.8 Lemma. Let p(x) = a k x k + . . . + a^x + ag be a po lynomia l of degree k>0 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Let D = I n 1 5 k 5 k _ 1 ) . Let V be the program 1 IXQ radvanceQ * i & x k 1 : a d v a n c e k ^ i x k -where V^IQ advance.^ i s as g i ven i n d e f i n i t i o n 2.7 f o r v f p ( x ) - Choose n 6 N , y6{0}* such t h a t {y-| >p(n+k) , X = { x n } " n ° _ 0 where x j L=p(n+i) + 1. Let m 6 DQ be such tha t m(input)=y, V K " ] m(marks) = u 1 1 u 2 1 . . . 1 u k - 1 1 u k where ¥ k = 1 u ^ f O } * , V K"{ j u 1 1 . . . lu-j j \ = x i ( tha t i s heads 1 , . . . , k - 1 are each scanning a m a r k e r ) , jm(marks)!= i y j . I f <XQ ,mQ>.. . <x k ,m k> e C t (T~ ,D ) where mQ=m then ( i ) mQ(marks)=m^(marks)=.. .=m k(marks); ( i i ) ¥ k l J m±+^h±)- m i ( h i ) = ( V i + 1 X ) i + 1 ; ( i i i ) ¥ ^ l j m k ( h i ) = p(n+1+i)+1. P r o o f , ( i ) : S i n c e each subprogram advance^, 0<i<k-1 i s devoid o f i n s t r u c t i o n s o f the form |j or T j , 0<j<k-1, the a s s e r t i o n f o l l o w s immediately from the c o n s t r u c t i o n o f T~. ( i i ) : We f i r s t prove by complete i n d u c t i o n on i , 0<i<k-2, where k i s the Chapter I I I 7 2 degree o f the po lynomia l p(x) , t h a t V ^ Q m l + 1 ( h 1 ) - m i ( h j L ) = ( V l + 1 X ) i + 1 . The l a s t c a s e , m k ( h k _ i )-m k_-| (\_-|) = ( V k X ) k w i l l be d e a l t w i t h s e p a r a t e l y . Let i = 0 . Then by c o n s t r u c t i o n of T and advanceg we must have m-| (hQ)-mQ(hQ) = [ p ( n + 1 ) + 1 ] - [ p ( n + 0 ) + 1 ] = X ^ X Q = ( V 1 X ) r Assume the r e s u l t f o r i - 1 > 0 and cons ide r i . By i n d u c t i v e hypothes is ¥ J ~ Q m j + 1 ( h j ) - m j ( h j ) = ( V ^ + 1 X ) j + 1 . I t f o l l o w s from the c o n s t r u c t i o n o f V and advance j , 0 < j < i - 1 , tha t m i ( h i ) = mQ(h±) + ( j ) ( V 1 X ) 1 + . . . + ( i ^ 1 ) ( V i X ) i i - 1 = x ± + J ( j ) ( V J + 1 X ) j + 1 [by d e f i n i t i o n o f m Q ] . ~ j = 0 Now by c o n s t r u c t i o n o f advance^, head^ w i l l t r a v e l forward u n t i l i t encounters a marker , the nearest a c c e s s i b l e marker be ing tha t l o c a t e d at p o s i t i o n x^ +^ s i n c e x^<m^(h^)<x^+^. (I am i m p l i c i t l y making use of a s s e r t i o n ( i ) above. ) Thus m ^ d i ^ - m ^ ) i - 1 = x i + 1 - [ x l + J ( J ) ( V J + 1 X ) J + 1 ] j = 0 = ( V l + 1 X ) i + 1 [by lemma 2 . 3 ] . The l a s t case m k ( h k - 1 ) - m k _ 1 ( h k - 1 ) = ( V k X ) k f o l l o w s e a s i l y s i n c e " k ^ k - l ^ k - l ^ k - l ) = k ! a k [by c o n s t r u c t i o n o f ]~~ and advance k _^] = ( V k X ) k [by lemma 2 . 6 ] . ( i i i ) : I t f o l l o w s from ( i i ) , the c o n s t r u c t i o n o f f " , and the i n d i v i d u a l subprograms advance^ t h a t i ¥ i = 0 " i + l ^ i 5 = x i + I ( j ) ( V J + 1 x ) j + 1 = x i + 1 [ b y l e m m a 2 ' 3 ] -Since f o r i = 0 , . . . , k - 1 advance^ c o n t a i n s no a c t i o n s o f the form R j , j < i i t Chapter I I I 73 f o l l o w s from the c o n s t r u c t i o n of j~ tha t V^IQ m^ +^(h^)=m k(h^). Consequently m k (h i )=x i + 1 =p(n+ i+1)+1 . 1 2 . 8 2.9 Lemma. Let p(x) be a po lynomia l of degree k>0 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Let r f p ( x ) be as g i ven i n d e f i n i t i o n 2 . 7 , D=In1 ; k ; k - 1 ^. (A) I f W = < ( n p ( x ) ) s , D I ( y ) > . . . <z0,m> e C ( r f p ( x ) , D ) then l e t t i n g s be the number o f occur rences o f the l a b e l Z Q i n W, then ( i ) V ^ l J m(h i )=p(s -1+i )+1; and k ,, a m i * uk -1 |„ 1 1 I ( i i ) m(marks) = u 1 1 . . . 1 u k - l 1 u k > -VJ = 1 u ± 6 {0} , -Y j l j • | u 1 1 . . . u i 1 p (s -1+ i )+1 . (B) I f W i < ( n p ( x ) ) S ' 2 l ( y ) > ••• < z 1 ' m > E 5 ( "p ( x )»2> fcnen l e t t i n g s b e t h e number of occur rences o f the l a b e l Z Q i n W, then ( i ) ¥ ^ : J m(h i )=p(s+i )+1; and ( i i ) m(marks) = u 1 1 . . . 1 u k _ 1 1 u k , ¥ k _ 1 u ^ f O } * , ¥ k l ] | u 1 1 . . . u ± 1 J = p (s -1+ i )+1 . P r o o f . (A) We proceed by i n d u c t i o n on the number o f o c c u r r e n c e s , s , o f the l a b e l Z Q i n W. I f the l a b e l Z Q appears on ly once then i t i s obvious from the d e f i n i t i o n of n p ( x ) tha t ¥ K ~ Q m(h^)=p(i)+1 and m(marks) = u ^ 1 . . . 1 u k _ ^ 1 u k , v£ = 1 \U^...U±M = p ( i ) + 1. Assume the r e s u l t t r u e f o r s-1>1 and c o n s i d e r s . Let W = <([] p ( x ) ) s , D I ( x ) > . . . <zQ,m> . . . <z 1 ,m'> . . . <z Q ,m"> e C(rfp(x) ,D) where there are p r e c i s e l y s - 1 occurrences o f the l a b e l Z Q i n <(rfp(x) )g,D-|-(x)> . . . < Z Q , m > and on ly two occur rences o f the l a b e l Z Q i n < Z Q , m > . . . <z^,m'> . . . < Z Q , m " > . By i n d u c t i v e hypothes i s ¥ K ^ Q m(h^) = p (s -2+ i ) + 1 and m(marks) = u ^ 1 . . . 1 u k _ ^ 1 u k where ¥ k _ 1 U j^efO}*, ¥ k " | 1 ' u 1 . 1 . . •u i1-j = p (s -2+ i ) + 1. From the c o n s t r u c t i o n o f r i p ( x ) and lemma 2 .8 ( i ) and ( i i ) i t f o l l o w s tha t m'(marks) =m(marks) and ¥ K ~ Q m'(h^)=p(s-1+i)+1. Thus i n memory c o n f i g u r a t i o n m' heads 1 , . . . , k - 2 are each scanning a square marked by a pebble w h i l e head k _^ i s n o t . Chapter I I I 74 We i n f e r from the c o n s t r u c t i o n o f n p ( x ) that m"=m' except tha t m"(marks) = v 1 1 . . . 1 v k _ 1 1 v k where V K ~ ] v i 6 {0}* and ¥ k ~ ] | v 1 1 . . . v i 1 1 l = p (s -1+ i ) + 1. (B) I t f o l l o w s from the c o n s t r u c t i o n o f i ~ i p ( x ) t h a t W = < ( n p ( x ) ) s , D T ( x ) > . . . <ZQ,m'> . . . <ZpU> where the computat ion <ZQ,HI'> . . . <z^ ,m> c o n t a i n s on ly one occurrence o f the l a b e l Z Q . Let s be the number o f occur rences o f the l a b e l ZQ i n < ( n p ( x ) ) s J S T ^ ^ ••• <z 0 ,m '> . We have by (A) tha t ( i ) ¥ ^ l j m ' (h i )=p (s -1+ i )+1 ; ( i i ) m'(marks) = u 1 1 . . . 1 u k - 1 1 u k , ¥ k = 1 u ^ t O } * , ¥ k l ] { u 1 1 . . . u i 1 - | = p (s -1+ i )+1 . A p p l i c a t i o n o f lemma 2 .8 y i e l d s ( i ) ¥ k l J m(h i )=p(s+i )+1; ( i i ) m(marks)=m'(marks) which i s the d e s i r e d r e s u l t , i 2 .9 2.10 Theorem. Let p(x) be a po lynomia l o f degree k>0 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s , D=In1 ' k > k _ 1 ^ and n p ( x ) as g i ven i n d e f i n i t i o n 2 . 8 . Then L_/ „ \ = { 0 p ( n ) | n e N } = dom D r r plx; _ " p ( x ) ft P r o o f . We f i r s t show t h a t i f z n e {0} , i z n l = p ( n ) , n 6 N then z R 6 dom Dn thereby p r o v i n g L - z ^ N ^ d o m Dn . The argument proceeds by i n d u c t i o n 'p(x) p ( X ) ~"p(x) on n. I f n = 0 , 1 , . . . , k - 1 then c l e a r l y , by the c o n s t r u c t i o n o f fTp(x) z n e d o m Dn _ " p ( x ) Assume the r e s u l t t rue f o r n - 1 > k - 1 . By i n d u c t i v e hypothes i s W = <(np(x))s,Dj(zn_1)> . . . <z1,m><z2,m> 6CT(np(x),D). By lemma 2.9 (B) we must have i n p a r t i c u l a r m(h k - 1 )=p (n -1 )+1 and i n genera l tha t ¥ k I ^ m(h i )=p(s+i)+1 where s=n-k, the number o f occur rences o f the l a b e l ZQ i n W, and m(marks) = u . , 1 . . . u k _ 1 1 u k where ¥ k = 1 u ^ f O } * , ¥ k ~ ] | u 1 1 . . . u i 1 | = p (s -1+ i ) + 1. We a s s e r t tha t W' = <(ri p( x) ) s , D T ( z n ) > . . . <z 1 tm> . . . <z Q ,m'> Chapter I I I 75 ... <z ,^m"><Z2,m"> 6 C T ( r f p ( x ) , D ) where there i s p r e c i s e l y one occurrence o f ZQ i n <z^  ,m> . . . <ZQ,m'> ... <z-| ,m"><Z2,m">. Observing that there are s+1 occur rences o f the l a b e l z Q i n < ( r f p ( x ) ^ S ' ^ i ^ n ^ < z 1 'm> "' < z o » m ' > f r o m lemma 2 .9 (A) we have t h a t ¥^lj m'(h i )=p(s+i)+1 and m'(marks) = u ^ 1 . . . u k - 1 1 u k , v£=1, u£ e{0}*, vj"] i 1 . . . u ^ 1 J = p(s+i ) + 1. App ly ing lemma 2 .8 to the computat ion <ZQ,m'> ... <z ,^m"> 6 C ( r f p ( x ) , D ) we conclude tha t V^IQ m"(h^)=p(s+1+i)+1 and i n p a r t i c u l a r tha t m"(h k_^) = p(s+k) + 1 = p(n) + 1. Thus D/ T \(m") = <m",-|> s i n c e the l e n g t h o f the input - u k - 1 = ; tape i s p(n) ( that i s , head l c _ 1 must be scanning the r i g h t endmarker) whence W' 6 CT(]*L/ »D) demonstrat ing tha t z „ 6 d o m Dn ~ l 'p(x)'-' ° n - H p ( x ) Converse l y , i f some s t r i n g z 6dom r f p ( x ) then i t f o l l o w s d i r e c t l y from lemma 2 .9 (B) and the c o n s t r u c t i o n of r f p ( x ) tha t jz|=p(n) f o r some n 6 N , p rov ing dom Dn <=L n/ Y\. - " p ( x ) p ( x ) i 2 . 10 Remark. S ince every bounded language accepted by a d e t e r m i n i s t i c bounded r e v e r s a l mul t ihead f i n i t e automaton ( d e t e r m i n i s t i c one-way mul t ihead f i n i t e automaton) i s s e m i l i n e a r [Sudborough 7 4 ] , i t f o l l o w s tha t there e x i s t d e t e r m i n i s t i c marker languages not recogn ized by any d e t e r m i n i s t i c bounded r e v e r s a l mul t ihead f i n i t e automaton ( d e t e r m i n i s t i c one-way mul t ihead f i n i t e automaton) . Chapter I I I 3 Other o n e - l e t t e r languages. 76 One might t h i n k t h a t the po lynomia ls exhaust the o n e - l e t t e r languages ( A • n • \r) a c c e p t a b l e by I n 1 V r t ' ' '. However, the re e x i s t s a c l a s s , c h a r a c t e r i z e d by constant l i n e a r d i f f e r e n c e e q u a t i o n s , which are not generable by any p o l y n o m i a l . The f o l l o w i n g d e f i n i t i o n i s g i ven f o r completeness ; the reader i s r e f e r r e d to [ H e n r i c i 64] f o r a d e t a i l e d p r e s e n t a t i o n . 3 .0 D e f i n i t i o n . A constant l i n e a r d i f f e r e n c e equat ion o f o rder n i s a f u n c t i o n f : S n + 1 - > R , S<=R, : ( y Q ,y 1 , , y n ) r > a n y n + . . . + a Q y 0 + b, { a Q , . . . , a n , b } S R . A sequence X={x i}^>_Q<=S i s c a l l e d a s o l u t i o n o f f i f VkeN f ( x k , x k + i , • • • » x k + n ) = 0 . We s h a l l be d e a l i n g w i t h constant l i n e a r d i f f e r e n c e equat ions o f order n w i t h domain N n +^ and whose form i s f ( v 0 ' y 1 ' y n } = y n + a n - i y n - 1 + ••• + a o v O + b where a Q , . . . , a n _ 1 < 0 and b<0. To f we s h a l l a t t a c h i n i t i a l c o n d i t i o n s Q = <qg,. . . , q n _ 1 > 6 N n, 0<qQ< . . . <qn_-] denot ing the p a i r by <f,Q> and i n s i s t tha t a s o l u t i o n , X, to f , i f one e x i s t s , meet the c o n d i t i o n V"IQ x^=q^. Note t h a t , except f o r t r i v i a l c a s e s , the sequence XQ,X^ , X 2 , . . . i s always p o s i t i v e and, w i t h the p o s s i b l e except ion o f the f i r s t n+1 e lements , s t r i c t l y i n c r e a s i n g . Given the p a i r <f,Q> the order o f f , n , i s i n d i c a t e d by order f . The f i b o n a c c i sequence, f o r example, i s a s o l u t i o n to « y 0 »y 1 r> y 2 - y 1 -Yo, <o, 1 » . The f i r s t r e s u l t shows tha t a s o l u t i o n to <f,Q> may be generated i n a way t h a t i s amenable to computat ion by I n 1 ^ A ' n » k ^ . 3.1 Lemma. Let <f,Q> be g i v e n , X a s o l u t i o n to f ( y 0 . y v - . y n > = y n + a n - i y n - i + ••• + y 0 a o + b -n-1 Then ¥m 6N x m + n + 1 = x m + n + ) ( - a j ) ( x m + j + 1 - x m + j ) . n-1 P r o o f . x m + n + ) ( - a j ) ( x m + j +1 - x m + j ) j=0 Chapter I I I j=0 \ n _ 1 (xm+n + ]_ ajxm+j) j=0 n-1 I (-aj ) xm+j+1 j=0 - b = x m+n+1 3.1 On the b a s i s o f the prev ious lemma I o f f e r 3 . 2 D e f i n i t i o n . Let <f,Q> be g i v e n , n=order f . I n l ( { 0 } ; n + 1 ; 2 ) t o b e t h e p r o g r a m Def ine z2< g- -I i n i t i a l i z e 0 z 2 < — Q — © " i n i t i a l i z e ^ z 0 : v n Iadvancen i U t ^advance n-1 z 1 : I n = » z 2 : where Vn_Q i n i t i a l i z e j i s the program ?R0 1 J +^1 t imes SR. i i .=—2—>©i So: Chapter I I I 78 and i n i t i a l i z e n i s the program JR 1 i n 1 t >( -a 0 )q 0 + . . . +(-a n_-| ) q n _ 1 + ( -b) + 1 t imes where VJIQ advancej i s the program )(-a.= ) t imes and advance n_.| i s the program i >SM -—,— " n - 1 1 i ' n - 1 U - a n _ 1 ) t imes The program Pt<^ Q > f i r s t d i s p a t c h e s h e a d i f o r i = 0 , . . . , n - 1 to p o s i t i o n q^+1 on the t a p e . I f the input i s o f l e n g t h q^ then head^ w i l l be scanning the r i g h t endmarker and the computat ion w i l l te rminate s u c c e s s f u l l y . I f the tape i s o f l e n g t h 1, q ^ K q ^ i f o r some i then the input w i l l be r e j e c t e d s i n c e head^ + ^ w i l l be fo rced " o f f " the end o f the t a p e . Head n moves to p o s i t i o n (-aQ)qQ+ . . . + ( - a n _ 1 )q n _^ + ( -b) + 1 which i s the va lue x f i +1, x n 6 X , the s o l u t i o n o f <f,Q>. When the f l ow o f c o n t r o l reaches node ZQ heads 0 , . . . , n - 1 are i n p o s i t i o n s Chapter I I I 79 xm+1 , x m + n + 1 f o r some m 6 N . Head n then l a y s down a marker which i t w i l l l eave behind as i t i s " f o r c e d " by heads 0 , . . . , n - 1 to the p o s i t i o n x m + n + i + 1 . The " f o r c i n g " proceeds i n n stages beg inn ing w i th headg and c o n t i n u i n g i n sequence w i t h h e a d p h e a d n _ ^ . The j t h s t a g e , 0<j<n-2, begins w i t h h e a d j + i marking i t s square w i th a pebb le . Headj then moves forward to the square occupied by h e a d . For each r i g h t move o f h e a d j , h e a d n moves ( -^ j ) tape squares . When headj a r r i v e s at i t s d e s t i n a t i o n i t p i c k s up the pebble l a i d down by h e a d j + 1 . F i n a l l y head n _^ moves forward to the p o s i t i o n occupied by h e a d n a t the beg inn ing of t h i s c y c l e , head f i moving - a n _ - | squares f o r each r i g h t move o f h e a d n _ i . Head n _^ upon s i g h t i n g the marker depos i ted by h e a d n a t the s t a r t o f the " f o r c i n g " c y c l e h a l t s and r e t r i e v e s the marker . At t h i s po in t heads 0 , . . . , n - 1 are i n p o s i t i o n s x m + i + 1 > •••> xm+n +^ r e s p e c t i v e l y and h e a d n occup ies x ra + n + 1 + ( - a 0 ) ( x m + 1 - x m ) + ••• + ( " a n - 1 > ( x m + n - x m + n - 1 ) w n i c n b y l e m m a 3 - 1 i s  xm+n+1 + 1* ^ n e a d n ^ s n o w s c a n n i n g the r i g h t endmarker ( i m p l y i n g tha t the l e n g t h o f the input i s x m + n + - | ) the program w i l l h a l t , a c c e p t i n g the i n p u t , o therwise another i t e r a t i o n o f the " f o r c i n g " c y c l e w i l l be executed . Observe tha t i f the input i s o f l e n g t h 1 , and x m < l < x m + 1 f o r some m>n then h e a d n w i l l e v e n t u a l l y be pushed " o f f " the end of the t a p e , caus ing the input to be r e j e c t e d . The f o l l o w i n g lemmas are a formal restatement o f the above d e s c r i p t i o n . 3 .3 Lemma. Let <f,Q> be g i v e n , X a s o l u t i o n to f (yg,y.|, . . . , y n ) = y n + an_iY n_i + ... + aoYo + b » w n e r e n=order f . Choose r 6 N . Let D = I n 1 ( { 0 } ; n + 1 ; 2 ) _ Const ruc t m 6DQ such tha t m(input)=y 6{0}*, i y i > x r + n + 1 , Vn_0 m ( h i ) = x r + i + 1 , (Eu,v) m(marks)=u1v, u,v e{0} , j u 1 v | = i y i , i u 1 ^ = x r + n (=m(h n ) ) . Let r be the program 1 IXQ :advanceQ t j>xn_^ :advance n _^ =»xn: Chapter I I I 80 where V^~Q advance^ i s as g i ven i n 3 . 2 , the d e f i n i t i o n of Q>. I f <XQ,II1Q> . . . <x n ,mn> e Crp(r,D) where niQ=m then <*> *i=0 W = x r + i + i + 1 ; i - 1 ( i i ) V N = 1 m i ( h n ) = ( x r + n + ) ( - a j ) ( x r + j + 1 - x r + j ) ) + 1; j=0 ( i i i ) m n ( h n ) = x r + n + 1 + 1 ; ( i v ) m n (marks) 6{0}*. P r o o f , ( i ) and ( i v ) : S ince advance^, (0<j<n-1) c o n t a i n s r i g h t move commands on ly o f the form Rj or R n , i t s u f f i c e s to prove tha t V"IQ m i + 1 ( n i ) = x r + i + i + 1 • Choose 0<i<n-2. I t f o l l o w s from the p rev ious remark that m i ( h i ) = m 0 ( h i ) = x r + i and m i ( h ± + 1 ) = m 0 ( h l + 1 ) = x p + i + 1 where x r + 1 < x r + i + r Consequently the d e s i r e d r e s u l t f o l l o w s d i r e c t l y from the c o n s t r u c t i o n o f advance^. (Observe t h a t m^ +^(marks)=mg(marks).) The case i=n-1 must be t r e a t e d s e p a r a t e l y . S ince m n_^ (marks) = r e m a r k s ) = u1v, where u , v 6 { 0 } * , Jul, ' = x p + n + 1 and Vl ' h r i - l ' = x r+n-1 + 1 < x r+n + 1 i f c f o l l o w s from the c o n s t r u c t i o n o f advance n _^ t h a t m n ( h n _ ^ ) = x p + n + 1 . (Observe tha t m n (marks) e{0}*.) ( i i ) : We proceed by i n d u c t i o n on i , 1<i<n. I f i=1 then s i n c e m.| (hQ)-mQ(hQ) = x r + ^ - x r by ( i ) above i t f o l l o w s from the c o n s t r u c t i o n o f advance Q t h a t m-|(hn) = ( x p + n + 1 ) + ( - a Q ) ( x r + 1 - x r ) . Assume the r e s u l t t r u e f o r i -1>1 and c o n s i d e r i . By i n d u c t i v e hypothes is i - 2 m i - 1 ^ n n ) = ^ x r + n + 1 ^ + T ( _ a j ^ ( x r + j + 1 " x r+ j^* S i n c e m i ( n i _ - | ) - m i _ i ( n i _ i ) = ~j=0 x r + ^ - x r + ^ _ ^ by ( i ) i t f o l l o w s from the c o n s t r u c t i o n o f advance^_^ tha t m i ( V = m i - 1 < h n ) + ( ^ i - ^ ^ m ^ m - l 5 i - 1 = ( x r + n + D + J ( - a j ) ( x r + j + 1 - x r + j ) . j=0 m-1 ( i i i ) : m n ( h n ) = ( x r + n + 1 ) + ^ ( - a j ) ( x r + j + 1 - x r + j ) [by ( i i ) above] ~j=0 = x r + n + 1 [by lemma 3 . 1 ] . Chapter I I I 81 i 3.3 3.4 Lemma. Let <f,Q> be g i v e n , X i t s s o l u t i o n . Let D = I n 1 ( { 0 } ; n + 1 where n=order f , n<f Q> as g i ven i n d e f i n i t i o n 3 - 1 . Choose y 6{0} . I f W = < ^"<f ,Q>^S'2i (y) > ••• < Z 1 » M > E Q ( n < f >Q>»D) then v"= 0 m(h.j_) = x i + g where s i s the number o f occur rences o f i n W. P r o o f . We proceed by i n d u c t i o n on s . I f s=1 the r e s u l t f o l l o w s from the c o n s t r u c t i o n o f ]~]<F Q> and s e c t i o n s ( i ) and ( i i ) o f lemma 3.3. Assume the r e s u l t t r u e f o r s-1>1 and c o n s i d e r s . We then have W = ^ ™ < f Q>^S'2i^y) > ••• < Z 1 » m > ••• <z-| fin'> 6 C(Ti<f Q>»D) where there are s - 1 occur rences o f z^ i n <(n<f Q^S'P - i^y )^ ••• < z i » m > a n d on ly one occurrence o f z.| i n . . . <Zpm'>. By i n d u c t i v e h y p o t h e s i s Yj|-1 m ( n i ^ = x i + s - l • A p p l i c a t i o n o f lemma 3.3 y i e l d s Vn_0 m ' ( h i ) = x i + s . i 3.4 3.5 Theorem. Let <f,Q> be g i v e n , X i t s s o l u t i o n . Let D = I n 1 ( { 0 } ; n + 1 ; 2 ) where n=order f , r!< f as g i ven i n d e f i n i t i o n 3 . 1 . Then L = { 0 ^ x i ^ j i 6 N } = dom Drr - "<f ,Q> P r o o f . C l e a r l y L = {y Q ,y 1 , y 2 , . ..} where y^ ^ 6 {0} , ! y ± i =x ± . We proceed by i n d u c t i o n on the i n d e x , i , t o show t h a t y.. e dom Dn . For i = 0 , 1 , . . . , n 1 -"<f,Q> the r e s u l t f o l l o w s from the c o n s t r u c t i o n of n< f Q>. I f i=n+1 i t f o l l o w s from lemma 3-3 t h a t W = <(n < f }Q>)s'2i( wn+1^ ••• < Z 1 » M > ES('i~I<f )Q>,D) where the l a b e l z 1 appears o n l y once i n W i m p l y i n g by lemma 3-4 t h a t Vn_Q m(h i ) = x i + 1 + 1 and i n p a r t i c u l a r m ( h n ) = x n + 1 + 1 . Consequently W<z2,ra> ec T(f] < f Q>»B)» whence y n . 1 6 dom Drr n + 1 -"<f,Q> Assume the r e s u l t t r u e f o r i-1>n+1 and cons ide r i . C l e a r l y W = < ^ < f Q ^ S ' - I ^ i ^ ••• < z i ,m> 6 ^ (n^f Q>»D) where the number of occur rences o f Chapter I I I 82 z.| i n W i s i - (n+1) ( that i s , m(hn)=x^_^ + 1 ) . I t f o l l o w s from lemma 3-3 t h a t ( i ) <z^,m> . . . <Z|,m'> 6C(rl<f Q>>2) where there i s p r e c i s e l y one occurrence o f i n . . . <z.|,m'> and ( i i ) m ' (h n )=x i +1. Consequently W . . . <z^,m'><Z2,nT> 6C-j idl^f Q>>2) which means tha t y^ 6dom Dn . Thus L<=dom Dn " n <f,Q> ~"<f,Q> To see that dom Dn <=L suppose tha t W = <(T\sr n\)Q>D-r(y)> . . . ""<f,Q> ' y ~ 1 <Z2,m> 6 Cj(ri<f Q>»D) where {w|<xn. I t f o l l o w s from the c o n s t r u c t i o n o f g> tha t ( E i ) , 0<i<n, |y{=x i demonstrat ing y 6 L . I f ! y j>x n then by lemma 3.4 m(h n ) = x n + g + 1 where s>1 i s the number o f occurrences o f z^ i n W. I t f o l l o w s tha t l y i = x n + s , hence y 6 L . 1 3.5 3.6 Example. The f i b o n a c c i numbers are the s o l u t i o n to the p a i r <f,Q> where f ( y n > y i » y 2 ) = y2~yi~yo a n d Q = < 0 > 1 > . Therefore the se t {w{w6{0} , ( ( E f , a f i b o n a c c i number), |w]=f)} i s I n 1 » 3 ' 2 ^ - a c c e p t a b l e . 3.7 Example. Let k 6 N + be g i v e n . The sequence X = ( X i ^ - Q ' x i = k 1 i s the s o l u t i o n to the p a i r <f,Q> where f(yg,y-|) = y^ -kyg and Q=<1>. Thus the set { O ^ ^ j n e N } i s In1 ; 2 ; 2 ^ - a c c e p t a b l e . (A c a r e f u l read ing of d e f i n i t i o n 3.2 w i l l show t h a t i t i s a c t u a l l y I n 1 v 1 } ' ' ' - a c c e p t a b l e : s i n c e n=1, no subprograms advance^ f o r j<n-1 are c a l l e d f o r . ) The next two r e s u l t s show t h a t , f o r k>1, the language of example 3-7 i s not generab le by any p o l y n o m i a l . 3.8 Lemma. Let k 6 N + , k>1 be g i v e n . Let X = { k " } ^ . Then ( V i X ) J = ( k - D 1 ^ - 1 > 0 . P r o o f . We proceed by i n d u c t i o n on i . For i=0, we have ( V ° X ) j = k J , as r e q u i r e d . Assume the r e s u l t t r u e f o r i -1>0 then Chapter I I I 83 ( V i X ) j = ( V i - 1 X ) j i - 1 j - 1 = ( k - D 1 - 1 ^ - ^ - 1 ) - ( k - D 1 - 1 ^ - 1 - ^ - 1 ) [by i n d u c t i v e hypothes i s ] = ( k - l ) 1 ^ - 1 . i 3.8 3-9 Theorem. Let k 6 N + , k>1 be g i v e n . Def ine f :N->N :n r>k n . Then there does not e x i s t a po lynomia l p(x) such t h a t pjN = f . P r o o f . A p p l i c a t i o n o f theorem 2 .4 to lemma 3-8 b r i n g s us to the d e s i r e d c o n c l u s i o n . B i b l i o g r a p h y 84 [Baker 76] Baker , John L . , Lec tu re n o t e s , Department o f Computer S c i e n c e , U n i v e r s i t y o f B r i t i s h Columbia , Vancouver B. C , Canada, (1976). [Baker 77a] Baker , John L . , Lec ture n o t e s , Department o f Computer S c i e n c e , U n i v e r s i t y o f B r i t i s h Co lumbia , Vancouver B. C , Canada, (1977) . [Baker 77b] Baker , John L . , S i m u l a t i o n i n a Theory o f Programmable Machines, T e c h n i c a l Report 7 7 - 7 , Department of Computer S c i e n c e , U n i v e r s i t y o f B r i t i s h Columbia , Vancouver B. C , Canada, ( J u l y 1 9 7 7 ; . [ G i u l i a n o 70] G u i l i a n o , J . A . , W r i t i n g Stack Automata, IEEE Conference Record o f 1970 E leventh Annual Symposium on Swi tch ing and Automata Theory, (1970) , 181-193. [ H a r r i s o n and I b a r r a 68] H a r r i s o n , M i c h a e l A. and Oscar H. I b a r r a . M u l t i - T a p e and M u l t i - H e a d Pushdown Automata, In fo rmat ion and C o n t r o l 13, (1968), 433 -470 . [ H e n r i c i 64] H e n r i c i , P e t e r , Elements o f Numerical A n a l y s i s , John Wi ley and Sons, I n c . , (1964) . [ R i t c h i e and S p r i n g s t e e l 72] R i t c h i e , R. W. and F. N. S p r i n g s t e e l , Language Recogn i t i on by Marking Automata, In fo rmat ion and C o n t r o l 2 0 , (1972) , 313 -330 . [Rosenberg 64] Rosenberg, Arno ld L . , On n-Tape F i n i t e S t a t e A c c e p t o r s , IEEE Conference Record on Sw i tch ing C i r c u i t Theory and L o g i c a l Des ign , (1964), 7 6 - 8 1 . [Rosenberg 66] Rosenberg, Arno ld L . , On M u l t i - H e a d F i n i t e Automata, IBM J o u r n a l 10 No. 5 , (September 1966) , 388-394. [Rosenberg 67a] Rosenberg, Arno ld L . , A Machine R e a l i z a t i o n o f the L i n e a r Contex t -F ree Languages, In fo rmat ion and C o n t r o l 10 No. 2 , (February 1967), 175-188. [Rosenberg 67b] Rosenberg, Arno ld L . , M u l t i t a p e F i n i t e Automata w i t h Rewind I n s t r u c t i o n s , J o u r n a l o f Computer and System Sc iences 1 No. 3 , (October 1967), 2 9 9 - 3 1 5 . [ S p r i n g s t e e l 67] S p r i n g s t e e l , F. N . , C o n t e x t - F r e e Languages and Marking Automata, Ph.D t h e s i s , U n i v e r s i t y o f Washington, (1967) . [Sudborough 71] Sudborough, I. H . , Computation by M u l t i - H e a d W r i t i n g F i n i t e Automata, Ph.D t h e s i s , Computer Sc ience Department, Pennsy lvan ia S t a t e U n i v e r s i t y , U n i v e r s i t y Park , P A . , (1971) . [Sudborough 74] Sudborough, I. H . , Bounded-Reversal Mu l t ihead Automata Languages, In fo rmat ion and C o n t r o l , (1974) , 317-328. [Sudborough 76] Sudborough, I. H . , One-Way Mu l t ihead W r i t i n g F i n i t e Automata, In fo rmat ion and C o n t r o l 30 , (1976) , 1 -20 . 

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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051784/manifest

Comment

Related Items