REVERSAL-BOUNDED COMPUTATIONS Tat-hung Chan Ph.D. Thesis December 1980 TR 80-448 Department of Computer Science Cornell University Ithaca, New York 1?VwAL-flODNflED CO?(?UTATlO!1S Tat-buns Chan. Ph.D. Cornell University. 1980 Ia computations by abstract computing devices such as the Turlig ssachine. head reversals are required for searchins the input or retrieving intemediate results. hence the number of head reversals La a neasure of the conpiexity of a computation. This thesis is a study of reversal-bounded computations on three models of abstract computins devices. The first model is the i-tape Turing machine vith finite bounds on head reversals. It is known that such nachines recognire exactly the regular sets so that for recocuition purposes0 reversals can be eliminated entirely. Por traneduction purposes. that is. if an output is expected on the tape. a single reversal suffices. Ilence these sachines are most appropriately called finite automate. Clearly they are amon5 the veskeat possible computing devices. and nany decision problems shout them are solvable. We use this fact and a very simple input-output encoding achene to obtain areatly simplified proofs of the decidability of sons veak nathenstical theories. including the veak monadic second- order theory of one successor and preshurger arithmetic. Similar techniques yield linear ai2e bqunds as veil as linear time complexity bounds (on the multitape Turing machine model) for functions definable in Presburger arithmetic. As corcilaries. ve find applications in linear diophantine systems and linear integer progranloing. The second model La the multiconter macbLue vLtb general bounds --H eo?ter reversals. fly relating counter reversal to tLaa and space. me s1- that recuraivenese 0 reversal bounds Laplies recuraivenesa 0 the sets accepted. For bounds that are at least linear. counter reversal La polynomially equivalent to Turing machine tile in both the deteriiniatic and the nondeterminiatic cases. This result leads to a general deterministic reversal hierarchy and a natural formulation 0 the PaILS question on the multicounter machine ssodel. It alac auggeata that on every reasonable universal conputing model. there is a unaturals complexity measure that is polynosially equivalent to Turing machine 1?2 time. For reversal bounds that grow more alovly than n . vs 51- that the nondeterninistic 2-way reversal complexity class La not closed under conpienentation and etrict?y includes the corresponding deterniniatic class. In contrast. the analogous questions are open or 2qay 2-tape Turing machines with logarithaic apace bounds. Finally. we consider inits hounds on counter reversals. For both the 1-vay and the 2-way models. we obtain very sharp upper bounds on the Turing machine tile and space complexity of the languages accepted. ?n the I--Hmay case. me present a unified account 0 the known results. interspersed mith our contributions. which include (1) equivalence to I-way simple nultihead finite automats. (2) an easy technique for proving nonrecognixability. (3) an abstract characterization of the power of finte reversal-bounded counters. and (A) an application to the theory of progre schsnes. Lastly we consider finite reversal--Hbounded multitape finite autonata. Ve show that over a single-letter alphabet. the languages accepted are exactly the unary encodings of Preahurger relations. This result holds whether the model is deteniinlstic or nondeterministic. and even if it is ausse?ted vitb. for ezaipie, finite reversal-bouvded counters end an sureatricted puabdove store. or if the reversals are rsstricted to revinds. that to. in.tructione that ainulteneously poaitlnn all beads at the beginnings 0f their reepective tapes. For both detersintetic and nondeterninietic revind autonata. v. establish exhaustive bierarcbiee based on the finite nusber of revinda. When reatricted to a single- letter alphabet. the detersiniatic hierarchy standa but the sondete:e1n?s?Lc one collapses. lETIULL-D?SlID C?irUTTWUI A meet. ?re?eted to the raculty of the Creduete School of Cornell university La Parttal Pulfillient for the fleSree of Doctor of Philosophy by Tat?hung Cbsn sq?et 1?ao flingraphical Sb.tch Tat-hnng Chan `as born in long Kong on August 21. 1?5I. He graduated fres St. Louis ScbonI. Hong Kong. in 1970 and earned the A. 5. degree -o+ ii Isupe and with highest distinction in nathenatics fros DsrtnouLh College. Hanover. Hew Hanpahire0 in 1974. Mter working as a progrsloer with Asiadata Limited. Hong Kong. be entered Cornell Cuiversity in Septenber, 1976 as a graduate student in the Departnent of Colputer Science. He was awarded the M. 5. degree in January. 1980. Xr. Chan is a nenher of Phi Beta Kappa. the Association for Computing Machinery. snd the Society for Industrial and Applied Hathenatics. ii To ? par?to I?L sckaowledgessents The autbor is deeply grateful to his thesis a?wisor. Professor gobert Zo+ Censtable. ?hose patient guidance led his through bLa entire' graduate career. fros ad.ission to the coupletion of this thesis. lie is indebted to Profeesor Jun. lartuanis for stisulating his interest in the theory o+f cooputation and for constant encouragflent. He also vishes to thank Professor Charles Van Loan and Professor M?chael J. Todd for serving on bia special cossittee. Professor Oscar a. Ibarra of the University of Minnesota for uny useful discussions. Professor Sheila A. Creibach of UCLA for directing his attention to Professor Ibarra's work. and his fellow student. Mr. Gary M. Lewin. for invaluable assistance in the preparation of this thesis on the Unix systess. The author gratefully acknowledges the following support for his graduate study: Cornell graduate fellowships (1976-1979). rord roundation engineering fellowship (1976--H1977). Cornell su-ir graduate fellowship (1971). 7aM graduate fellowship (lfll-1980). and lISP through grants lICS 78?OO953 and ??S 7C?OOAlS (sco+o+?rs 1978-1980). iv .4 Table of Cetents Chapter 1 IntroductionI 0. Ceneral discussionI I. Definitions and notationa Chapter 2 Finite Aut?ton Coaputations12 0. Introduction12 I. Theories decidable via finite autoasts . 13 2. Arithietic relations and functions coiputable by finite autonata17 Chapter 3 aeversal?Bounded Counter Machines32 0. Introduction 32 I. Two-way coun?er eachines wiLh general reveraal?bounda36 2. One-way counter aachines with general reversal bounds67 3. Two-way counter nschines with finite reversal bounds77 4. One-way counter nachines with finite reversal bounds86 5. An application to progras acheses103 Chapter 4 Finite keverasi-flounded Multitape Finite autosataI2? 0. Introductionl2? I. Definitions and notation129 2. Characterization of the recognizable unary languages130 3. leduction of reversals236 4. aewind autosata135 Chapter 5 Conclusions151 lefarences153 w LLa? or Illuatratloic F1au?o 3.1.1 risure 3.1.14, ILguro 3.1.3 vi Cbspter I Introductios 0. Sanaul ??a?????o' Tbe ala of this thesis is to study the role of head reversals `a abstract cosputing devices such as finite aut?ta aad Isring asebisee. Typically. an abitreeL coaputing device consists of a fisite control. one or sore input tapes. and any nuaber of auxiliary tapes. The auxiliary tapes are used as 2-way read-write work tapes. In sons devices. ths input tapes ese also be used as work tapes. whereas in others. they are "read-only". The function of these devices is usually set. or ?l5ngu5ge?? recognition. i.e; they are only asked to conpute "yes1 or "no" answers. Within this general f?asework a host of computing devices have been defined: the finite control nay be detereimistic or nondeterninistic. the input tapes nay he I-way or 2-way. the auxiliary tepes may be restricted to stacks. queues or counters. etc. wany such devices have been studied and extensive qualitative conparisons of the conputatlonal powers of the different physical "resources" have been made. Clearly. the aost general nodel -- the aultitape Turing nachime which has a single I-way input tape and one or sore 2?ay read-write work tapes --H- is the lost powerful In that it can sisulats all other devices. It turns out that the Turing machine can also sinulate all other knows fornaliass of mechanical computation. Church's Thesis is a statenent of the conviction tbat this will remain true no setter how sany sore Hreasonahle? forealisus we may define in`the future. A refinement of the qualitative classification of nachines with diferenL physical resources is the quantitative classification of nechines with different eounts off the sane resources. The nost popular such classificationS are the Line and space hierarchies for the?IuLtitapC Terms nechine sodel. It has becone standard practice to neasure the Jifficulty. or couplexity. of abstract problens in terns off tbe tine and?or space requirelents for their solution on this nodel. ?ther nessure of computationsl couplexity is the nunber of bead reverasis on the input tapes endlor auxiliary tapea a conputing device requiree to solve a proble. Intuitively. bead reversals are required for searching and conparing tbe input endlor the internediste results iritten down on tbe work tapes. and one night expect that the nunber off reversals required reflects the degree off intricacy in the conputation. leversal bas been studied on all the familiar conputing devices. So far the ephasis has been on finite (i.e. constant) reversal bounds. There are several reasons for this. Firetly. whereas finte bounds on Line are pathological and finite bounds on apace 1ield trivial coiputetions (i.e. regular sets). finite bounds on reversal often yield interesting hierarchisa of nontrivial conputations. secondly. even though finite reversal-hounded devices can reco&nire nonregular este. in nany cases they are quite tractable. ror example. questions about the such as ciptiness and finiteneas often turn out to be decidabte. LastLy. the classes of languages recognized have nany nice structural properties. such ae senilinear Parith naps and natural algebraic or greustical charecterixations g5 now aunnarize the nein results concerning reversal that occur in the literature. gahia and Scott (lISI) and shepherdeon cls5?3 showe4 that any I-reps 2-isy deterniniatie finite autoeston can be effe?tively 3 converted to a. equivalent I-way deterninistic finite setonaton: in fect tbe s?e is true 0 I-tape 2-way nondate?inistic finite autolate0 so that for I-tape finite autoesta reversals are coepletely redundant. It La easy to see that this no lonter holds when the finite autonata heve sore than one loput tape. in either the deterniniatic or nondeteroinistic case. koseaberg El1671 studied deterniniatic nultitape finite autoosta with rewind instructiona which ellultaneously pocition all heads et the beginnings of their respective tapes. ne shoved that for each such device. finite revinds alvays suffice. and that for each a. the class of a-tape detersinistic revind autolaton languages is the Booleso closure of the class of a-tape I-way deterniniatic finite autonaton languages. lbarrs LlflS? considered the decision probles of various finite reversal-bounded nultitape autonsta. Ciaaburg sad Spanier El966b? studied puabdowa autonata with finite reversal bounds on the pushdovn stores. They shoved that such puabdowa autoesta accept exactly the context-free languages generated by each of two special classes of context-free gra-ars --H--H the ultralinear graimars and the nonterninal-bounded graiMirs. In particular. I-reversal pushdofl autonata accept exactly the linear context-free languages. Whereas tbs equIvalence proble is unsolvable for I-reversal puabdova autonata and open for unrestricted detersinistic puebdown autosata. Valiant EI973? gave a decision procedure for finite reversal-bounded deterninistic puabdova autonata. Baker and look (l?74J considered I-way ?chiaes with sore than one pushdova store. They showed tast wLtn nonoeterninisi. even sachines with only two 1-reversal puabdown stores have the full power of Turieg sachines. On the other band5 detersinistic sachines with 4 recarsive rewersaL boueds os their pusbd? stores always accept recursive sets. A special case 0 the ?ltipushdown nachine is the o+ulticounter sachine i? vhich each pushdowe store is restricted to a smile-letter alphabet. Deteminiatic I-way 2-counter sachines have bean shown equivalent to Turin8 sachines (Mineky El%l)) whereas nondetereinistic 2-way I-counter sachines always accept in n3 tile and hence can recognize only a very snail class of recursive sets (Creibach (l?75bJ). With finite reversal bounds jiposed on the counters. I-way nondetereinistic sachines always accept in linear tile (Baker and Book El97?)). and the cias; of languages accepted can be characterized in terne of sinpie languases and siaple language operations (Baker and Book (1974). Latteux (1977)). Ibarra (19781 shoved that these sane nachines accept only senilinear languages and hence have lany solvable decision probleas. and that alloving finite reversals on the input tape does not enhance the elass of languases accepted. Recently. ?urari and Ibarra (1980) studied the conpiexity of the solvable decision problems of Ibarra (1978). They showed that for the class of nondeterninis?ic 1-vay eachines with a r- reversal counters. vhere a and r are fixed. nany decision problems are solvable in deterainiatic polynonial tine: when a and r are allowed to vary0 the coaplexity julpa up to NP-hardness. PSPACE-hardness. etc. In a different vein. Curaci and Ibarra (1979) showed that when restricted to unary input. detenninistic 2-way nachines with finite reversal-bounded counters can be effectively converted to equivalent finite autoasta. Finally we cone to the general Turing nachine nodel. First consider I--Htape nachines in which the single tape serves as both input tape and ?ork tape. lanete Cl?65? showed by a erosNing sequence argusseet tbat uitb finite reversal bounds such machines accept erect11 the regular sets. siacher El%8? generalised the argument to show tbst for this model. linear speed-up in reversal by any constant factor is always possible. More work was done on the I-tape Turing machine model which has a read-only input tape and a 2-way read-write auzilisry work tape. Bartmanla ?l96Sa? established a rich hierarchy based on reversal bounds on the deterministic I-way model. and shoved that for slovly growing bounds no speed-up in reversal is possible. lor both the deterninistic end the nondeterministic i-way models. reversal bounds are recursively relsted to time and work tap? space bounds (Hartnanis El96Ssi. Baker and Book E197AJ). so that recursiveness of the reversal bounds implies recursiveness of the sets accepted. In two papers. Creibach El97Oa. 1978b) made a thorou:h st.sdy of both the I-way and the I-way nondeterministic models with finite and more general bounds on work tape head reversals0 crosses or visits. The machine model was generalised to allow the initial contents of the work tape to be preset from a base isoguage (note the nondeterminise here). so that each class of machines can be considered as generating a new family of languages from each family of base languages. Many interesting results. including comparisons of reversals. crosses and visits. language characterilations. hierarchies. and complexity bounds. were obtained. We now sketch an outline of the present thesis. The technical results are contained in three chapters. each dealing with a different computing device. Chapter 2 studies finite reversal bounds on the I--Htape Turing machine model for both reconition and transduction purposes. 4 Seceese of the results 0 Bonnie ?l?OS3 and liacher El%8? these devices are soot appropriately called finite autolata. even when they are used as tranaducers. Our sain concern here is with applications of these aacbines to satheistics. Thus we sinplify the decidobility proofs of several weak nathenatical theories due to presburaer Elno). Buchi Ll96O? sod ZIgot (igol). In the case of binary arithnetic. i.e. linear integer arithoetic extended with the "pover of two" predicate and the `inclusive er? function on biusry representations of nuibora. we show that definability for relations and functions is equivalent to conputability by finite autonata. This equivalence is used to obtain linear hounds on the o+ultitape Turing ,schine tile cooploxity of functions definable in Presburger arithietic as well as results in linear diophantino systeis and integer linear progr?ing. Pinally we hound the cooplaxity of finite autonaton cosputationa by showing that the relations and functions definable in binary arithoetic are proper subclasses of the Crsosorcxyk classes S0 and ?l respectiiely. Chapter 3 is a study of reversal as a conputational conpioxity asasore on aulticounter sachines. us already saw that nondoterainistic I-way sachines with two l?reversal pushdown stores has the full power of enroatricted Turing nachines (Baker and Book (1974)). Thus in general recureivenoss of reversal bounds on nondeterninistic sachines with sore than one auxiliary work tape does not inply recursiveness of the sets accepted. By relating reversal to tisa and space. we show that if the aneiliary work tapes are counters. then recursiwo reversal bounds are sufficient to guarantee rocursivonoss of the sets accepted. even for nondotersinistic aachinos with ;-way input. Furthernoro. we show that reversal on 2-vay counter i.cbines is polyncitally equiralent to tias on Turing sachineel specifically. we show that --H a(n) reversal-bounded nondeterainistic nulticounter nachine can be sinulated by an (n+I(n))k tine-bounded I-tape nondetem?nLarLc Turin: nachine for sole posiLive integer k. whereas it is veil known that a t(n) tise-bounded nondeterainietic Turing nachine can be aiuulated by a T(n) reversal- bounded nondeterninietic 3-counter?nachins (for exaiple. see liopcroft and Clina. Cl96?)). SiMilar equivalences bold for the deterainistic nodels. wherene unifors. provably optisal or near-optisal ejiulation bounde are obtained if the nulticounter sachinee are I-way. Corollaries of these polynosial equivelencee include a deterniniatic reversal coaplezity hierarchy end a natural fornulation of the ?:??p queetion on the sulticounter sachine nodel. the results obtained for general revereal bounds are specialised to aublinear reversal bounds. Thue for bounds up to n1,2. vs show that the nondeterainiatic 2-way reversal cospiezity clean is not closed under cospLenentation and strictly includes the corresponding deterainiatic class. Finally vs restrict the reversal bounds to be finite. For both the 2-way and the 1-way nodels. vs give very sharp upper bounds on the turing aachine tise and apace coaplexity of the languages accepted. In the I-way case. we present a unified account of the known results. interspersed with our on contributions. which include (I) equivalence to i-way siMple nultihead finite autonata. (2) an easy technique for proving nonrecognisability. (3) an abstract characterization of the power of finite reversal-bounded counter?. and a. application to the theory of progran acheass. is Chapter 4 we consider finite reversals on o+ultitape finite a aut-ata. V? sbov tbat ever a siagle-letter alphabet. the lausuases accepted by finite reversal-bounded aultitape finite autolata are exactly the unary aneodings of Presburger relations. This is true whether the undel is deterainistic or nondeterninistic5 and even if the `odel is augmented vith finite reversal-bounded counters and either an unrestricted puabdown store or a finite reversal-bounded auxiliary work tape. or if the reversals are restricted to revinds. Finally we show that for revind autonata5 hierarchies based on the number of rewinds exist in both the deterninistic and nondeterminiatic cases. When restricted to a single-letter alphabet. the deterainistic hierarchy stands but the nondeterainistic one collapses. Chapter 5 is devoted to concluding remarks. ?. flpf??i?i'nn. Ant no???inn Va shall assu.e faniliarity with the basic notions5 definitious and results of the theories of automate0 fornal languages. and coaputational coaplexity. such as can be found in flopcroft and Ullian El%9J. liarrison El97a?. or Hopcroft and Ulluan (19791. Both single-tape and multitapa Turing machine models have already been described in the previous section. In this thesis. a Turing machine refers to the single-tape sodel except when we state otherwise or when the discussion pertains to nachines which use less than linear space. We use the standard abbreviations Th. IBA. PDA and FA for Turibg machine. linear bounded automaton5 pushdown automaton and finite automaton. respectively. We prefix such an abbreviation with D when we wish to emphasize that we are restricting the discussion to the deterministic model0 and we use the prefix N when we want to emphasize that nondeterminism is sslowcd. abbrevistions for less co-on i.cbLne models wLll be introduced wnen needed. CFL end CsL stand for context-free language and context- seositive language. respectively. The neanings of nCFL. DCSL and NCSL ebould be clear. P (respectively NP) denotes the clasa of languages recognizable by deterninietic (respectively nondeterniniatic) Th'e in polynonial tile. Notice that when we say a nachine M is f(n) bowLded in soes resource. we nean that there is a constant c auch that for every input v that N accepts. there is an accepting computation of N on v which uses no nore than c'(f(IwI) unite of that resource. where lvi is the length of v. This holds whether M is deterninistic or nondeterninistic. Most of the language-theoretic concepts tbat we shall use should be faiiliar to readers with a basic knowledge of the elementary theory of automate and formal languages. Possible exceptions are the P.ri?h na and Cone related notions. Let ? a (a1.....a0) be a finite a)phabet whose elements are ordered as shown. Let II be the set of natural nunbers. Then the napping o+i: ?t?n gives the conpoaition of each string. i.e. for all v a where ti is the number of occurrences of Ci in v. `then there is no danger of confusion. we shall simply write o+ instead of For any language L over ?. the image o+(L) of L under o+ is called the Parikh nap of L. Clearly o+(L) can he considered as a "projection" that wipes out information about the order of occurrences of the symbols in the strings. The structural complexity of o+(L) then yields an indication of the structural complexity of L. liowever. to be able to exploit this idea. we need some criterion of structural simplicity for subsets?o( NO. One 10 eatsrsl. straightforvard criterios is that the aubsets should be "regular latticee". or finite unions of such regular lattices. These lutuitive notions are captured in tbe following definitions. A subset g,of In is said to be lLML it there exist n-iectors v00 v1, o+?00 vk such that 5 fl ( V0 + ??tiVi 1 ti ? 0 ). A ieite union of linear sets is said to be s?1?nppr the neturalness of s?ilinear sets is underscored by the result. due to Ginsburg and Spanier (1964. 1966sJ. that they are exactly the sets definable in ?resburger ariti-tic. i.a. the firat?order theory of the utural nunbers vith sddi?ion. `urthernore, there are algorithns for converting fros a a?ilinear representat?e to an equivslent Presburger fornuls and isca ?. so that the two notions can be used interchangeably. With regard to the structural coeplexity of languages. it is an easy exercise to shov. by induction on the structure of regular expressions. that all regular sets have aeailinear Parikh laps. The such nore difficult result that the s?e ia true of all CFL?s i? due to Parith (1961. l966?. after wh? the cap is naned. Vs say a language is se.ilinear if its Perith sap is a sesilinear set. A notion related to the conposition. of strings is the operation of n.rmii?,t;nn pe which can be defined by p(L) s j v 5 :+ I 3w'eL. o+(w) I o+(w?) J. A language L is fn??r??l?a if it is closed under nersutation. i.e. if p(L) We conclude with aces rearks on notation. We shall use ? for isproper set inclusion. and c for proper inclusion. ror a nosnegative real susbsr x. rx? and L? at?d for the aiLLaL and Ljnisc respectively off I. i.e. II rxl a ?io+ a a I ? x? a LxJ a 55x a a I s as x logarithas viii be taken vitb base 2. unless a different base La explicitly stated. ? and `I are used for indexed conjunction and diajunction respectivaly just as 2 is used for indexed au-iation. in this thesis. sections are nuaberad concecutively starting froa 0 vithin each chapterS theoreas (respectively leassas. reaarka. siapias. figures) are nuahered consecuLively starting froa I vithin each saction; coroilaries are nuabered consecutively starting fron L for each theora. vs' adopt the Dewey notation for identifying sections. theoreas. etc.. vith chapter nuabera onitted for references fron a different section in the s?e chapter. and vith both chapter and section nuabers -?itted for references froa vithin the asee section. Chapter 2 Ii.ito Autointom C?putatioms 0 ?ntrnSuerlqn Consider I-tape Turing machines which have finite (L.a. comatant) bounds ilposed o+1 the nunbers of tiles their readerite heads CM reverse direction in any coiputation. By a "crossing sequence" argulent. Hennie EI965? abowed that such machine. hava the aame accepting power as finite automate. so that for aet recognition purposes. head reverasla can be alininated completely. Using Hennie's technique. Fiacher El968) proved a general linear "speed-up" theorem for the number of head reveraals of I- tape Turing machines. From FiacherIs argument. it is easy to see that for transduction purposes. i.e. if the finite reversal-bounded machines are intended to leave an output on the tape. one reversal suffices. Vs shall call such machines finite autometa whether they are used as acceptora or traneducers. For emphasis. we shall use the prefixen o+l- vayft and "I--Hreversal" wherever appropriate. Clearly finite automate are aseong the weakest possible acceptors and traneducers. In this chapter. we are concerned with applications of finite automata to mathematics. By a combination of second-order logic and the theory of finite automata. Buchi?(l96O1 and Elgot (l96l? devised decision procedures for various veak mathematical theories. including weak second-order arithmetic and Presburger arithmetic. Their methods involve encoding relations in such 5 way that they can be recognized by finite automate. litchie (i963a? made use of arithmetic functions computable by I-way finite autonata using the same encoding.. here we shall give aimplified proofs for the results of Buchi and Elgot. using only automate 12 13 Cb?ry and avoiding sanipelatloas ia ?eoad-order logic antir.ly. Va shall ala. derive ebaracterisationa for tbe aritbistic relations and functiou coiputable by finite autovata uuder the o+? encodinga. A corollary of the characterization for the c..putable functions ia that functions defiuble in Freaburger aritheetic can be coiputed in linaar Line by Iulti?ape Turine ?schines and have function values that ara linearly bounded in the size of their arausenta. The sane argusent can be used to bound the size of "snall' solutions to linear diophantina systess (later (undated nanuacripti) and to obtain algoritbis for solving some reatricLed integer linear pro:rsna. Finally. we also bound tha conpiexity of finite autoneton conputations by showing tbst the conputable relations forn a proper subclaas of tbe relations of the Crzeorczyt class whereas the conputabla functions forn a proper subclass of the Crzegorczyk class S1 (Crzegorczyk Llg531). 1. Tbopr?ep ?.?i?sb1. ILL f(n.?te automate We basin with infornal descriptions of several weak sathesatical theories. The underlying language of each theory consists of individual variables zi0 z20 set variables S1. S20 ... for second-order theories only equality 5 for individuals or sets propositional connectivee A0 Y? i? ? quantifjers V. 3 special. interpreLed constant. funetioa and predieate.synbols. For each theory. it suffices to specify the doisina of the individual and set variables0 and the special synbola together with their interpretations. 14 (1) Ica .r?r?pr? (??) (i) The d?i. o+ the individual variables La the set o+ natural nuibera 1. Cii) The doiain of the set variables La the set o+ all isite subsats of U. o La the natural nu.ber zero. ` is the successor funetLon ox I. (iii) (iv) (v) a is the inbershtp relation. (2) Pr.bcr.?r iri??p?if (? The dosain of the individual variabres is I. (ii) There are nq set variables. (iii) 0 and I are the natural nunbera zero and 005 reapeetivel7. (iv) o+ is the addition on I. (v) c is the order relation on I. (3) liflw .rit?e?;c (`L) This is just PA extended to include the follovings (v) Pv? is the "pover of 2" predicate. (vi) 0 is the "inclusive or" of t',o natural a-hers `1 binary representation. (4).ZhLaAt OL wi-Lin?? ftLi (QE) This La the sane as W2A except that the set variables ranse over the auj-?. i.e. finite or cofinite. subacts of 1. fluchi El960) and Elgot Ll96l? shoved that the four theories above are all decidable. Their approach can be suniarixed as follova. By aseipulations in second-order logic (fluchi (l?6o. Lesis l?) every forsula La `2 cas be convertee into Co equi?aleat one in iw?-? aunLi e `5 a-al fl:i (2IflI)s is which the set variable quastiftore precede the individul variable quantifiera. Wezt it was eben that relations over finite sets defiMble in V2A by a foriula with no ?t variable quantifiere can be encoded is such a `ray that they can be recognised by PA's. Specifically. ? ?l5 o+??? o+k are k finite eats such that I I sax SlU??SUSk ta defined (t.e. at least one S? is no-ipty). then the k-t?ple ?5l'???55k? is encoded as the kx(itl) array (a?j)isis...s?ij:?.....u where a?j 5 l U J 0 St 5 0 other'rise. That is5 the ith row is the "truncated characteristic function" of The k-tuple of cupty flta is encoded as the epty latri'. For input to an PA. each such satrix can be considered as a string over the finite alphabet consisting of the 2k possible coluina. The recognisability by PA was then extended to any relation defiuble in V2A by a foreula in 2?uFs this was achieved by a routine induction on the structure 0 the forsuls. Thus the truth value in W2A of every 2?'P sentence5 hence of every sentence whatsoever. is effectively reduced to the trivial ciptiness problen of scue PA over an epty alphabet. The decision procedure for QI is ainilar5 whereas those for PA and SA can be obtained by cibadding in W2A. The above decision procedures are not the wost siuple and intuitive possible. Consider the procedure for W2A. Piratly5 osa has to go through a conversion to iruP in second?rder logic. Secondly5 Suchi (lI'O? used a rather unfastliar propositional-calculus sodel of the PA5 0 I' uhereas Ilget E1%1? used regialar expressions. meither o+f these forialisma Is as intuitive as the operational model of the VA as a finite--Hstate tranaitiom systess. fly extending the encodins for `pure' o+et--Hrelations to ?ixed" relations1 and by adopting the operational model of the FA. we obtain trivial proofs of the same results. avoiding manipulations in second-order logic. Let a mixed (i+n)-tuple (xi1?1?1xo+1Si?1111Sn) be encoded as an -(i+n)-row array as before. with each xi treated as the singleton set Then the encodinga of mixed relations definable by formulae in W2A are recognizable by FA'a1 Such FA1a always check that each xi row contains exactly'one 1. Atomic formulae are checked as follows: (i) Xi e S?: the FA checks that the Sj row has a I in the same column that the Xi row has a I. (ii) x? XjtS the VA checks that the xi rov has a I one column after the ij row has a 1. (iii) i? 5 xj or S? o+ Sj2 the VA cbecks that the two rova involved are identical. Inductively. we see that A and I correspond to the intersection and complement of encodinga. For ?xi or ?S.. vs construct a new FA that gueqees the xi or Sj row and feeds it together with the real input to the old FA1 This cospletes the argument as A1 I and ? forn a complete set of logical connectives1 Notice that we have used implicitly the fact that an NFA can be converted effectively into an equivalent DFA. Similar direct encodings c?n be constructed for the other three tbeories1 For QF. we simply truncate the array of characteristic functions at the point beyond which all' the finite and cofinite sets as `7 v.11 as the individual variables have `settled don pe?eemtly'. Per PA and `As the rova are the biury reprasentations of utsral a-bern. aligned at the least sisnuicant bit positions. Aa PA can check atolic formulae of the forms x o+ y.a. x C y. Pw2(x) and I I yCa: in the case of addition. the PA siaply ejiulates the manual addition algorit)- that humans use and compares the two sides bit by bit. eaking use of the fact that the carry from each bit position is either 0 or I and so can be stored in finite memory. Since every formula in PA and IA can be converted to an equivalent one whose atomic subformulse are all in these siuple forms. the argument can be completed by the same induction as before. Hence vbpprpo+ A (Presburger El?3O?. Ehrenfeucht (unpublished). Buchi ?l96O?. BIgot (l%l)) W2A. PA. HA and qv are all decidable. 0 5emsr? A We have given an utterly trivial automata-theoretic proof of the decidability of PA. Even though our decision procedure has `super- elementary" ties and space complexity. it highlights the fact that the decidability follows from the finite memory requirements for performing linear integer arithmetic. See Piacher and labin El?7?? for lower bounds on the complexity of decision algorithes for PA. and Oppen Ll978? for a decision algorithe for rA with triple-exponential tile complexity. 0 2. A?i?b?p?(e rc?ar?pns Ani fiipftipn? epmnut?b1e ? finite .,.??nt In this section. we investigate arithmetic relations and functions that are computable by PA's un?er the encoding used for PA and IA ic Section 1. We call this the p?r?llPl kiaw ????ai?. Also recall the following notions from elementary logic (see Enderton Ei972)). Suppose we are given a theory T over the natural numbers ?`. A formula o+ with k `a k 4.. ?srLebIea Jaf?fl?' A caLaina N `I in z if for all M1s o+??. 1k in I. a a iff o+(z,s???s1k) La true in T. Sote tbat o+a the rigbt band side. z?s o+??s 1k really stand for tbe CDrreapondins s?erals" in the forial language. Va shall not introduce separate notations for nusarala. The grsnh of a function fi tritta wh(L). La defined aa the (k+p)-ary relation grapb(f) 2 (?(z1.....1k.y1.....y?) a I ??`j5???5Mk? 5 (y15???.y?) ). A forinla o+ vith k?p free variables pef?nes L Fu?ctpn fi ub.iip ? z if o+ 4efinea graph(f) in T. A relation or a function La p.f??.b1. in T if there La a forinla tLat defines it in T. Clearly. the failiar order relations ? etc. are easily definable in PA and SA. In the sequel. Va shall sake use of such definable relations and functiona vithout further erplanation. Fros the proof of Theora 1.1. vs isiediately obtain Lezint L (fluchi Lls6o)) `very relation definable in IA is recognizable in parallel binary encoding by an IA. 0 The converse to LeiIa I also holda: Z Ivery arithietic relation recognizable in parallel binary encoding by an IA is definable in IA. "`pail fly arithastization of IA coiputations. For input of length n. a acceptiag coMputation by an IA is a zequence of n?l states ?o? 5?s o+??s 5a5 vhere o+i is the atate the IA La in after reading the firat i syabols of the, input. end 5a is a accepting state. Thus by definition. o+0 is I' the isitial o+tate of the VA. V.r a k-arp relation. each input a7.hol is a k-tuple 0 015 end l's? vs can also encode each state as an a-tuple o O1s and l's or so- a such that the VA has at aOat 2' atates. Then the transition function 0 the VA can be speciied as ? (k?2a)-ary relation D (0?1)t+2U? whereas the set 0 inaL states is an 5-ary relation A I to.l)1. This arithaetization produce. a deinition 0 the VA that is identical to the propoattional-caLculus forialisa 0 luchi ElS6Oi. To say that a k-tuple 0 natural nunber. A : (xl????0Mk) is accepted. we assert thet there La an u-tuple 0 natural nuabera A (y1.?.?.y,) which encode an accepting coiputetion ?5l?????0n? on A in parallel binary. Without loss 0 generality assune that so- ? 0. Then the assertion La aade as a disiunction 0 ? subassertions. with the ith aubassertion corresponding to the 11guess" that xi is the usijaula coaponent 0 A. The aubassertion is k 1??0 A ft:1(xisii) A Transiti A Accepti. Transiti asserts that the sequence 0 stats changes is correct. and Accepti asserts that the lest state is accepting. under the assunption that i? is the `axinun coaponent. Let A o+ a ` (c1.....c,) and 4' (d1.?.?.d,) be 0-1 vectors; also let be v. and PI be a. A is intended to be an input syibol. whereas h. ?. and 4 are intended to be ancodings 0 states. In particular. 4 encodes the initial state Than: Accepti: w (ViCPw2(s) A `%`i A 25??i heA ??A,1 (So+7j Pbj rj)?? :0 TramsLtLS `v Ca? It? A isi ?1?yj Pbj 7j?) ?5??cD tsl ?10x? A ????5 (hi3(5?) A a:2a' A asj ? `v E? (aextP? t:l It ) A (:0yj Phj 7j) A ?l ( s'.Yj Pc? Yj) 1). All these foraulee do Le to extract the appropriate hits ros the se?uencea and make sure that when reassembled as input avuboin and states they yield accepting states and valid state transitions. Vor instance. 1 a Le a power 0 2 and h is an adimensional 0-1 vector. then the conjunction a ?E??j 0b vj) j:l j simply says that the coeficients 0 a in the binary representations 0 the yj oTh the vector k. lotice that the irst conjuact 0 Transiti validates the first transition. whereas the second conjunct vslidstes all subsequent tranaitions. U Lenmas 1 and 2 yield ?eprem j The arithmetic relations recosnisable in parallel binsry encoding by FA's are exactly those definable in BA. (1 t?ark L Theorems 1. 2 and 4 0 Buchi (l9?O) together imply that 0 can be removed fron BA in Theorea 1. His Theorema 1 and 2 establish an equivalence between FA's and W2A similar to our Theorem 1. whereas his Theorem 4 asserts the analogous equivalence between U2A and BA minus o+. 21 lowevar. the proof of bis Theoren 4 La incomplete beesuss the fornuls be save for the relation 1(x.y): I is a power of 2 sad I occurs in the represestation 0 y as a su. of powers of 2 La incorrect. We believe --Ho+ but have not proved that both Pw: and o+ are indispensable in La-a 2 and Theoren I. i.e. fluchi's Theorsa ? is false as it stands. Of course it is trivial to nodify fluchi's proof to show instead that W2A and IA are equivalent. In fact. our proof of La-a 2 La essentially a "short-circuit" of Buchi's proofs for his Theor?s 2 and 4 (second direction. modified). 0 1 Meyer (l973? showed that the tins complexity of the decision problem for W2A is not elenentary-recuraive. so the sane holds true for IA. This highlights the tremendous junp in the complexity of the decision problem caused by the addition of Pw: and 5 to PA. for which a triple-exponential upper bound baa been established (oppen Elnal). 0 5?mprk ? It is obvious that vs could obtain different versions of Theoren I by varying the bass of the encoding. In each case the resulting arithnetic is a strict extension of PA. as can be seen from the fact that the only sets definable in PA are ultimately periodic (sea rnderton El972. Theorem 32F)). Clearly the additional power is entirely due to the base of the encoding. It is natural to conjecture that the base.independent power of rA's is exactly PA in the sense that the arithmetic relations recognizable in all bases ? 2 are exactly those definable in PA. A proof for the case of unary relations (sets) was obtained by Cobhaa (l%9?. In a private conversation. Dr. Cobban informed the author that he had extended the proof to the general case, 22 tbfa new result La so far unpublished. (1 Wait to oxtead Theore I to functions coaputabie La parallel biasry eacoding by DvA'a. Va adopt the conventioa that the DF viii accept its input argunenta La parallel binary encodlul. and viii oven'rite these vith the output valuca La parallel biasry encoding. the lesat aigaificaat bLts of the input sad output being aligned La tha asIa tape aquare. L=a 1 ivory function definable in BA La coaputable ia parallel binary eacoding by a (l?reverssi) DF&. Let the function fi Bk?p be defined by the fornuis o+. L.e. o+ defLnea k grsph(f) thich is a (k+p)-sry relatLon over I auch that for `very A C I there is a unique A C 1IP vith (?.:) a grsph(f). By Leans 1. the parallel binary encoding of grsph(f) La recognized by sone D?A v. Va define a 1- reversal DFa 1' which conputes f sa follows. Let the argunents be A. At each point. v? reebers the set of atatee that v can asauae. Initially this consLets of juat the initial atate. Suppose this aet is 5 before acie input synbol A fron (0?1)k La scanned. Then the nev set 5' La defined by : j 5O ? ?kc(O.lJ?. 5(5 s.t. v scanning (a.k) La state a can change to atate ?? 1. vurtheriore. v. finds all tuples (s.a'.h) such that a a I and a ? a? on input synhol (.k) La a valid transition (so that a' e 5'). and vrites the on the tape square containing A. This is siaply an extension of the technique of esubeat construction5 used to show that IvA's are equivalent t. nvA'a. Vben r' has gone past th? 5oCt significant bLts of A it substitutes 0 23 bite for the isput. At the saee tisa. it also starts searchiag each successive set I 0 possible states for a final state. When it finds a inal o+tate0 ?. renebers this state as the current Csuceessor?stateC and reverses its bead. flu the re-vialt to sons tape square. let the successor-state be a'. Then 7. selects. froi the set of valid transitions vritten on the square during the orvard scan. the unique tuple (s?s???) vith 5' as the second. conponent. r. then wites hon tbe square as the bits 0 the unction values in that position. and uses a as the nev successor state. This goes on until 7? has re?urned to the least significant bit position. To couplete the proof. ye need to argue that (1) at sons point a inal state viii be found. (2) in the reverse scan. there is in each square a unique choice 0 the tuple previously witten. and (3) the output values are correct. These all folloy fron the fact that 7 recognixes grapb(f). By definition. there is a unique t such that I accepts (i.t). Clearly the transitions 0 this conputation viii be uritten dovn step by step by 1. in its orvard scan. together vith sany other irrelevant transitions. When this conputation reaches a inal state. 7' viii detect it. and reverse its head. Then as it goes backigard. at each step the couputation on o+(.t) guarantees the existence of at least one previously vritten tuple vith the current successor-state as its second couponent. Because of the uniqueness of ? and the uniqueness of tbe accepting conputation on (?.?). the final state detected by I' and tba choice of the tuple at each backvsrd step nust be unique. so I. aust in fact leave ? as its output. Iota that the above procedure La really a exhaustive search vithout backtrack. It is siailar to the nathed ?ischer El%a? used to obtain 24 linear `speed-ups' La tape reversals for I-tape n(?? 0 In.rb ? V. find LesM 3 rather surprising. For exeeple. suppose v. define a function f: t'?? in terse of an o+xn integral aatrix A by ` lexiccein ( A I AL? 1. A ? ? 1 ????.AL?? I a otherwise uhere lexiconin atands for "lexicographic aininun". Then f ii definable La PA. On the other hand. it is not at all obvious fron conventional sathenatics that one can construct a u?.I to coapute f in the ciuple fashion described in L?a 3. 0 1nt & Every arithactic function conputable in parallel hinary encodins a I-reversal DFA is definable in BA. Let f: be coaputable by a 1-reversal DFA V. Then graph(f) is recognizable by a I-reversal DFA V' which on input (i.&) couputes f(A) using V and coapa?fl it with : By Lenaa 2. graph(f) is definable by a fornula in Is. El Th?prem 2 The arithautic functions couputable in parallel hinary encoding by VA's are exactly those definable in IA. 0 For a vector A : (x?s???sxc) in let ll?ll `ax Corolliry Z.L If fi "t?1p is definable in IA then there is a constant c such that for all A in with IlLll ? 0. IIf(A)II ? cll?ll. Furthernore. f is conputable in linear tine by a nultitape mm using the nornal "serial binery encoding5 for input and output. :5 By L-a 3. is c?putabla by 5010 DIA V. Let I Lava q states. Then fros the ;roof 0 Lessas 3. v. see that o+a input . I cann.t visit nore than q tape squares beyond the lost significant bit position of ? in its forward scan. as othervise I viii enter an infinite forward scan. Thus for any input. the function value La at lost q bits longer. This lives the desired linear si2e bounds. It is easy to construct a lultitape DTM vhich sinulates I, using only linear tins for conversion betveen serial and parallel encodings. 0 Cp-p?l.rv ?.? Corollary 2.1 bolda for PA? siucs IA La an extension of VA. (I We can apply the sane technique to bound the six. of ?ssall? solutions to linear diophantine systest ?beprp- 1 (laker) Let A be an ?q integral ntrix. Tban there is a constant c such that for any integral a-vector b. the linear diophantine systens 4sb a and integral baa a solution iff it baa one such that lltll ` clihIl. zLnnLs laker Eundated isnuscripti proved this theore by induction aid Baker ad look El?7A1 used it to prove a result about finite reversal-bounded counter nachines (see Theoren 2.4.1). Our proof exploits the fact that there is an IA which recognizes those (?.k) that satisfy (P). Suppose this rA baa q states. then for any h. if there is a solution : to (P). by the pumping argunent there is one whose binary encoding is at float q 2? bits?longer thai Lbat of h. 0 As another spolLcstLoa of IA's t? iLnear Liteger aritbietLe. us consider sole restricted liLataL liaca nrfl,rS--Hft (?). ii senerel. an XL? is of the for. (I) las TA AZ' b a a and inte;ral enere A is an o+q Litesral satris1 La a sonnesatLie intesral a-sector and k La so inLeral I-sector. For eacb A. and L there are three nosaihilitLes: (1) (I) is inf??i'b1p i.s. there La no A a a such that ? hi (2) (I) La Lwiki but unhp?ndpd. L.s. for any nositive integer K. there 5 aces A a a such that AZ a h and ATA ? X? or (3) (I) baa an cn?irL?t Aslununt A. i.e. A a a' At e b and TA a T& for all & a ? such that At To solve (I) leans to find out which of these three alternatives holds. sod in case (3) holda to find an optinal anlution A. For applicatLona of Iu's and iethod? for aolving then1 see Carfinkel and Nenbauaer 19721. There is no tnovfl deteriinistic alsoritho which solves (I) La ties polynolial in the size of A. and b. in fact the class of all IL??a La knogn to be lip-coiplete (for ezaiple. see?iopcroft and Ullian (19791). Mowever. a eatbenatically natural restriction is to consider (?) for each fixed A and . Each such restricted IL? can be considered as a partial function yielding as optieal A -o+ if one esLata -o+ for each h. Then we bave 21 & For each fixed A cod `. the restricted IL? (?) can be solved by a nultitape DTh in tise linear in the sine of h. and ebere is a constant d such that for each b. if (?) baa an optiMi solution . it baa one vith lull ` dilkil. Irpof: We can `.co.pleteft the partial function by letting be a for eacb h euch that (P) is icfeaa?ble or unbounded. and disebigucte it by choosing the lexiconin in case there are tvo or sore optisa. Thon the resulting function can ho defined by the ?reaburger foriula T T T T (AL:hAv?(A1:k?(?A>L&v ;p?AACL:))?) t T v (EVi(Atq) vvi(Ax:h??(A:hA?:))1 A p?) vhere CL is shorthand for "L?xicographically less than". The desired conclusions then follov by Corollary 2.2. 0 Finally. ve vish to locate the anti-tic relations cod functions conputable by PA's in the Criegorcayx bisrarchy (Creegorcayx El9??). This hierarchy is an infinite sequence of strictly increasing classes of functions ?O cS1 c52 c3 vhose?union is exactly PIF. the class of prisitive recursive functions. lach class 5n is defined as the snallest class containing ?i.z?l. ?Xy .1. Axy . y. and a Awa ft'inftinn f as icitial functions. and closed n under the operations of substitution sod linited recursion. The spine functions ?n are defined as follova: f0(x.y) a ysl. f1(x.y) a x+y. f2(x.y) a an4 for a ?2. 2C fw+i(O?7) I f1(y+l.y+l). The clan. f53+1(i.l.y) a fn.l(XSfe+l(IsY))? I in exactly Kaiser's class I of o+laasetary fuictiess (Crassorcayk tl?53. Theoree 4.??). For each class. we can think of the spine function and substitution an providing the "nis couplezity". `ihereas linited recursion providen the "refincient coiplexity1. the low conpiexity of FA conputations in desonstrated in the next two resulta. By a "relation of the clans I?? we sean a relation whose characteristic function is in 5 Thepre ? The aritbsetic relations conputable by FA'a. equivalently definable in IA. fora a proper aubset of the relations of 0 By an arithastization of FA cosputations ninilar to the proof of Len 2. using functions and relations in o Pros Craegorczyk El953. Tbeoren 4.5). we knov that o contains the following functions and relationsi nero ?xi???Ie?O identity (projection) )x1...15.xj I J ? a predecessor ?x.x-l (0 if?x s 0) order relations Axy . Ex?y) etc. renainder r(x.y) : renainder of the di?inion of x by?y quotient )xy Lxi. 7 Purthereore. by Crzcgorczyk (1953. Theoren 4.6). for every I ? 0. In is cloned under the operation of linitcd nininun. and the relations of 5 ars cloned under the operations of linited quantifiers and the operations 2' of tbe pronositioesl calculus. 1oq? `Fe can define. in S05 the folloviet feoctious for eseipulatini the biUry representation of natural nuibere: truncste(z.y) a the result of deletiq the least significant 7 bite froa the binary representation of ?. eatrsct(x.y) a the coefficient of 2? in the binary representatioc of z. and Length(x) a the exponent of the highest nover of 2 ii the bLeary representation of I. The definitions are as follova: truncate(x.O) : ? truncste(x.y+l) a 1rr..ne.;P?z???j truncste(x.y) ` I extract(x.y) a r(truncate(x.y)02) length(x) nin ysx+2 (?Icx.2E z?y ? eztract(?.a):O? J. We -v revrite the jth subassertion of Less 2 ceing the above functioae. under the sesueption that I ii the eaxiluss coaponeet of I and I. ? 0. We use t to encode the sequence ?5i'???'5n-i? Then each y? can be ? I end ve can apply the operation of li.ited quantifier to the y.?s. This overcoans the si:s problen for the linited quantifier hut forces us to treat both the first and the last transitions of the co?putstion specially. Acceptence te then aritheetized as It W 3y1.....y ?XiE subassertion?? i:l vhere subasscrtion? is k w (?c extract(xt.O),:at J t:l 30 A A'(e?tract(yj.O)lbj?) is' k A W W (ACeltract(xt.lengtb(li))Satl h (na.k)e? t:l a A ?Ceitract(yj.1engtb(Ij)?l)SCJl) j:I k A Vs%1?Stb(Zj)?l (S? ? W (At estract(xt.a)lat1 t:l A A a At sitract(y1.n-i)scj1 j:L At eztract(yj.n):bj1)). j:1 Vor tbe o+trLctness of tbe Inclusion. observe that the set of perfect squares is a relation of S0 (?rseg6rcayk tl9?3. Theorea ?.s1). Ilovever sbLs set Is not recognigable by any PA. Vor a proof. see aitcb?e t1963b1 or Minsky and rapert t11661. Alternatively. for a "vould-be" FA acceptor iitb q states. epply the pu'pins argunent to the high-order segient of 0's in tbe binary representation of ?2q+2+1)2 to obtain a nunber x sueb tbat for so.e a. o+ c z C c (21.1)2. lotice tbat this nonrecognizability proof can be adapted. vIa tbe binoilal tbeores1 to any larger base snd?or any bigher pover. El ZhLwi L Ibe aritbaetic functions conputable by iA's. equivalently definable in IA. fora a proper subclass of Let fs 1k? be coiputable by an VA. Then grapb(f) is recognisable by sole 1. Co by Theorel ? Is a relation in and bence in 0 31 Jurthemore. by CoroLlary 2.1 v. kil? that there i. a c ench that Senca since ?:l???xk c(x1+...+??l) is in so is a ?in y?c(x1+...+?+l) ( (iafl a graph() 1. The strictness 0 the inclusion is again vitnessed by the characteristic function 0 the perect squares. 0 Cprp1?irv L.L Let f: be conputable by an IA. Suppose there are positive integera i and c such that 1 ? i ? k and for all I C 1Ik? f(A) ? z?c. Then is in .0. In particular. this holds i the values 0 f are bounded by a constant. Sne as for Theore ?. vith Aiia??xt i?4e aa tb. bound for the lisited ninisue. 0 Citapter 3 leversal-Bounded Counter Machines 0. TnrrpSucr?ne Ii this chapter. ve study reversal as a conputationsi coepleaLty o+essure on the enun?.r pseh,'np sodel (see ilopcroft and t?llsan tl96??). It is well known (Minsky Els61)) that unrestricted counter iichines ars equivalent to Turing sachines. i.e. they accept exactly all the r.e. sets. Fischer. Meyer and Rosenberg El968? and Creibach Ei976) studied resource-bounded counter sachine cosputations The resources considered were tine. space. and the nunber of counters. relationships and trade- offs between these resources. as veil as hierarchies based on than. were established. Most results in both papers concern polynonial tine-bounded counter aachines. another way to neasure the resources used by a counter nachine is to count the saxinta nunber of reversals. i.e. alternationa fros increasing to decreasing and v;ep ?. that any counter sakes. So far. noat efforts have been devoted to the study of nachines with finite reversal- bounded counters. Baker and Book tl9??) showed that i-way sondeterninistic sachines with finite reversal-bounded counters always accept in linear tine. and gave a characterization of the class of recognizable languages as the sialiest family of lsneuages that contains ( anbo n ? 0 I and is closed under intersection. union. Inversa bononorphis.. hoaosorphiss and intersection with regular sets. This class was also shown not to be closed under Fleene e. Ibarra (l978? showed that the class of recognizable ian?uages renains the same even if we allow finite reversals on the input tape. lurthernore. the languages 32 have sasiliasar Parith naps. a. chat vartoea decLafos prohl?a (what Ibarra called Z-whLaiL) are recursivaly solvabla. Ibarre (Iflal also aboved that deterninistic 2-way iachines with finite reversal-bounded counters have an undecidable septincas probise by a reductios of Hubert's Tenth Proble-. whereas Gurari and ibarra (19791 proved chat tbeae acne aschinea vhen reatricted to aingle-letter input are effectively equivalent to finite autonsta. Greibach E1978c1 introduced i-way hLzl and nprr?p11y b1??? counter sachinca. Tbasa sachines bave counters that can bold any signed integer. and they accept by entertag a final state with zero counters. The blind sachines cannot detect tbe signs of their counters. and are equivalent to nondetarninistic I-way finite reversal-bounded counter nachines. The partially blind vacbinaa viii abort if any counter becones negative. and bence can verify tbat a counter is poaitive? they are sore powerful than the blind sachines. and are closely related to ZLL:i atnt and veftnr p?d?tnn? p?etpThe in particular. it is not knovn whether they accept only recuraiva sets. Finally. Gurari and ibarra (19801 shoved that sany F-problena considered in ibarra (19781 are decidable in polynontal tins for fized nunbera of counters and reversals. This chapter La divided into four parts. We begin with a study of 2-way counter nachines vith general reversal bounds. The nain results o this part relate reversal bounds on the counter sachina sodel to tins and apace bounds on both the counter sachine and the turing sachine sodela. in particular. we show that for both the deterniniatic and nondeterniniatic nodela with bounds that are at least linear. counter reversal is polynonially equivalent to Turing nachine tins. these results have several consequences. Firatly* tbey deonatrate that the relation berveen counter ?chines and Turins nachines is nore intinate than a nets instance of Church's Thesis. Secondly. they enable us to establish a reversal cospiezity hierarchy on the detersinistic counter nachine nodel. This hierarchy has the follo'iing interesting propertiess (1) for bounds that are at least linear. the classes are closely related to ties coiplexity classes on the deterninistic Turing aachine nodel. (2) the hierarchy can be extended dowiwarda through sublinear to constant reversal-bounded classes. and (3) the hierarchy can be 5refined" by the superieposition of tins bounds since on the counter nachine sodel. tins Is `exponentially weaker' than reversal. Lastly. vs obtain the corollary that 7 : ff7 if and only if the classes respectively of deterninistic and nondeterninistic counter nachines with polynoaial reversal bounds are equivalent. natural nonconstant aublinear reversal bounds are also Investigated. For nany such bounds. we show that the deterninistic reversal conplexity classes are closed under conplenentation and era strictly included in the corresponding nondeterniniatic classes. which are not closed under coapleentation. The second part establishes analogues of noeL of the results of the first part for Ivay vachines. The nain purpose of this part is to show that i-way counter sachines corresponJ note naturally to I-tape Turing nachines in that the polynonial simulation bounds are not only sharper but unifora in both directions. Thus for 1(n) and T(n) that are at least linear. a T(n) time-bounded detensinistic (respectively nondeterniniatic) Tuting nachine can be ainulated by a T(n) reversal-bounded deterainiatic (respectively nondeterninistic) 1-way counter nachine. vhereas an 1(n) 3, reversal-bounded l?ay deterainietic (respectively sondetersisistic) counter sachiec Cal be aisulated by as 1(1)2 (rupectively 1(0)21011(5)) tise-bounded detersinistic (respectively nondetersilistic) Turin: sachine. The third part concerne 2-say sachines vitb finite reversal-bounded counters. We apply the results of tbe first part to colpar. the classes of languages accepted by these sachines to so.e standard space and tise coiplezity classes on the Turin: sachine sodel. Their reletLon to 2-vay blind and partially blind counter sachines is also considered. Thue 2- vay nondeterninistic finite rever.al-bounded counter sachines are equivalent to 2-vay blind counLer sachines. and are strictly veaker thai 2-vay nondeterninistic logarithoic apace-bounded Turing sachines. vhiLu' La turs can be emulated by I-say partIally blind counter sachines. In the fourth part. we present a unified account of the theory of 1- vay finite reversal-bounded counter sachines. injectin: at appropriate points new results that we have discovered. Our contributions include= (1) equivalence of the sodel to i-say nondeterainistic siople a?ltihe?4 finite auLonata. (2) an easy algebraic technique for shoving la?gua?,e not recognizable by the sodel0 (3) algebraic characterizations of tbe classes of languages recognized by various sachine sodels1 such as ti. pushdovn autosaton. augnented vith finite reversal-bounded counter . ar? (4) an application to a decision proble in the theory of prograa schenes. Note that as we prosreas fron the first part to the fourth0 our ephasis ahifta fron conplexity issues to sore language-theoretic concerns. 3O Va conclude this Introduction vith 50.0 rasarks on notation. lace11 that a Th. DTM or NTh viii refer to a i-tape Turing nachina unless it La specifically stated that the machine has nor. than I tape or the discussien pertains to conputations that use less than, linear work apace. Iota that in the 2-tape nodel. the input tape je read-only. For a function f(n). we use DSPACE1Ef(n)). uSPACE1(f(n)?. DTUffl1(f(n)?. and Ntl?tL1Cf(n)1 to denote the appropriate conpiexity classes on the I-tape Th nodel. and lDSPACE2Ef(n)) (respectively 2DSPACE2Ef(n))) etc. to denote the correspondins classes on the 2-tape Th model with I-way (reapectively 2-way) input. u. shall alao use ??logspace" as an abbreviation for o+logsrithnic space?boundedu. I. zxa-? counrer mailtncat ?enerai r?vers?? hnunds in this section. we consider counter machines with reversal bounda that are arbitrary functions of the length of the input. A counter machine. abbreviated CN. consists of a finite control. a 2-way read-only input tape with endmarkers e and $. and finitely many counters. the counters can store only nonnegative integers. and the finite control can detect whether a counter is empty (i.e. stores zero) or not. Depending on the current configuration. i.e. the state of the finite control. the input symbol being scanned. and the subset of counters that are empty. the Cfl can choose. according to a finite sat of transition rules. to change its state. nova the input head one square In either direction. and increment or decrement its counters independently by at most one. A ?t is dettrainistic if it baa at most one choice of action under any configuration. and nondeterministic otherwise. By the ueual convention. a Ol accepts an input by entering one of several desienated final states `7 with all Counters epty. Ve eball also ass-a that a Counter Cal o+aly ewitch fros decreasing to Lucreasing wha it La epty. Foreal details are esitted and can be found in Iloperoft and ClIssan Cl%??. We write gOI instead of CM to sophasise that the eachine can be nondetetiinistic. and ma write flCM for a detereinietic eachine. For a Positive integer ?. me "rite k-O:. k-MCM or k-DCM to indicate that the eachine has k counters. One can measure conputational complexity on tbe CM model by the usual time and space requirenents. Another natural seasure La tbe eumber of reversals on the counters. which count tbe nunbare of times the counters are used. For convenience. we Lake a reversal to eccospass a growth from sero and the subsequent decrenent beck to lero. In general. nondeterminietic devices mith two or more aulilisry mork tapes do not necessarily accept recuraive sets even if recuraive reversal bounds are imposed. For example. Baker and Book El974. Theoree 21 shoved that every r.e. set can be accepted by a nondeterninistic l?ay eachine with two I reversal puahdown stores0 which is the most severely restricted such device short of the restriction of the auxiliary tapes to counters. Ilowaver. it turns out that CM?s with recursive reversal bounds always accept recursive ?sets. and we shall relate reversal on the CM model to time and space on both the CM and the Th models. Tha reversal bounds we consider will be arbitrary recursive functions of the length of the input. We first give some examples to show that CM0s Can enforce eans simple. natural reversal bounds. That is. most of the familiar functions f(n) are o+`reverasl.constructible? on counters in the sense that a C?1 can create a counter of length f(n) using auxiliary counters. with all counters making at eost O(f(n)) reversals in the process. The function 38 values left o+n the counters can then be used to bound the -.ber of reversals in the subsequent `.true1 conputations. 5-anpi. I (leversal-constructible functions) (I) f(n) I a or f(fl) c vhere c is a positLve integer can clearly be consLructed using a single i-reversal counter. (2) Suppose tvo counters bold positive nunbers I and y respectively. Then using one auxiliary counter. vs can coapute `7 in a ourth counter. all counters aa?ing at 1oCt r?i reversals. we -sieply incresent the fourth counter by I for a total of 7 tiass. each tins restoring I in one counter whiLe destroyLog it in another. (3) ror i : l? 2. let fi(n) ? I be constructible using ?? ri(n)-reversal counters. Then: (a) f1(n)+f2(n) is conetructible using k1.?2 uax(r1(n).r2(n))--H reversal counters. (b) f1(n)?f2(n) is constructible using k1+k2+3 f1(n) o+`x(r1(n).r2(n).? 2 1)-reversal counters. This amply follova froa (2). (c) f1(n)f2(n) is constructible by luplenentLog the exponentiation as f2(n) nultiplications by f1(n). it suffices to use k1.k2+S f1(n) ?x(r1(n).r2(n).f2(n)? 2 il-reversal counters. (4) By (1) and (3). all functions that can he constructed froa the identity function and the positive constant functions by addition. aultiplication and exponentiation are reversal-constructible. This depends on the fact that such functions are nondecressing. so the f?ction f1(n) Ia (c) of part (3) is either I I aluost everywhere. or 3? I alnost everyvhere. (5) Jor the constructions above. the input is scanned .cly once. Using the technique of ibarre (i?7S?. o? can in fact construct nk using o+nly tvo rL21?reversal counters hut nultiple scene 0 the inputs multiplication 0 a value x in a counter by the input length a is inpienented as I SCaUC of the input `rhile increnenting an initially eapty counter. (?) f(n) I ?logni can be constructed using three r 2 ?-revarsal counters. One siiply copies n onto a counter. and then repestedly divides by 2. counting the number 0 such divisions. (7) f(u) o+ ??l?k? for any integer k ? 2 can be constructed using b O(f(n))-reverssl counters. Call the counters C1. .... ck-i and A. k-l The idea is to conpute te o+??. t in C10 .... ck-i or t o+?O. I. 2. successively. at the sane tins positioning the input head to a distance of tk from the left enduerher. until a value t is reached such that the right endmarker is first detected. i.e. such that (t.l)k c n ? tk. A is an auxiliary counter. Initially all counters are sero and the input head is on the left eadmarher. i.e. vs are in the configuration corresponding to t o+ 0. Inductively. to change fron the configuration or t to that for t+I. ve ainply apply the binosial theoren. i.e. i i-i i (a) (t+l) a ti + Ci.it + o+ Cit o+ I Thus the CM holds the hinonial ooeficients Ci. 0 S j ? i s n. in its inite menory. It uses (?) vith i a h to move the input head k h-I k ck.It 4 ... 4 C1t 4 I 40 sositious to the rLgbt0 using the value of t La Ci cad restoring Lt La Ci vLtb the oLd 0 A. if in the process the risbt endiarker is detected. thou siuply bait vLtb the answer in C1. Otbervise. for I a k-l. k-2. o+... 2. use (e) to update Cj and finally increment C1 by I. Clearly it takes a fixed number of reveriale for each inductive etep. cod since it takes f(n) steps to compute f(n). the counters need only uske O(f(n)) reversals. (s) (n) : rn?k1 for positive integers a and k is reversal-constructible by (7) and (3). Wote that all the functions in the excaple can be computed deterainistically with one scan of the input. D it is a well-known result in elementary autoasta theory that unrestricted aulticounter aachines are equivalent to unrestricted Turing machines. i.e. they accept exactly all r.e. sets. in fact. the proof of this result for 3-counter machines also shows that Zhcnui L (see iIopcroft and Ull:?nn E19691) For T(n) ? n. if )( La a T(n) tiuc-bounded ?Tn (respectively Dm). then N has an equivalent T(n) reversal-bounded 3-NCH (respectively 3-ncfl). 0 Thus not only can CM?s and Th1a simulate each other. but in one direction the reversal complexity of a ?i simulator is linearly hounded in the time complexity of the original Th. For the other direction. in order to bound the time complexity of a Th simulator in terms of the reversal complexity of the original CM. we have to analyxe the computations of CHic with arbitrary recursive reversal bounds. This is done in Lemma I below. Our proof of this lemma is a generalisation of a proof that Baker and Book El?74. Theorem used to obtain linear time bounds for I-way 41 f?nito reversal-bounded MCM's curari and Iberre (I?SO? contains a sinilar proof f.r a result related to the essptiaeas problee of the?asse I-way nachinee. ?.u? JkC?i'i: na:nL-Ln:i ec-pu?sr?ont and s;?.1.r?n? hI flniIl Let M be an 1(n) reversal-bounded k-MCM with q states. We ehall assune. througbo?t this chapter. that 1(n) ? I for all 1. Suopose 1' accepts a word v 0 length n. Without loss 0 generality assuass that each counter incressents at lesst?tvice in each reversal. and that each operation of M changes at noeL one counter. Then ?ach reversal goes through 4 nope.: sero. nonasro and increasing. nouzero and decreasing. and tero again. We can therefor? nunber the statuses of each- counter as in Figure 1. identifying the final xero status of one reversal with the initial sero ststus of the next. The taaL caunrer ?nr. (TcS) is a vector (CSI.???sCSk) where CSi is the status of counter i. Sy the above asaunptiona. thin vector can increase by at nost one in at nest one connonent in each operation 0 N. If counter i nakes r reversals in a coeputation. then the tCS starts with (o.....o) and ends with (3r1.?e?s3r?). and each change increases the sue of the cosp6nents by exactly I. So the TcS goes through exactly k r I 3 : ri o+ I i:l velues. Cleerly as ri c 1(n). r A 3k1(n)+l. Now look at the given accepting caiputation of M on v. with r1. o+.?. rk end r as above. We seek to obtain a `succincta description of the `.1 4? 3 3. Itatusos .t sa rr?orsa1 couctel rigur. 3.1.1 43 cosputatios. For this purpose. vs first sanipulate the giveu ceputatine into an equivalent one in sole o+?ooreal forse. Consider each of the r subsequences 0 the ceputetion vith constact ICS. We call such a subsequence a .e??enr ?ach operation has an associated start state a and start input bead position p. as veil as an end stats a' and an end position p'. `rith 0 ? p. p1 n+l and Ip-p11 ? 1. A sequence of operations in a seguent is a lafla if it starts and ends vith the sane (s.p) pair. A loop is Antit if no tvo operations in it start vith the sale (s.p) pair. Since there are q states and n+2 input bead poaitions. a snaIl loop can have length at soat q(n+2). We nov isasage each segeent into an equivalent one that contains at lost q(n?2) chains of consecutive snail loops separated by loop-free sequences vhich perforce have length at lost q(n+2). To be precise. for each (s.p) pair that occurs as the starting configuration of sole operation in the segeent. vs sark the first such operation. lov repeatedly do the folloving: (1) look for a snail loop of unsarked operations; (2) resove the sash loop; (3) eark its operations; (4) insert it just in front of the initially narked operation with the sane starting (s.p) pair. Notice that because of the initial sarkinga. sts? (4) is alvays possible. Fach iteration produces a valid cosputatLon since (i) the (a.p) interfaces obviously renain correct. and (ii) the counter actions can be persuted as their totality does not produce a TCS change. The algorithss clearly tercinates. with at lost q(n+2) narked sequences separated by at usearked loop-free sequences o+f length at sost q('o+2). Wote that a sarked sequence consists of either a single ooeration or a single o+peration preceded by a chain of sarked small loop. on the same pair. To suanarize lfttlat `ftO have done 0 fat. ve preaeut a schematic representation of the computation vs obtain in Figure 2. One laat atep remains in the conversion to normal form. We asek a succinct description of each chain of amall loops. Nanely. Va vant to be able to specify such a chain in terms of the nunbers of occurrences of a small number of distinct small loops. Since small loops have length up to q(n?2). the number of diatinct small loops can be exponential in n. To suppress thia exponential explosion. we note that in the same TcS. two small loops on the same (a.p?) pair can be substituted for each other if they effect the same total change on each counter. The magnitude of such a change can be at most q(n+2). Thus we need only use (q(n+2)?l? distinct small loops for each TCS and (s.p) combination. Hence in each chain. replace each small loop by a representative. and finally reorder the representative small loops so that occurrences of the sane small loop are consecutive. This gives us the desired normal form. The normal form computation vs have obtaLned can be vieved as a scheme. fly varying the numbers of occurrences of the small loops present. we obtain a family of candidate conputationa on the sane input word v. It is easy to verify that a candidate computation will be valid iff for ach reversal of each counter. the total increment equals the total decrement. As in Baker and Book (lg7A). we set up a diophantine system to enforce these conditions. The nonnesative inte&ral solutions o+0 0 legleat 0 4, L I L I I 0 TcS chaqo I ?ItLa11y?uarted oporatLos (at float q(u+2) In eacb o+e?olt? L chain of alall loops I loop-free sequence (Length ? Ilturs 3.1.2 te abLe slsteu thes aive rise to valid couputetions on v. The variables is she syste are o+s follove: 5 S tise. i... the lentb of the coaputation 1. o+ total incresent of counter i in the ?tb ii reversal I total decresent 0 counter 1 in the jtb reversal Su I n'nber of repetitions in the 1th chain 0 narked identical snail loops. k Clurly there are : r1 I- and y-variablas. There are r seausUtS. cech 1:1 0 ehich baa at lost q(n+2) chains 0 snail loops. Each chain is usda up 0 at uost ?q(?+?)+jJk distinct types 0 susli loops. lienca there are at sost q?(ao+?)?q(n+?)4?Jk a-varishles. The equations of the systen are a ii o+?n1?1I1 ? o+ij Yij I tSij?Is . o+ij or j a 1. .... r1. I a l? o+... k `iJ Yji 5 I lA a lere 5?j,? 5ija? A1. ?ij? oij and n era nuserical coefficients derived froa the noreal fore coaputation. 5iji and o+ are the total incresent ija th and total decresent respectively in the j reversal of counter i due to one ezecution of the o+th snail loop. Pij and ?ij are the corroepondins increlant and dacresent due to operations outside the sarked small loops. Finally A? and ? are the tises of tha correspondin sections of k coa?utatioes. )Iote that there are 3 ? r1.l I r equations in the syste. iii end that `oat of the coafficients 5Lie and o+iji are 0. in particular. for any i. ja u. it least one of ij1 and o+i? unit be 0. Before vs can obtain bounds on uininsl solutions to the ayatsss. vs need to estiusts the sizes of the coefficients n?11 etc. Frou nov on. vs shall wherever possible siuply use the big 0 notation. it being understood that the suppressed constants depend only on the achine M and not on the input vord v or on the chosen normaL form conputation on v. k Thus since r and 2 r. are 0(1(n)). there are 0(1(n)) I and y.variablaa. i:l L and O(nk+la(n)) i-variables. Altogether there are O(nk?ls(n)) variables in the systen. Clearly o?j?1 o+??? and are 0(n) since a siall loop has length it nost q(n+2). and p??? ?ij and w are O(n21(n)). Iov we use the folloving result which is a slight variation of Borosh and Treybig CIflO. Theoren 5?: Let A be an nxo integral istriz. h be a e-vector of integers. and MA be thi usilnun of the absolute values of all ainors in A. If the systen AA=b baa a nonnegativi Lntegral solution A. then it has one in which for all j a l? o+... n. 10?A ? Ibi I i:l `flien our systen La ?ransforsed to this standard forust. the resulting uatrii A baa r rows and O(nt+lI(n)) col?s'. The coefficients of A are 0. tI. o+e???. 0iji and all of sias 0(n). Thi right bend side vector h has colponents 0. Pij. cij and a whose svs is o(n21(n)). Clearly any sub?trLx of A has order S r. o+and so has determinant vhoss absolute value is bounded by 48 r!to(e)?r S rro(ero+I) o+s o((rm)?1). lence niece the spIte ban a nonnegative solutice (the one corresponding to the noreal fora co.putation v. obtained). it ban one in vhich each of ts Zgj. 7ij and is bounded by OCrxnk+i1(n)x(rn)2(?l)xn2a(n)) ? O?R(n)Xnk+lR(n)?(n2?(n))2(3kR(n)+2)xn2n(n)? ` oEnk+31(n)3Cn2&(n))6k5(n)+4) ` Ot(n2i(n))6kft(n)+k$E? ` 0E(n25(n))l3kR(n)i ? O?(n1(n))26kR(n) Tbo+e by taking d 26k. ve obtain L-a I Let )( be an &(n) reversal-bounded k-NCN. Thee there is a constant d depending on M alone such that for any vord v. if N accepts v. tben there is a normal form eccepting computation of M on v in vhich (I) there are at most 0(nk+la(n)) chains of identical small loops. each containing at sont O((nR(n))dR(n)? repetitions. (2) there are St nont O(n2R(n)) operations outside the chains of smalL loops. and (3)?tha total tile. hence the maximum counter Ii:.. in bounded by c((nn(n))dD(n)). vhere n is the length of v. 0 5?pr? L In the proof of Lena 1. we could eliminate the variables xii. yij and equate the expressions for the directly to obtain a diophantine k system with only 3 r,+l equations. Tbis vould lead to a smaller value i:l ? `I for the nonstaut d but uould --H? affect the nyi$ottc arDs%L rates 0 tbe tin. and space requirenente for the TN eL-lotions to be discussed in tbe reusinder 0 this section. 0 1e--Hn Z Let M be an 1(n) reversal-bounded k-NCM. L.I 2 Then M La equivalent to an (n 1(n)losn . n 1(o) lognlos(nI(n))) time-bounded and (n+1(n)log(nK(n))) space-bounded 11Th. By Lease I. if 11 accepts a word w 0 lensth n. then there te a sorual fore accepting coiputation satisfying conditions (I) (?) low )I0 uses t tracks on its tans to simulate the k counters of 11 in binary. It simulates M as follows. At sane o+olent. M1 has its bead on the bead position of the silulstion? M' stores the finite stats and the counter oodes of the simulation in its own finite memory. and the values 0 the counters are on the tape. aligned with the current input bead position. MI can now choose to simulate sn individual operation of M or a chain of identical. legsl loops. The simulation of an indi4idual operation La straightforward. To simulate a chain of identical. legal loops (ut necessarily snail)0 M' first tries to find such a loop. Thus it narks down the simulated head position together with the simulated finite stats on the tape. sud then simulates individual operations of M until the marked position is re-entered with the recorded state. During these loop-detection simulations. )I1 assumes that the TCS does not change. and accumuistes the counter changes rather than updating the true counters. If a TCS change is detected nonetheless. as can happen if an empty counter starts increasing or an increasing counter starts decreasing. M' aborts0 Otherwise. uhen the looping is detected. MI guesses a repetition 50 factor in biury. and updates tb. counters as though the loop i. executed so simy times. saing multipiLcation and addition or subtraction in bLnary. In the process. it also verifies that no TcS change occurs. i.e. no counter is decrenented to a nonpositive value. When the counter updates are complete. M? again assumes the configuration at some point in a legal computation of M. and the simulation cycle is repeated. until an accepting configuration 0 M is reached. It is obvious that if )(` accepts some vord v. then N accept. v also. Converasly. if N accepts v. thn )(. also accepts v simply by simulating all operations 0 ?( individually. Vs mm, amalyss the tins requirements if vs happen to guess. the normal forn accepting computation described in Lemma I. For such a computation. by (3) each binary countet has o+;?ength bounded by ds(n)log(nR(n)) throughout the simulation. - fly c(n2a(n)) operations of M are simulated individuslly? each?operation takes )(1 O(a(n)log(nl(n))) time to update and realign the counters. lence the individual operations take O(n21(n)2log(nR(n))) time to simulate. Bert consider the simulation of identical small loops. Each small loop has length 0(n). so the total change to each counter by such a loop is also 0(n) and has length O(logn) in biUry. By?carrying these binary totals around vith the simulated input head.:??` can simulate each operation of )( in the loop-detection phase in o(?lo?n) time. so it takes O(nlogn) time to detect a small loop. fly (l)?M' need only guess a repetition factor bounded by o+0((ni(n))dR(n)) and hence of length 0(1(n)log(na(n))). 1Iov multiplication 0 tvo numbers of lengths O(1(m)log(nt(n))) and O(logn) takes O(1(n)lognlog(nx(n))) tims. and the `I subsequent addition or subtraction takes O(1(i)log(a(n))) tine. lence altogether the counter updates ta?a o+O(1(n)lognlog(nI(s))) tina. so that the sinulation 0 5 chain 0 identical 51511 loops takes at 5oct O(nlogn + 1(n)lognlog(nI(n))) tins. There are O(nk+lI(n)) such chains to be ainulated. altogether taking O(nk+21(n)logn + uk+l 1(n)2lognlog(nI(n))) tins. This clearly doninates the total tins for the ainulation 0 individual operations. so the len-a is established. since the entire ainuletion uses at IQat o(1(n)log(n1(n))) space for the hi-an counters. 0 Fron Lenna 2 vs obtain: Thepre ? Let `L bd an 1(n) reversal-bounded k-MCM. 1 1(n) ? n. then M is equivalent to an I(n)k+3(logl(a))2 tins-bounded and 1(n)logl(n) space-bounded 11Th M?. 1 urthereore a(n) is at least exponential. then )I' is at lost 1(n)3 tins-bounded. On the other band. if a(n) %?n. then M is equivalent to an 5b+3 (logn)2 tine-bounded and niogn apace-bounded 11Th M'. 0 Tbppre 1 For nondeterninistic sachines and bounds that are at least linear. counter reversal is polynosially equivalent to Th ti-a. 0 ??? ?I1: ??-?? rp?nutp?ipn. .nd ..?u?pt.nn It The above results can be sharpened for deterniniatic cachines. The reason is that in a halting conp?tatioo. once a flcM has coepleted a siall loop vithout any TCS change. by detersinisa it nust keep repeating the salo a-all loop until a TCS change occurs. Such a ICS change can only be the zeroing of sons cnunter. since any change fro. zero to increasing or 5, from Lacreasing to decreasing would have already occurred in the first execution of the asall?loop. Thus there is a constant c ? q such that for sufficiently large n. the computation on an input of length n is divided into constant TCS sesments. each of which consists 0 a loop-free sequence of at most cn operations. optionally followed by repetitions of a single small loop of length also at most cn. Furthermore. we know that k at most ? r sesments can contain loops since altotether the counters i:l ` k change from positive to zero ? r. times. Now let m be the o+axinua i:l L I o+th length of all counters at the beginning of the j segment5 j I I. o+... r. Clearly ml I ? We bound 1j+l in terms of mi for j ? 1. Suppose the th j seament is not ended by a decroment to zero. Clearly it must be loop-free and can increase any counter by at most cn. and so even taking the TCS change operation into account. we see that (I) 55 S m.?cn. j+l ? o+th flext suppose the j sesnent is ended by a decrement to zero. if it La loop-free." then (I) again holds. So suppose it contains small loops. The maximui length of all counters is at most m1+cn at the beginning of the first execution of the small loop. As seen above. the small loop must decreasent at least one counter by at least one. Ilence it can execute at most l?+cn times. Furthermore. it can increment any other counter by at most cn-l. Thus the maximum increment to any counter is (cn-l)(m1+cn). lience in this case (2) 1j+l ` m?+cn+(cn?l)(m?$cn) a (cn)m1+(cn)2. Clearly (2) holds for a segmcnt that ends with a decresent to zero. whether the segment is loop-free or nOt. So we can set up a system of 5, sucb ln.qualltles relatIng to ij for j I I. o+... r--H2. isles (2) U tbe jtb seguent ends vttb a decreent to sero and (I) otberulse. SolvIng tbo systee by substltuLlon. we see that t t t r-2 r-3 o+r-l ? (ca) o+(cn) o+...?(cn) where l ? L1 ? t2 ? ? tr.2. To ntlute tbe upper bound. vs eake tbe ollowjng observaLjons: k k k (a) t??2 I ( ? r1-l)+l I ? Wjo sInce tbere are exactly 2 r1--Hl relatIons I:! 1:1 III of type (2) In the cycLe becauu Lhe fIrst r-I seenents account for k only 2 r.-l decreents Lo gero. the last one beIng accounted for by the (r--Hl)CL segient. (b) AL loeL 2k consecutive tj?? can be tb. 5.15* sInce La every 2k.l consecutive TCS changes at least one lust be a decreent to rero. It then follows that k k 121r1 2 r1-l 1:1 1r--Hl < (2k+l) E(cn) o+(cn) k 2 r1+l I (2k+l) co-I k 2 r?l ? (2k.!) (cn)?2 k 2 r1 I (4k.2)(cn)1:1 k 2 r1 clearly ii c (4t.2)(cn) for j I Is o+.?. r-l. o+ov tbo lsxIsusC lengtb ?4 o+f M1 counter during the entire eciputation aust be o+j$l for son. j I .... r--Hi. since no counter is increented after the start 0 the (r.l)St k 1 ri segeent. lence the nszinun counter length ie bounded by (&k+2)(cn)ill and hence by?(4?+?)(??)kl(O) since rt 1(n) for all i I ?? o+..? k. This establishes L?? 1 Let M be an 1(n) reversal-bounded k-DCM. Then there is a constant c depending on M alone such that for any vord v. if N accepts v. then there is a unique accepting conputation of M on v in vhich (1) there are at loSt 0(1(n)) chains of identical snail loops. each containing at nos? 0((cn)t1(I)) repetitions. (2) there are at soat O(ni(n)) operations outside the chains of snaIl loops. (3) the naxisus counter size is hounded by o((cn)tR(n)). and (4) the length of the conputatlon is hounded by o(nt(n)(cn)kR(n)). `bare a is the length of v. 0 The sinulation in Lonna 2 leads to an Nm M' even if the original CM `I is detersinistic. novever. a detersicistic simulation of a DCK i. also po.slble: te?a & Let )I be an a(n) reversal-bounded k-nCM. Then ?I is equivalent to an nl(n)2logn tins-bounded and (n+R(n)logn) space-bounded DTh M'. liaaL: By Lens 3. in an accepting conputation on an input of length a. ve have an o((cn)ti(n)) hound on the counter sizes and hence an O(1(n)logn) bound on the lengths of their binary encodings. The strategy of our simulation vill be to sisulate individual operations of )( as in Lens 2. vith the `s counters aligned vith the input bead. but also recording the states in ubich each input cell is scanned (say be more than once) to detect loops. Clearly ;Lf M has q states then there can be at most q visits to each input square and hence a total of at lost qn operations before a loop is detected or a tCS change occurs. If a ICS change occurs. )(1 simply reaCts the loop-detection mechanism. If a constant TCS loop is detected. M' carries out a simulation as in temia 2 to compute the counter changes. caused by the loop. If no counter is decrmnented in the loop. then M enters an infinite loop and the coaputation could not have been acceptin?. Otherwise. for the counters that are decreented. )I? perforna binary divisions and. by comparing quotients. detemLoes the number of times the loop is repeated before a TCS change occurs. It than simulates all these repatitions in one fell swoop by updating the counters using binary aritbnetic. After that it resets the Loop-detection flecbanian. and resumes the simulation of individual operations. The process is carried on until M halts. Clearly the simulator never uses more than O(a(n)logn) space for the binary counters. the timing analysis is similar to that in Lemma 2. In each ae5ment. one must detect a loop in at most 0(n) individual simulations. and there are at float o(n) individual simulations fotlovins the wholesale simulation of the chain of loops. These take O(na(n)logn) time. The simulation of a single loop to compute its counter changes takes O(nlogn) time. Then the wholesale execution of the loops takes O(logn a a(n)logn) = c(t(n)(logn)2) time since the division as well as the multiplication of a p-bit number and a q-bit number takes O(pq) time. Finally resetting the loop- `6 detection ceclanin takes 0(n) tie.. ?ence a segeent takes C(n1(I)logn) tiee to aieulate (since a doeinates loan). and altogether the 0(1(n)) se5eent5 take ties 0(n1(n)2loan). 0 thenrp?n & Let M be an 1(n) reversal-bounded k-DCM. If 1(n) ? n. then M 4. equivalent to an 1(n)3logI(n) ties-bounded and 1(n)logl(n) space-bounded DTh M'. If furthernore 1(n) ? nloan. then ?(` is at nost 1(n) tiee-bounded. On the other hand. if 1(n) ? n. then M La equivalent to an a3loan ties- bounded DTh which is at noat niogn space-bounded. 0 Thep?e ? The polynoaisl equivalence between counter reversal and tM time also holds for deterainistic sachines and bounds that are at least linear. Furthereore. for 1(n) ? n. the class of lanruages accepted by 1(n) reversal-bounded 2-way flol's contains flTIME1(R(n)) and is contained in lTln11C1(n)3loa1(n)?. 0 ? Vith regard to Theores 3 and 5. notice that for detersinistic eachines. the polynoijal bounds are unifore in both directions. vhereas for nondetereinistic eachines. the polynocial hounds we have are unifore in one direction but not the other. 0 Cprpll.r? ?.L (Reversal hierarchy for 2-way flcK's) Let T(n) ? n2 be defined by a ?Th and be coeputed on log1(n) space. Then for any 11(n) such that T 1(n)logT1(n) T(n) reversal-bounded 2-way DC)I languages is properly class of T(n)logT(n) reversal-bounded 2-way nCM lie tbe class of 11(n) contained in the languages. This is a sis$e tranalatiso. via Theor? 5. of the r?.lt that eith T(.) as above. for any T2(n) such that : 0 T(n) there is a set vhich ii acceptable hy a T(e)logT(e) tiae?bounded DTM but not by any T2(n) tine-bounded nm (lartuania tl%Sb. Theoree 7)). Ilotice that this hierarchy result is independent of the suaber of counters. and Lhet translations of other Th coiplezity hierarchies to the CM nodel are possible. 0 aeatricting Tijeoreus 3 and 5 to polynosial bounds. vs have: _______ ? p (respectively MP) is exactly the class 0 languages accepted by nC?I's (respectively NCbI's) vith polynouisl reversal bounds. ilence P 5 NP iff poly?cuial reversal-bounded DCX'e are equivaleet t. polynonial reversal-bounded L??I's. (I I:wL I There is another open problee in coeplezity theory that has a natural fornulation on the CI nodel. Ceing the sane argulenta as is Fischer. Meyer and aosenberg (1968). it is easy to ebot, that polynoiial tise-bounded DCM's (respectively ucH's) and polynoeial space--Hbounded DCM'e (respectively NCM'e) are both equivalent to 3-vay logspace DTM?s (respectively jIm's). `lance 2flSpAC?2Elogn) a 211Sp&C2Elogn) iff for Cli's. deterninistic polynonial tile (or space) is equivalent to nondeterninistic polynonial tine (or space), 0 zjiLLhgL propertiPs nL cp,ntpr rpvprcpl ?pmple??v Ve cen derive further properties of the reversal coiplezity of Cli's `s fro. its relatios to the time complseity of TN's. Specifically. `,a aball consider bow reversal complexity is affected by (I) reduction of counters and (2) restriction to l?vay input. It is veil known tbst a T(n) time-bounded multitape TN baa an equivalent T(m)2 time-bounded I-tape TN. Thua for TN's. reduction to I tape involvee at iost a asquare loss' in tins. In the case of cK?s, the aituation is somewhat different. Creibach (l975b) proved that a l-bCM alvays accepts in ti's n3. Thus l-?IC'L'a can accept only a very restricted class 0 recursive sets. in fact. a subclaas 0 :nsp&cr2Elogn). and bence also of P. This means that for C?i'a. it is not alwsya possible to reduce to a single counter. Minsky (19611 ahowed that it is always possible to reduce to two counters. However. the obvious prime.fectorixstion encodini produces from a T(n) time-bounded k-CM a T(n) reversal-bounded 2-GI. Since the time complexity of an 1(n) reversal-bounded k-CM can be exponential in 1(n). thia method 0 reduction to two counters involves an exponential explosion in reversal coeplexity. We do not know whether there is an alternative way to reduce to two counters with a less severe deterioration in reversal complexity. However. by combining Theores I. 2 end 4. we obtain: fl?nr? 1 Let M be an 1(n) reversal-hounded k-NCN. with 1(n) ? n. Then k+4 Ii has an equivalent 1(n) reversal-bounded 3-h'Cfl M'. 1 furthersore 1(n) is at least exponential. then M' is at most 1(n)3 reversal-bounded. 1 x is detersinistic. then ?` is also detersinistic end at lost 1(n)4 reversal-bounded. 0 L.L For SCM's (respectively nC)j's) with reversal boun4a that are at least lisear. it is possible to?reduce t? tbree c.usters with only a?polyuoiial (respectively quaflic? deterioration is reversal coiplexity. 0 A sluilar phenoienon occurs with restriction to i-way input. 4ain. i one tries to encode the input tape on counters by the eathod used is the proof 0 Theores I. then the resulting i-way Ol has reversal coMplexity equal to the tile coiplexity 0 the original 2-way CX. flowever. we obae?e that the equivalent aichina XI 0 theores 7 is is fact i-way. flence: Cprpllir? 2.1 For iCH's (respectively nCu's) with reversal bounds that are at least linear. there are equivalent I-way 3-?CXI? (respectively 3--H DCM'e) with only a polynoaial (respectively quartic) deterioration is reversal coiplexity. 0 uuLxt1 kamis The reasindor 0 this section deals with aiihI?nesr reversal-bounded 01's. i.e. Cl's with reversal bo?nds a(s) such that Ifnl a 0 5 By Theoresa 2 and 4. us know that with such bounds. 101's sccepr a subclass 0 up. whereas DCX's accept a subclase 0 DTfl(11En4? and hence a proper subclass of P. Another way to bound the conpiexity 0 such languages is to consider their work apace requirelents on the 2--Htape TX sodel. Using a straightforward I-tape sisulation of Cl's with the counters encoded in binary on the work tape. we obtain. froi Lesas I. Th?pre 1 Let X be an a(s) reversal-bounded 101 (respectively SCM). with a(s) 5. Thes L(H) is in 2iigpACt2(a(n)logs) (respectively?2DS?AC12(a(s)logn?). 60 Xi particular. if lie a O? then L(M) can be accepted by a 1?00 logn sublinear apsce-bouuded 1-tape Mm (respectLvely DTM). 0 As an ezaple. vs consider the case `where 1(n) I loin. Logeritbaic counter reversal bounds are interesting in that they are sufficient. and probably elso necessary. for performing UMtY to binary conversions. i.e. the language ( bin(z)1O' : I is a positive integer. bin(z) is the binary representation of x J is acceptable by a logn reversal-bounded nCM. From Theorsa 8 and Savitch's Theore. (Savitch ?l97O)). Ye obtain Cprn?lsrv 1. The class of languages accepted by logn reversal-bounded `wCw'a (respectively flCH'a) is a aubclass of 2'wSPAC2E(logn)2? (respectively 2tSPACL2((logn)2)) Mence the class of languages accepted by logn reversal-bounded NC?'s is a subclasa of 2DSPACE2((logn)4) ? It is not known `whether fl?SPACr2Elogn) a 2nSPACE2Clogn). or `whether 2?ISPACL Elogn) is closed under complementation. These questions turn out to be related to the IJA problem. by padding arguments. a positive answer to the first question implies that ?CSL : DCSL (Savitch (1970)). whereas a positive ans'wer to the second question implies tbst NCSL is closed under complementation. In constrast. we now show that with logarithmlc reversal bounds. ?la?'s are strictly nore powerful than u???5? and the class of languages accepted by NCfl's is not closed under conplementation. Cur arguments also show that the inclusions asserted in Corollary 8.1 are proper. Let L1 a ( : v c (0.11+ 1. Clearly ? La La 2DsFtCI2Clqn?. and L1 La recogaLnable by a?l?1CM ahoen counter lakee only one revernal. joyaver: zhcwi I L1 La not recogninable by any lose revarnal-bounded SCM. lence the clan. of languagen accepted by losn reveraal-bounded SCM?a La not cloned under caiplenentation. Prop?: Anaume. for contradiction. that L1 in recognised by noane loan renarnal--H bounded k-MC? M. For convenience. ve annunne that 1' ntartn it. computation by loving itn input head onto the # in th? ieitial atate. and that the very next nova caunen the head to enter the part of the input; ve alao anaune that M halta by loving ita input head?onto the ? from the left. thun an accepting computation in naturally decoaponed into 1?f? and ri?h? to?r. an nhovn in Figure 3. Counter atatunen (cs'n) and total counter atatuaca (tcsta) are defined an before. flare the tCS got. through exactly 3klogn+l valuta. from (o.....o) to (3 logn.....3 logn). aince ve can annuan. by part (6) of giasple I. that every counter of M make. euctly losn revereala on input. of length 0. fly Leon 1. thare La a conatant a auch that M accept. input. of length a in tise c nalogn For nufficiantly large odd n. ve take a ainimal- a n=L length accepting computation of ?( on uth? for each vord v of length 2 Each nuch computation ha. length lean than on logn? hence containa at lont 0a logn left tour.. g0 now partition the net of 2 2 accepting computationa by neveral levela of clannification: a 10 (I) Divide the whole net into at lont?n gn nubaetn according to the nunber t of left tourn in the computation. kL ii. left t-r a -IJJ?v ?1gbt t?r I' `IL? WL'afl 3.?.3 o+2 `3 (2) Divide each level (I) set accordiss t? the ICS values that occur is the left tours. There arc (31055?1)t distinct TcS values. The sucher that occurs can be ? a A. o+... 3kloseel. Tor each such v. there are at 5oct c?3 loss+ 1)k ? (3 loss+ 1)kv `(3 logs+ 1)3k21055+b v choices. Hence each level (I) set is partitio?d into at ssoat 2 k b (3klosn+l)a(3losn$l)3k losn? c (loan) loss level (2) sets for sole constant b. (3) Partition each level (2) set accordins to the TCS values that occur is but neither start nor end left tours. These TcS valuca are said to be lnirit the rest are al:s. If there are v diatiact TCS values correanonding to the level (2) set. ve cas have u ? v closed TC5 values. ror each u0 there are at eost c vu ? vv choices of the u closed TcS values. So alto?ether there are at lost (v+l)vv c (3klogn$2) x(3klosn+l)3klO5fl$l c (lose)cl level (3) sets in each level (2) set. (4) Por each level (3) Set. for every 2 consecutive opes TCS values. vc have a choice or vhethcr thore La a left tour that starts is the first TCS value and ends in the second. Hence each level (3) act cas be partitioncd into at lost 2v? 23klo?n+l ? 5d level (4) sets sccordin5 to such choices. vhers a is a constant. (5) Por each level (4) set. there is as 5 c v such that every coaputatios is the set contains a left tours that chase TCS values. Mach such 2 tour has q choicei of start ?nd esd states. a. altosether there are as eost 64 c q?? q2(3kl0S5?l) c possible state interfaces for these TCS-cbange tours. vhere 0 is a constant. lence partition each level (4) set into at lost 50 level (5) sets according to such interfaces. (6) For each level (5) set. the t-s tours that do not involve TCS changes are distributed into at lost q2(v-u) catart atata. end state. TCS ?alus? coibinations. Altogether. there are at lost Ct2e4q2(v-u)--Hj q (v-u)-l c (t+q2v)? v c ??alosn+q2?3?10g5+????2(3kl0S??l) ? ?f(lo?n)2 1575 to do the distribution for 5055 constant f. Partition each level (5) set into level (6) sets according to such distributions. (7) Partition each level (6) set according to the total counter changes effected under each TcS value prea?nt. rach of the t countors can change by at lost n5 logn under each TCS value. and there ate at lost 3klogn+l ICS values. so there are at most E(n5logn?k?3klotn?l < 0g(logn)2 subdivisions for some constant 5. lance altogether there are at most m5log0?(logn)blog0M(loc0?? 1050xndxnCxif(losn)2?s(losn)' 2 3 < nh(logn) : 2b(logn) nL partLti.as 0 the 2 2 ??tatLoas5 ibore h La a eseatast. lor a-. n:L b(logn) sufficiently large a. 2 2 o+ so there are Via VI such that 1w1i I ly2le `ri 5 V2e whose accepting coiputatione are classified La ezeetly the sale way. V. now derive a contradiction by pasting together the left tours on V1 and the right tours on `r12 to obtain an accepting coiputation ?? a wIfyl. This can be done by substituting left tours on V1 for let tours oS V2 La the accepting coaputation of a Because v2."2. 0 the way the classification is defined. a one-for-one substitution that laintains all the TCS values as well as the state interfaces exists. The resulting string is a valid conputation because ye are guaranteed that the total counter changes under each TCS value resin unchanged fron the original valid couputation on ?2swa2 We conjecture that the recognition of L1 requires 0(n) reversals. but have not obtained a proof of this claja. Ilowever. the proof of Theore ? can be esodified to yield the folloving stronger results Corollary 1. Let a be a real nunber such that 0 c c c l?2. Then L1 is not recognizable by any n? reversal-bounded 11CM. Mence the class of languages accepted by ft(n) reversal-bounded gCM?? is not closed under coupleaentation for any a(n) such that there is a positive a < l?2 with lii R?n? n? n fly Lenna I. an n5 reversal-bounded 15CM accepts in tiue nsa5 for sosse constant a. We can then siaply repeat the proof by contra?iction of 66 Theoras ?. v?tb the folloviag bounds on the aultiplicative factors 0 the a bnE coC dna various levels of partitions: (I) ?50?? (2) n . (3) n a (A) 2 . (5) a 025 2a 2an o+ (6) a and (7) n?? . uhere a. b. Ca 4. 0. f end a are n:L constants. lance there is a constant b such that the 2 2 coiputations ho25logn are divided into at sost 2 sets. For 0 c a c l?2. 22 ? 2a 2hn logs for aufficieotly?large 0. and the sao+e cut-and-pests argunenta then yield tbe desired contradiction. 0 The class of languages accepted by logo reveral-bounded nCM?s is closed under cospicientation. `ence L1 is not accepted by 507 logo reversal-bounded DCM. zLflaL: Sy Lenna 3. for a logo reversal-bounded k-DCN ??. there is a constant a soch that accepting coaputationa have lengths bounded by nalOlO. We can use the sethode described in parts (5) and (6) of Ixaiple I to coupute 0alogo io one counter end logo in k counters using O(logn) reversals. Then to accept L()(). a sinuletor N' siuply runs M while sinultaneously decr.enting the n?logo count for each siouleted step and one 0 the logo counts for each ainulatad counter reversal. If M halts first then 1. reverses its result; if on)t of the 0a logo or logo counts expires first then M' accepts. D f?plljr? 1l.L For any positive ratioul nuiber a. the class of languages accepted by i? reversal-hounded lCN?a is clond under coupleasotation. lance L1 is sot accepted by any a reversal-bounded 0CM for any positive Sl ratioul ni-ber a c l?2. 0 flaaui IL The class of languages accepted by 1.a reversal-bosaded DOl's is a proper subclass of those accepted by loss reversal-bounded ICH's. The class of (respectivaly languages accepted by loga reversal-bounded mci's Dci's) La a proper aubclaaa of 2mSrACt2((logn)21 (respectively 2nsrAC?2(logn)2)) Mence the class of languages accepted by logs reversal-bounded Mci's is a props: subclaee of 2DSPACE2E(logn)&). 0 corc?la?r U.L In: any 1(n) ? I. if there La a positive nuiber a c 1,2 such that I&n:1 lii 0. 5400 then tbe class of languages accepted by 5(n) revereal-bounded mCn?? is a proper subclass of (1) the class of languages accepted by 1(n) reversal--H bounded MC?'5 and (2) the class of languagea accepted by a reversal--H bounded Dci's. 0 2. flnt-nx anLu ahiuc1 aiLk wnuL uwali In lesark 1.2 vs observed that the polynonial equivalence betveen the reversal complexity of 2-way ?IC?i's and the tins complexity of 1-tape liTh's is not uniforn. but dependa on the nunbers of counters the M??5 bave. We can restrict to 3-Xci'a to obtain unifori polynomial aquivalencee in the nondeterniniatic as well as the deterninistic cases. but even so the polynonial simulation bounds are not as sharp as one night desire? it takes an 5(?)6+C tins-bounded Mm to emulate an 1(1) 3+' reversal-bounded 3-ICH. and an 1(n) tins-bounded DTh to sinulate as `a 1(a) resereal-bounded 3-DCM5 vbere a L. any poattive real nunber. There La another Ludication tbat the relatLon betveen 2-way Ch?5 and I-tape T'n?5 La not the 1oCt intimate possible. nanely. every I-tape ni can be emulated by a I-way ?1. This leads us to suspect that a aore Lntimate correspondence exists between ivay CM'a and i-tape m's. The present section is devoted to establishing this correspondence and to atudying I-way CM's. The arsuncnta used are aimilar to thoae of the previous section. and we shall only indicate the nodifications that are necessary for proving the new results. Ve begin by restating ??e?re? L (see Mopcroft and nilman E1969)) For T(n) ? n0 if M La a T(n) time-bounded VTh (respectively Dm). then M has an equivalent T(n) reversal-bounded i-way 3-NCH (respectiveLy 3-nCH). D Now consider the analysis of accepting computations in the proof of Lea? 1.1. Suppose the machine M is i-way. a ? is now defined as a sequence of stationary operations that start and end in the sane state and the sane TCS. and a in11 loop is one in which no two operations start in the asia state. Clearly. since M has q states. a snaIl loop has length no greater than q. We can perform the same "remove and insert" operations on snail loops as before. except that we now maintain (5.5) interfaces instead of (s.p) interfaces. where a is an input symbol and p La an input position. flence in a normal form computation. each sagnent La divided into at nost qI?I chains of small loops separated by loop-free sequences in which there is an input bead notion at least once every q operations. Furthermore. each chain of small loops consists of at most subchsina of identical small loops. where b is the nun?er of 0' transition rules o+ ? lance or input o+ length a. there are altogetber at aoet (3ka(n)+l)q?:Ib?+l chaine 0 identical -all loops. and escb nail loop can change a counter by at aOst q. Thue the reaultiq diophantine systan has 3?t(n)+l equations and 0(1(n)) variables. the Satrix has entries of size bounded by q. and the right hand side has entries whose absolute values have sun at aoat C(g(n)+n). sy the aaae araunents as before. we obtain L= L Let M be an 1(n) reversal-bounded I-way k-'CH. Then there is a constant d depending on N alone such that or any word v. if M accepta v. then there is a norial forn accepting conputation of M on v in which (I) there are at nost o(n(n)i chains 0 identical nail loops. each containing at nost o?n1(n)dt(n)) repetitions. (2) there are at nost O(R(n)$n) operations outside the chains of -all loops. and (3) the total tie.. hence the aaxint- counter aLa.. is bounded by 0(n1(n)dR(n)). where n La the length 0 V. CI The sinulation of Leans 1.2 can nov be siepliCied because tbe inits control 0 the sinulator M? can store all possible -all loops 0 II. so there is no need to search for -all loops during the aiaulation itself. ?urthernore. counter updates for a chain 0 identical snaIl loops can nov be done in a single pass over the binary counters. since they involve only additions. aubtractions. and nultiplications by constants. lance Le? 1 Let M be an 1(n) reversal-bounded I-way k-MC?i. Thcn )( is equivalent to an (R(n)+n)(t(n)logR(n)$logn) tiae-bounded and (n.l(n)logR(n)) apace-bounded Nfl!. (I 70 L Let bi be an 1(a) revarsal-bouded I-say k-?ICM. If 1(n) ? a. then ? La equivalent to an 1(n)2logR(n) tins-bounded and Itn)logl(n) space-bounded Um On tbe other band. if 1(n) ? n? tben M La equivalent to an n2iogn tile- bounded and nlogn apace-bounded nnt ?`. D Th.pre- I 1cr nondeLerainiatic nachines and bounds that are at least linear. counter revereal is polyncilally equivalent to Th tins. lurtheracre. tbe polynosial equivalence La unifori: the ainulation bounda are linear in one direction. and superquadrstic but aubcubic in the other. Thue for 1(n) a n. the class of languages accepted by 1(n? reversal- bounded I-say 1C?I's contains 1T1l1Z1(1(n)) and La contained La 1r1121El(n)2log1(n)?. 0 leit consider accepting coaputations of an 1(n) reversal-bounded I vay k-DCM. As before. let a. be the naxinua counter eLse at the beginning of the jth ae?ent. Let nj be the distance noved by the input bead during the ?th se?ent. the recurrence relations bounding 11.1 in teras of Cow becoas 1j.l ` a?4qnj if the ?th segnent is loop-free and o+j+l ` qlj.q'nj otbervise. Solwiq as before. vs obtain tr.2 tr-3 S q n1+q n?....q n?2 b r ahere I ? t1 ? ... ? ?r-2 a ?.1rL. Since i!LCi a 11 k ? ??qi?j?L 2 r?I ?i:lo+? o+ a q-l k 2 ri c ??qiSl ? 2?qk?(n) This yields I Let ? be an R(n) reversal-b?ded I-way b-DCM vitb q states. lor any vord v. 1 ?I accepts v. thea tbere La a uciqee accepting co.putation 0 M on v in vhich (1) there are at `oat O(R(n)) chains 0 identical easil loops. each containing at coat 0?0qtk(n)? repetitions. (2) there are at `oat O(k(n)+n) operations outeide tbe chains 0 acall loope, (3) the caxinuc counter sise is bounded by 0(nqkl(n))? and (4) the Length ot the cocputation is bounded by `rhere a La the length 0 V. lence i 1(n) ? logn then M accept. in polynocial tics. 0 L-a ? Let li be an 1(n) reversal-bounded I-way k-DCM. Then I is equivalent to an (a(n)+n)(1(n)+lou) tics-bounded and (1(n)+n) apace- bounded DTh M'. The counters have binary encodinga 0 length at `oat 1(a) +log.. It takes a constant nucher 0 passes over the counters to perora the updates or a chain 0 identical acall loops since only additioca. 72 snbftaetione. end unltiplicatione and divisions by constants are Luvolved. Tha tiuing then follows fron Lesaaa 3. D I ,?otice that the sLaulation of Lansa 4 requires at least alog0 tile for all 1(n) ? 1. This is consistent with the following fact.: (I) there are DC?('s with reversal bound R(n) I I which recognize nonregular sets. and (2) if Ii. : ? then flT1)(1(f(n)) is the class of regular sets ___nlogn (Hsrtaanis El96Sb. Theores 2?). 0 Thpnrp & Let M be an 1(n) reversal-bounded I-way k-?)I. If 1(n) ? n. then ? is equivalent to an 1(n)2 tile-bounded and 1(n) space-bounded nTh ::`. Oa the other hand. if 1(n) n. then M is equivalent to an tins- bounded and linear space-bounded DTh. 0 5???rk ? The s?ulation bounds in Theoress 2 and 4 are both very tight. since the set of palindrones L1 can be recognized by a I-way n reversal--H bounded nCfl but requires n2 tine on an Nm (for a proof. see IIopcroft and nllnan ?I969. Theoren Io.?)). 0 Theprp? ? The unifom polynonial equivalence between counter reversal and Th tile also holds for detersinistic nachines and bounds that are at lesat linear; the sinulatioc bounds are linear in one direction and quadratic in the other. Thus for 1(n) ? n. the class of languages accepted by 1(n) reversal- bounded I--Hway DCH's contains DTl?!E1(R(n)) and is contained in DTl?1E1l(n)2). 0 Cprp??,ry ?.L (Reversal hierarchy for 1-way n?i'.) Let T(n) ? n2 be defined by a flTh and be ?onputed on lonT(n) space. Then for any 11(n) seeb that T1(e)2 T(n) so the class of T1(n) reversal-hosaded ??ay DCII laq.ases is properly contained in the class of T(n)loaT(n) reversal-boanded l?ay DCII languases. (I Zhcaua n r (respectively 1??) is exactly the class 0 lanauases accepted by I-gay flCM's (respectively SCM's) vith polynoaial reversal bounds. `lance P o+ II? iff polynosial reversal-bounded 1-vay nC'sI? are equivalent to polynneisl reversal-bounded Ivay SCM's. 0 Tb?pr? L Let 5 be an 1(n) reversal-bounded 1-vay k-NCM. vith 1(n) ? Then `s has an equivalent 1(n)2logl(n) reversal-bounded 1-vay 3-bC's M0. If `s La detersinistic. then `s' is also deterniniatic and at sost 1(n)2 reversal-bounded. 0 Finally. sone of the results on aublinear reversal-bounded 2-vay Qi?5 can also be carried over to the l-vay cases zhcaua L Let `s be an 1(n) reversal-bounded 1-vay SCM (respectively ic's). vith 1(n) n. Then L(M) is in l'ss?ACE2(1(n)loal(n)+logn) (respectively lDSFAC2(1(n) + losni). In particular. if lii ??n?1n.55(?? ? 0 (respectively lie s 0). then n?qo n sooo L(M) can be accepted by a sublinear space-bounded 1-vay 2--Htape ffflI (respectively bTh). 0 Cprpllarv a.L The class of languages accepted by loan reversal-bounded I-way MCM'. (respectively n?I's) is a aubclass of both STIMg1Enlognloglogn) and luSPACE2LIognloglogni (reape'tively 74 DT7Mf1(alogai and Ibapaci2tlogni). 0 I As obsersed in iciark I. lTT)(1(nlogni is a ainisal ?nonregular ties coaplezity class on the i-tape DTM sodel. Corollary S.l shows that the class 0 languages accepted by logn reversal-bounded i-way DCn's separates this class iron the class of regular sets. 0 Thpor? I L1 is not recognirabie by any loan reversal-bounded i-way 1C?. lence the class of languages accepted by logn reversal-bounded i-way aCh?5 is not closed under coiplessentation. 0 In fact. by considering the configurations in vbich the iachine scans 5, vs obtain: Cp?pll.r? I.L L1 is not recognirable by any n5 reversal-bounded i-way MC:: for any positive real nuaber a c 1 lence for any 1(n) such that there is a positive a c 1 with lie 0. n the class of languages accepted by 1(n) reversai-bo?nded i-way MCfl?? is not closed under couplenentation. and the clsss of languages accepted by I(s) reversal-bounded i-way Iclils is a proper subclass of those accepted by a reversal-bounded i-way DcK's. 0 At this nonent. we have not established any i-way analogues of Theorens 1.10 and 1.11 and their corollaries. The difficulty is that by our convention. bounds on reversals do not apply to nonaccepting conputations. With 2-way input and natural hounds one can easily preconpute such bounds on counters and use thee to detect and halt nonaccepting conputations that attenpt to exceed the bounds. so there is no loss of generality to assuns that reversal bounds apply to ALL - conpatations. A sisilar argunent is used to show that `any `natu?al' 2- vey deterainistic reversal ceplezity classes are closed nader coepleo+entation (Theore 1.10). This arguesut breaks dove for 1-vay input because it is no longer possible?to precoapute reversal bounds. and it is not clear vhether the natural 1-vay detereinistic reversal conpiexity classes are closed under coeplesentation under our convention. This leaves open the question of whether tbe inclusions cf Corollary fl.l are proper. Vs conclude this section with a generalisation of a result due to Ibarra E11781. ZiLowi flL Let M be an 1(n) reversal-bounded 2-vay k-MCn for which there is a positive integer I such that in any conputation. M can reverse its input bead at nost I tiess. Then M baa an effectively constructible equivalent eai(l(n).aI reversal-bounded 1-vay (k+l)(ao+l)-1IcK M'. lance finite reversals on the input can be elilinated by adding counters with the sas reversal coaplezity. rrpnf: (Ibarra) Ibarra proved this theorna for the special case in which the reversal bound 1(n) is constantI his proof also works for general reversal bounds. We give a sketch of the proof. A 2-vay MCM is in flwLL Lazi if (a) the input head can only reverse direction at the encearkers. and (b) acceptance is only eade at the end?rkers. fly a standard sieulation argunent. II baa a equivalent Mz(1(n).U) reversal-bounded noreal-fore (k+l)-uCM ? which reverses its input bead exactly e tines in every accepting conputation. Ibarra then showed how to construct a Mu11a aachat which 7' ailultane?aly simulates several !`CM'a in nomal forss. Specifically5 if Mi is a ki?WCM in norasl fori. then the parallel simulator N10...0M1 is a (kl4 `.4k5)-MCN which. on each visit to an input tape square. simulates tbe actions 0 each Nj with a private finite control and a private set of ki counters. until all N. are ready to love to the next input tape square. Notice that because they are in nornai forn. the Mi are bound to love their input beads in the sane direction. and hence one co-non head suffices, Also if each Mi is determiniatic. so is N1O...sM5. The accepting states of the parallel simulator are left unspecified. R The next construction is a ? s,??i1.?nr N0 for No This is a aax('(n).a) reversal-bounded I-way (k+l)-tiCH which. given a configuration (state plus counter contents) at the left enduarker of an input. will traverse the input in a left-to-right scan. entering successive configurations which. when reversed5 constitute a correct sequence of operations of N0 coaputing on the same input in a right-to-left scan. Thus if starting in a configuration c1 at the left endnarker enters a 0 configuration c2 on reaching the right endnarker. then ??. starting in the configuration c2 at the right endnarker. has a sequence of operations that leads to its entering the configuration c1 on reaching the left endiarker. The simulation is similar to the construction of an NFA that accepts the reverse of the set accepted by the N?A F. with extra details added to handle the reversed behavioura of the counters. Notice R that even if is determiniatic5 N0 will in general be nondeteruiniatic. Finally., take `+1 machines N15 ??s No++1 such that M15 N3. ... are just R restricted to one forward input scan. and N25 N45 .. are M0. Thus all Mi are aax('(n).nI reversal-bounded I-way (k+l)-IICN'a. Now construct the I-way (?.I)(o++l)-NcM N0 a M?...o??1. The siaulator M' contains a eppy of It glasses eel eomfLgiratlois for ?: c1. c2 5 c3. c4 5 C55 o+?` with e1 I the initial coafiguration aid a e1+1 an accenting configuration if e La o+dd. and runs M with M. starting Li CL. When reaches the right endiarter. with M. in the configuratiou I : c?. c3 s c?? and that co+o+'l is an accepting c1. M' verifies that cj configuration if a is even. It La easy to see that M? La equivalent to aid hence to M. Furthermore. for v in L(M) such that lvi a ?? there La an accepting computation by ?0 in which each counter mates at lost aax(a(n).n) reversals. then M' baa an accepting conputation on v in which Mi guesses the Lth input pass of this conputatiom of )??. In the resulting computation of )(` the counters are at lost iax(1(n).n) reversal-bounded. This simulation is a generalisation of the construction of an ??& F' from an NFA F. such that F? accepts the set f x : I accepts (1zI)L(I+l)?2J ) if a La odd5 or 5 I I accepts (xx1)L(o++l)12J1 ) if a La even. Ilotice that M5 is not determiniatic even if W is. Cl 3. Lta-waut `tiLnLcL ?pchines wirh f(nits u1LwLxuaI hnnn?a This section is devoted to the study of CM's with 2-way input ad Constant reversal hounds on the counters. It is easy to o+ee tbat a t--Ho: with a reversal bound of I is equivalent to sole hI-Of with a revereal bound of 1. `lance we Can restrict our attention to machines with single-reversal counters. We shall write SM instead of Of for such a o+achine. SimilarLy llS?. k-'lSll. etc. Note that the nunber of reversals 70 of tbe input bead is still unrestricted. Vs basis by considering tbe conpiezity of 0)1 languages. fly tbe sane argunents as in Lena 1.1. vs obtain L=L L A L-fFSM always accepts ii tine 0(03t?5)? We proceed as in tbe proof of Lena 1.1. up to the point where vs bave set up the diopbantine syste. We now use tbe fact that 1(n) 1: I to obtain a abarper bound on tbe leogtb of a sininal accepting cosputetion. By directly equating tbe expressions for tbe total increent and the total decrenent for eseb counter. vs obtain a syste with k+l equations and 0(0k?l) variabLes. The iatrix baa entries of size 0(n) as before. wbereas tbe rigbt band side baa entries of size 0(n2). Tberefore the nazinun absolute value of all uLnors in the aetriz baa size (k.l)1?(nk?l) wbicb is 0(0k+l) tbus by the result of Boroab and Treybig (lfl61 we obtain an accepting coiputation of length 0((t4l)?nk+lz(n??l)2z(k+l)n2) 0(03k+?) 0 We aball also eats use of the following result: Th?pr? L (Creibach E1975b. Corollary 2)) A lancuage accepted by an cd tins-bounded t-)ICH can be accepted by an 03(kd+l) tins-bounded I-way 2--H taps DTw. 0 Conbiniog Lensa 1.2 and I with Theorens 1.9 and I. we obtain: I Let M be a k-US)1. Then (I) N is equivalent to an 5k+2??g? tins-bounded 11Th. (2) M is equivalent to an 53(3k2.5k.I) tins-bounded i-way 2-tape DTK. so that L()() is is ?. 1, (3) L(M) Is La 211S?AC12Closn?. Jurthereore. the clam of 15)1 lenguaSes Is a proper subelass o 211S?AC2E1oSn1 -- hence also 0 P --H and 0 the clam o polys-Lal tile-bounded (equivalently apace-bounded) 2-say 10' 1engua?ea. and La sot closed under coiplenentatlon. Prppf? (1) amply follows fron Lenaa 1.2. (2) follows fron Len-a I and Theorn I. (3) follows fros Loses I since losarLthaLc apace sufficea to sisulate polynonially bounded counters in binary. The last o+aaertion follows roa Loses I. Theorsa 1.? and the facts that 2 (I) L1 can be recogni:ed by a 2-way logapace DTM and by an o(?) tias- bounded 2-way bCM (Fiacher. Meyer and aoeenberS E196S. Theoresa l.3?)a (2) 2)(SPACL2Elon) s ?. and (3) r1 can he recotni:ed by a 1-115)1. D We can obtain siailar results for DS?. We shall late use of Tb?pre? 1 (Curari and iharra E1979* Theore. I)) Let II be a k-flSM vltb unary input. Then L(M) is a reular ast effectively conputable roa 11. 0 Zhcaui A Let N be a t-flSM. Then 11 accepts in nk+l tile. Furthermore. the class of DS)1 languasee is a proper aubclass of DTlMc1(nlon?. 2DSPACE2Clon? and the class of polynoasial tine-bounded (equiwalently apace-bounded) 2-way nai lansuaeas and La closed under couplesentation. ProofI The first assertion follows fr? Lsaes 1.3. The proper inclusions of the DSM languages La 2nsPACs2Elose? and La the so class o+f polynosial tiie-bounde4 2?ay ?CM languages then follow by the same arsusents as for Theore 2. 5y Less l.?. )( can be simulated by an nlogn time-bounded I-tape Dm. nence it only remain. to show that there is a language in ?l?!L1Enloan? not recognizable by any k-DSM. An example of such a language is 2n L2 : a : n ? 0 ). By Bennie El96?J. L2 can be accepted by a I-tape nTM which sakes loan passes over the input. every time marking every second unmarked "a" and making sure that the last unmarked "a" is now marked. until only one is left unmarked (this is equivalent to successive divisions by 2 with no remainder). However. L2 cannot be recognized by any DS)I. as otherwise by Theore. 3. L2 would be regular. a contradiction. The proof of closure under complementetion is similar to that, for logn reversal-bounded u?t?s (Theoren 1.10). 0 flp?ark L For 2-way DC??s. we obtained a general reversal hierarchy ,ruult for bounds that are at least Linear (Corollary 1.5.1). For bounds that are at most linear. we know that (1) nC reversals with c < l?2 are strictly less powerful than linear reversals (Corollary 1.11.1). and (2) constant reversals are strictly less powerful than logarithuic reversals (consider L2). We conjecture the existence of a rich sublinear reversal hierarchy. 0 )Iext we conaider two variants of 2-way NOl's introduced by Greibach (l?78cJ. A hiinc CM is one whose counters can hold any inteser. Its finite control is unable to detect the sign of any counter. i.e. its SI tran.itions depend only on the input sysb.l being scanned and on the state of the finite control. A n.rr's?1i b1'n? CM is one whose conters can bold only nonnegative integers. Like tbe blind CM. tha partially blind 0! cannot detect the sign of any counter. However. if an attenpt is nede to decrenent a zero counter. tha sachine eborts. Hence a partially blind CM can verify that a counter is positive. although it cannot in general verify that a counter is zero. Acceptance is by final state Ant enpty counters in both nodels. uc shall write BC)'. k--HSC?I. PC?! and k-P0! for blind and partially blind C?!'s. It turns out tbat even though HCllte are allowed unbounded reversals on their counters. their 5blindness5 is such a severe constraint that they accept e:actly the ?ISM languages. theora I of Creibach El978c? clained this result for l?vay sachines. but her proof seas to be inconplete. However. it is easy enough to supply the lissing arguflents. which in fact generalise to 2vay tzchineas Theorsa ? Ivery k-NSM has an effectively constructible equivalent k-HCM. Zvery k-BCM has an effectively constructible equivalent 2k-lISM. Hence the class of ?ISM languages is exactly the sane as the class of SCM langueges. ProoFs Let M be a k-MSM. then a k-BCM M' can sisulate M by storing is its finite control both the finite control of M and the atatuses of its counters. At each step. on the basis of the input synbol scanned. the state of the sinulated finite control of M. and the stored counter statuses. M' will pick a transition of M to siaulate. If the transition does not involve a decrenent to any counter. Mt will in fact be able to 82 cpdste tbe etored counter etatuses correctly. Otherwise it will have to guess whether the decreent has zeroed out the counter involved. The fiesi states of M' are those that encode final states of M and final epty statusee for all counters. To see that M? is equivalent to M. observe that a counter is left unchanged once XI has guessed that it ie ?pty. So at the end of the sisulation1 it is truly enpty iff M' has sade a correct guess. Since M' only eccepte with epty counters. if it accepts a word w1 it has nede correct guesses for all the counters; this jupliss that the stored counter stetuses are true during the entire sinuistion. which is therefore a valid coeputation of X. So M accepts w also. Conversely. if M accepts qi1 there is a sinulation that leads to the acceptance of v by low suppose M is a k-flCM. Since )( does not need to knov the signs of its counters for its operations. a 2k-lISM XI can sisulete II using two counters t? accuenlats the total increnent and total decrenent to each counter of M. uhenever M enters an accepting state. X? can choose to guess that M has reached an accepting configuration. To verify such a guess. M' need only check that the total increncnt equals the total decreent for each counter of M. by sinultaneously decronenting each pair of sisulating counters. M' accepts iff these conditions are indeed satisfied. By the usual argunents. X' is equivalent to n. o Vs just saw that )iSM?s are equivalent to BCM?s. in fact. the proof shove that they are both equivalent to finite reversal-bounded IcIl's. Vs no, consider roi'.. which intuitively are nore powerful than BCX's in that they can verify if a counter is positive. romelly. it is easy to S3 see that the?proof of Theores 5 also shows that PCK'a cas siMulate ISM?s. Ve shall prove a stronser result: PCM's can sisulate 2-way logapeco I'm's. which vs have shows to be strictly uore powerful than ISM's (Theoren 2). The crux of the proof is the fact that with the aid of its 2-way input tape. a PC' can test ceptiness of linearly bounded ;counters. This shows that PC"s can emulate 2-way nondetersinistic nultihead finite autonsta1 and the desired result then follows fros: Thpnr?m ? (flartianis E1972)) 2-way logapace NTh's are effectively equivalent to 2-way nultibead IrA's. El Tbppre L Civen any k-head MFA I. we can effectively conatruct a equivalent (2k+2)-PCM I'. Rence the class of PC' languages conteins 2ISPACE2Elogn). and POl's are at least as powerful as polynonial tiec-bounded (equivalently space--H bounded) 2-way IcI's. Proof: I' uses a pair of counts and y? to sisulate the ith bead I? of M. These counts will reside in different counters at different tiMes. but the finite control of I? can keep track of their whereabouts. There are two sitra counters for nanipulative purposes. Let the input have length n. Then the input positions are nuihered fron I to n. with the left endsarker e at position 0 and the right end,srter o+ at poaition 1+1. At any nonent. if Ii. is on tape position ?i' then x? s p and y? 2 n?l?pi1 The extra counters are cipty. Clearly. these counter values can he set up for the initial heed positions by leaving each a ? and by settiq each y? 5 eel vith a single scan of the input tape. It only renains to show how I" can sinuate each transition of I correctly. First of all. N' baa to deterii? the syibol under each bead of M. Let the extra countara be C1 end C25 both epty. Consider H?. Startles vith Its true head 1k on ?. 1k' viii love 1k to the risbt until it reaches o+. At the ease ties ?? decreients 11 and increments C1 until at seme point, K5 arbitrarily switches to decrementing Yj and incrementina C2 instead. Vben it lakes the switch. 1k' also stores in its finite control the input avnbol being scanned by Ii. If Ii successfully reaches $. then 1k? lust -- have nade the switch just at the loment when li is on position x?. ror if It baa not nade the switch by then. the x. count will just have becone sero. end the next love will cause an abort. On the other hand. if 1k' sakes the switch with Ii. on sole position p < x?. tl?en it takes n+l-p ? 5+l?xi : further loves to reach $. and there would have been an attalpt to decremen& the y1 count below zero. causing an abort. Thus if I successfully reaches $. then C1 and C2 vill end up containing xi and respectively. the counters originally containing x? and y? will becoac epty. and N' will have obtained the input syebol currently under 1k? in the siaulation. Furthemore. there is always a correct guess of the switching position for this to happen. 1k' will then relabel the Counters5 and continue to pick up the synbols under the renainins heads. After all k input synbola have.b?en picked up. 1k' will still have the pairs of position pointers (x?.y?) in 2k counters. with the relsining tvo counters empty. Now 1k' will choose a transition of 1k to perform: this Involves. besides changing the state of the sinulated finite control. updating the counts XiS ?? to reflect the lovelent of N? 1k' Is now ready to sinulate the next love of fl. This goes on until 1k enters a final state. Clearly 1k' is equivalent to 1k by the argulents clrendy ss gLven. 0 The asia technique can be used to shou Cnrp?1.ry L.L An arbitrary o+ultibsad ?CM Is effectively equivalent to a single-bead PC". cl 1.? The class 0 ECH languages is closed under coccatoestion. ProoFt Let Hi and H2 be a k1-PcH and a k2-PcH respectively. Vs shall construct a 3-head (k1+k2)-Pcn M' to accept L(w1)L(M2). One bead. naned 1. is used as a read head for the ei.ulations; another head, nased I. is used to separate the input tape into L(N1) end L(M2) segnents. The renaining bead A is used as an auxiliary head. On any input. N' starts by sendins S out to a guessed separating position. This position is then the 5virtual" position for the $ 0 the L(N1) ae5uent. Vith a and A on e. H' atarte ainuisting Nj with k1 0 the counters. using a as the read head. Every tise I is noved risht. K? will check to see if it has noved onto the position of 5. This is achieved by sinultaneously caving a and 5 towards ? and A away fron e. and seeiq if a and 5 reach d at the sane nonent. a and 5 are then restored to their original positions by reversing the nations of all 3 beads until A reaches ? agsin. If a and 5 are on the sane position then NO uses $ as the input synbol for the sinulation of N?; otherwise it will use the real syubol under a. This goes on until Nj enters a final state and M0 guesses that its counters are enpty. NO will then cove a to the position of 5 using A. nove 5 one position to the left. and sinulate on the right seccent of the input with the reasining k2 counters. checking for coincidence of a and 5 as before to eake sure that the left enduarker ? First of all. N' baa to deterii? the syibol under each bead of M. Let the extra countara be C1 end C25 both epty. Consider H?. Startles vith Its true head 1k on ?. 1k' viii love 1k to the risbt until it reaches o+. At the ease ties ?? decreients 11 and increments C1 until at seme point, K5 arbitrarily switches to decrementing Yj and incrementina C2 instead. Vben it lakes the switch. 1k' also stores in its finite control the input avnbol being scanned by Ii. If Ii successfully reaches $. then 1k? lust -- have nade the switch just at the loment when li is on position x?. ror if It baa not nade the switch by then. the x. count will just have becone sero. end the next love will cause an abort. On the other hand. if 1k' sakes the switch with Ii. on sole position p < x?. tl?en it takes n+l-p ? 5+l?xi : further loves to reach $. and there would have been an attalpt to decremen& the y1 count below zero. causing an abort. Thus if I successfully reaches $. then C1 and C2 vill end up containing xi and respectively. the counters originally containing x? and y? will becoac epty. and N' will have obtained the input syebol currently under 1k? in the siaulation. Furthemore. there is always a correct guess of the switching position for this to happen. 1k' will then relabel the Counters5 and continue to pick up the synbols under the renainins heads. After all k input synbola have.b?en picked up. 1k' will still have the pairs of position pointers (x?.y?) in 2k counters. with the relsining tvo counters empty. Now 1k' will choose a transition of 1k to perform: this Involves. besides changing the state of the sinulated finite control. updating the counts XiS ?? to reflect the lovelent of N? 1k' Is now ready to sinulate the next love of fl. This goes on until 1k enters a final state. Clearly 1k' is equivalent to 1k by the argulents clrendy ss gLven. 0 The asia technique can be used to shou Cnrp?1.ry L.L An arbitrary o+ultibsad ?CM Is effectively equivalent to a single-bead PC". cl 1.? The class 0 ECH languages is closed under coccatoestion. ProoFt Let Hi and H2 be a k1-PcH and a k2-PcH respectively. Vs shall construct a 3-head (k1+k2)-Pcn M' to accept L(w1)L(M2). One bead. naned 1. is used as a read head for the ei.ulations; another head, nased I. is used to separate the input tape into L(N1) end L(M2) segnents. The renaining bead A is used as an auxiliary head. On any input. N' starts by sendins S out to a guessed separating position. This position is then the 5virtual" position for the $ 0 the L(N1) ae5uent. Vith a and A on e. H' atarte ainuisting Nj with k1 0 the counters. using a as the read head. Every tise I is noved risht. K? will check to see if it has noved onto the position of 5. This is achieved by sinultaneously caving a and 5 towards ? and A away fron e. and seeiq if a and 5 reach d at the sane nonent. a and 5 are then restored to their original positions by reversing the nations of all 3 beads until A reaches ? agsin. If a and 5 are on the sane position then NO uses $ as the input synbol for the sinulation of N?; otherwise it will use the real syubol under a. This goes on until Nj enters a final state and M0 guesses that its counters are enpty. NO will then cove a to the position of 5 using A. nove 5 one position to the left. and sinulate on the right seccent of the input with the reasining k2 counters. checking for coincidence of a and 5 as before to eake sure that the left enduarker ? First of all. N' baa to deterii? the syibol under each bead of M. Let the extra countara be C1 end C25 both epty. Consider H?. Startles vith Its true head 1k on ?. 1k' viii love 1k to the risbt until it reaches o+. At the ease ties ?? decreients 11 and increments C1 until at seme point, K5 arbitrarily switches to decrementing Yj and incrementina C2 instead. Vben it lakes the switch. 1k' also stores in its finite control the input avnbol being scanned by Ii. If Ii successfully reaches $. then 1k? lust -- have nade the switch just at the loment when li is on position x?. ror if It baa not nade the switch by then. the x. count will just have becone sero. end the next love will cause an abort. On the other hand. if 1k' sakes the switch with Ii. on sole position p < x?. tl?en it takes n+l-p ? 5+l?xi : further loves to reach $. and there would have been an attalpt to decremen& the y1 count below zero. causing an abort. Thus if I successfully reaches $. then C1 and C2 vill end up containing xi and respectively. the counters originally containing x? and y? will becoac epty. and N' will have obtained the input syebol currently under 1k? in the siaulation. Furthemore. there is always a correct guess of the switching position for this to happen. 1k' will then relabel the Counters5 and continue to pick up the synbols under the renainins heads. After all k input synbola have.b?en picked up. 1k' will still have the pairs of position pointers (x?.y?) in 2k counters. with the relsining tvo counters empty. Now 1k' will choose a transition of 1k to perform: this Involves. besides changing the state of the sinulated finite control. updating the counts XiS ?? to reflect the lovelent of N? 1k' Is now ready to sinulate the next love of fl. This goes on until 1k enters a final state. Clearly 1k' is equivalent to 1k by the argulents clrendy ss gLven. 0 The asia technique can be used to shou Cnrp?1.ry L.L An arbitrary o+ultibsad ?CM Is effectively equivalent to a single-bead PC". cl 1.? The class 0 ECH languages is closed under coccatoestion. ProoFt Let Hi and H2 be a k1-PcH and a k2-PcH respectively. Vs shall construct a 3-head (k1+k2)-Pcn M' to accept L(w1)L(M2). One bead. naned 1. is used as a read head for the ei.ulations; another head, nased I. is used to separate the input tape into L(N1) end L(M2) segnents. The renaining bead A is used as an auxiliary head. On any input. N' starts by sendins S out to a guessed separating position. This position is then the 5virtual" position for the $ 0 the L(N1) ae5uent. Vith a and A on e. H' atarte ainuisting Nj with k1 0 the counters. using a as the read head. Every tise I is noved risht. K? will check to see if it has noved onto the position of 5. This is achieved by sinultaneously caving a and 5 towards ? and A away fron e. and seeiq if a and 5 reach d at the sane nonent. a and 5 are then restored to their original positions by reversing the nations of all 3 beads until A reaches ? agsin. If a and 5 are on the sane position then NO uses $ as the input synbol for the sinulation of N?; otherwise it will use the real syubol under a. This goes on until Nj enters a final state and M0 guesses that its counters are enpty. NO will then cove a to the position of 5 using A. nove 5 one position to the left. and sinulate on the right seccent of the input with the reasining k2 counters. checking for coincidence of a and 5 as before to eake sure that the left enduarker ? First of all. N' baa to deterii? the syibol under each bead of M. Let the extra countara be C1 end C25 both epty. Consider H?. Startles vith Its true head 1k on ?. 1k' viii love 1k to the risbt until it reaches o+. At the ease ties ?? decreients 11 and increments C1 until at seme point, K5 arbitrarily switches to decrementing Yj and incrementina C2 instead. Vben it lakes the switch. 1k' also stores in its finite control the input avnbol being scanned by Ii. If Ii successfully reaches $. then 1k? lust -- have nade the switch just at the loment when li is on position x?. ror if It baa not nade the switch by then. the x. count will just have becone sero. end the next love will cause an abort. On the other hand. if 1k' sakes the switch with Ii. on sole position p < x?. tl?en it takes n+l-p ? 5+l?xi : further loves to reach $. and there would have been an attalpt to decremen& the y1 count below zero. causing an abort. Thus if I successfully reaches $. then C1 and C2 vill end up containing xi and respectively. the counters originally containing x? and y? will becoac epty. and N' will have obtained the input syebol currently under 1k? in the siaulation. Furthemore. there is always a correct guess of the switching position for this to happen. 1k' will then relabel the Counters5 and continue to pick up the synbols under the renainins heads. After all k input synbola have.b?en picked up. 1k' will still have the pairs of position pointers (x?.y?) in 2k counters. with the relsining tvo counters empty. Now 1k' will choose a transition of 1k to perform: this Involves. besides changing the state of the sinulated finite control. updating the counts XiS ?? to reflect the lovelent of N? 1k' Is now ready to sinulate the next love of fl. This goes on until 1k enters a final state. Clearly 1k' is equivalent to 1k by the argulents clrendy ss gLven. 0 The asia technique can be used to shou Cnrp?1.ry L.L An arbitrary o+ultibsad ?CM Is effectively equivalent to a single-bead PC". cl 1.? The class 0 ECH languages is closed under coccatoestion. ProoFt Let Hi and H2 be a k1-PcH and a k2-PcH respectively. Vs shall construct a 3-head (k1+k2)-Pcn M' to accept L(w1)L(M2). One bead. naned 1. is used as a read head for the ei.ulations; another head, nased I. is used to separate the input tape into L(N1) end L(M2) segnents. The renaining bead A is used as an auxiliary head. On any input. N' starts by sendins S out to a guessed separating position. This position is then the 5virtual" position for the $ 0 the L(N1) ae5uent. Vith a and A on e. H' atarte ainuisting Nj with k1 0 the counters. using a as the read head. Every tise I is noved risht. K? will check to see if it has noved onto the position of 5. This is achieved by sinultaneously caving a and 5 towards ? and A away fron e. and seeiq if a and 5 reach d at the sane nonent. a and 5 are then restored to their original positions by reversing the nations of all 3 beads until A reaches ? agsin. If a and 5 are on the sane position then NO uses $ as the input synbol for the sinulation of N?; otherwise it will use the real syubol under a. This goes on until Nj enters a final state and M0 guesses that its counters are enpty. NO will then cove a to the position of 5 using A. nove 5 one position to the left. and sinulate on the right seccent of the input with the reasining k2 counters. checking for coincidence of a and 5 as before to eake sure that the left enduarker ? a. La silulated correctly. M' can choose to bait La an accepting state ehenever M2 enters a final state. It La 5557 to argue that ?` accepts L(M1)L(M2). The deaLred result then follows fron Corollary 7.1. U Finally. we renark that fLnite reversal-bounded rCll'a are .quivalent to BS)('s. 4. ntita? cn?nr.r .eb"?.a iiLh "n'?? revpr..1 bp.,nA. As renarked La the Letroduction to this chapter. 1-way Cn'a wLth fiuLte reversal bounds have been the subject 0 nuch research. In Baker and Book (l97?1. thcy were considered as a special class of i-way reversal-bounded nultipuabdown machines. Ibarra (19781 and Gurari and Ibarra (19801 investigated the aolvabilitT and couplexity of their decision problena. whereas Letteux (19771 treated thee as acceptors of a fanily 0 laneusges that is closed under pernutation. Finally. they were shown equivalent to?l-way blind counter machines i? Creibach (1978c1 and studied in the guise of I-way ainple nultihead finite automata in Ibarra n AL (19761 and inous L AL (19791. As in the case of 2-way C?1's with inite reversal bounds. it suffices to consider i-way Cl's whose counters are restricted to a single reversal. Vs shall use k-?SM. )IS?I. k-flSM and DSfl with the prefix el-wayn to denote such machines. cn--Hp1P?1'?v ? We begin with the tins conpiezity 0 I-way NSM'a' Ihawa L (Baker and Book (19741) Let M be a I-way )ISL Then there is a constant 4 such thet M accepts in tins dn for input of length a. z:neL: By Lemme 2.1 vitb 1(n) I 1. 0 course in this special case the proof of the leema reduces to the original proof of Baker and Book (l?74?. 0 Let ? a finite alphabet. and let ? and $ be special left and right endiarters not in Z. For k ? 2. a lesy k-head finite automaton over 1 is said to be limni. if only one head. called the rpsp'n1 hu?. can distinguish emong the symbols of 5u(?.$). vhereaa tbe remaining k-l heads. called the ?ounting hP?d1. can only tell vhetber a symbol is from 1. iei or 1$). Such automata vera studied in Ibarra &L sL (l?76? and Inouc AL li El979?. They turn out to be equivalent to 1-bay LSH's. Thepre- ? Let k be any positive integer. gvery lesy simple k-hesd MIA is effectively equivalent to a 1-vay k-WSN. Conversely. every lesy k-NSM is effectively equivalent to a 1-vay simple (2k+l)-head MIA. lence 1-vay simple multibead IlFA's snd I-way ISM's are effectively equivalent. Let M be a 1-way simple k-head NIA vith reading head II end counting heads 112. ??? 11k ?efins a I-way k-XSM "1 bith counters C1. . o+. ck as follova. On any input v. first guess lv1+1 in each of C1. ??. ?. Then start aimuleting M. using the input head as Ml and C2. ??. as 12? At the same time. use C1 to verify that the guess of lvi?l is correct. Thus for each i M? decrements C? for every sove of Mi? C1 lust become empty at the same time that the input head reaches $, and for i ? 2 M? is assumed to have reached $ vhen Ci becomes empty. .1. accepts iff the simulation 0 M enters an accepting state vith the true input head on as o+ and all coultera esspty. Clearly N' is equi?alent to M. Conversely let M be a I-way k?NSM vith counters C15 o+... CIL. Thee by Theores 1. there is an integer d such that dn bounds the tisse. hence also the counter sizes5 of a `tinisal accepting computation on input 0 length a. By increasing the finite aessory of H. we can assume that in a aininal accepting conputation on input of length n5 the counters are all bounded by How define the eq!ivalent 1-wey simple (2k+l)-head ??A H' with reading head and counting heads H15 o+5?5 H2k as follows. For each is uses `12i-l and H2j to simulate Ci Whenever Thi increments Cj. H' noves 12i-l and 1Ili to the right by one square and two squares respectively. If I'2i encounters $ in this phase. H' aborts. When N reverses the head on Ci M5 loves H2i.l and Hii to the right simultaneously. until 112i reaches $. Then for each decrement of Cil M' moves H2i?l one square to the right. vith Ci taken to be epty `ihen 112i-I reaches $. The correctness of the simulation can be seen from the fact that on input of length n5 if the iaximum sise of C. is x C n-i then when 11. reaches $. I 2' 2i 12i--HI is at a distance of n-(n-2x)-x I from $. D In the proof of the second part of Theorem 2. if the original tISM is deteriinistic then so is the simulating `sultihend FA. Hence foro?i?rv Z.? Let k be any positive integer. Then every 1-way k-flS11 is equivalent to a I-way siaple (2k+l)-head nFA. 0 Rowever5 in the other direction. the simulating 11511 is nondeterministic even if the original nultihead FA is deterniniatic5 because of the need to guess the length of the input. Hence we do not know whether there is a converse to Corollary 2.1. I, The o+ext result place. a ?ery sesere upper bound --H tha etructural ?ple?ity of I-way )ISM lantusses and highlights their kinship to the regular languages and the context-free languages: ?h.o-em ? (Latteux LIfli). Ibarra (l'781) Let M be a 1-way k-tSM. Than L(M) has a sailinear parikh nap effectively constructible fron M. rniaLs By Theoren 2. it euffices to prove the sane rualt for I-way siuple k--H bead ?FA. In fact a stronger result was proved in Ibarra (l?74): the language accepted by every I-way sinpie k-head rn baa an effectively constructible senilinest Parikh nap. The proof we present here follows Ibarra Elfia). Let M be a I-way ainpie k-head )?FA over an alphabet T. Then we can code a cosputation of fl as a string over a a where Q is the state set of M and o+k. `I2? o+??. are new special synbols. A synbol fron Tu1$i) represents a nova of the reading hesd onto the synbol. Wor i ` 2. .... k. `1. (respectively $j) represents a nove of counting head i `onto a synbol of T (respectively $). The ides is that a colputation string consists of a sequence of blocks each consisting of a synbol q c Q followed by at nost one synbol fron each of the k sets Tu($1). ??2??2?? o+??? ????k?? the sequence being terninated by sons final state Each block represents an operstion which starts in the specified state q. nakes the head notions encoded. and changes into the state qI that follows the block. The validity of such an operation depends on the synbols being scanned by the heads in state q: this infornation can be deduced fron the prefix of the string that ends `jith q using finite nenory. Thus it is clear that a finite autonaton F can accept the set a of strings which are 1locally `0 vali4e. i.e. vbich can be decosposed into individually valid operations. For a local17 valid string to represent a valid coiputatione it is secessary and sufficient to satisfy the further "global validity' criterion tbat it encodes the sane nuaber of loves fbr alL beads. i.e. that it also belongs to I' (v c a : 3 n?(a) : nv(il2) a o+.. : n',(li?) ) act vhers for b e a. n?(b) denotes the nuaber of occurrences of b in v. thus if V is tbe set of valid coaputations then V : afir. Clearly I is a s?ilinesr cociutative language. Since I is regular. it is also aeailinesr. it is then easy to argue that o+a(V) o+a(R)n?a(E) so tbat V is also s.ilinesr (tor exaaple. see Latteux E1977. Leone 2)). Finally L(M) is seilinear because it is a boaoaorphic inage of V. that is effectively constructible is obvious froi the proof of its senilinearity and froa the theory of se.ilinear seta (Ginsburg and Spanier E1964)). El "sing Theoreas I and 3. vs can place very tight upper bounds on the TX tine and taps coiplexities of Ivay NSN languages. Thppr & the class of languages accepted by i-way NS??s (respectively DS?I?s) is a proper subclaas of ntI?IZl(nloga). INSPACL2Elogn). lutIMl2En) and the class of linear tias-bounded l?vay I)? languages (respectively it1KL1(nloga). laspACl2Elogn). lfltlNI2En) and the class of linear tine- bounded I-way 1CM languages). The inclusions follov fros tbeorea I? in the case of the linear tias bounds for tbe 2-tape TX siaulations we also use the observation of Fischer. Meyer and sosenberg (IgOS. theorea ,.I) that a increasuts of 1 IL to an initially o+pty counter can be slaulated in binary naiq on tile or solo constant c. The strictness of tbe inclusion. is vitusesed by the non?snailinear set L2 a ( a21 a n ? 0 ). 0 cn?11iry &.1 The class of languages accepted by A-way Isil's is a proper aubclass of ?. 0 This corollary also follows fros Thenre ? Let M ba a l?vay k-?ISM. Then L(H) is accepted by an 03(k.l) tins-bounded I-way A-tape DTh. Pronfa ly Theoreu I and Theore 3.1 due to Creibach (lIl5bi. 0 slagaLfl properries )Iext we enunerate the known closure properties 0 the classes 0 I way ?ISM and flSM languages. Le? L (Baker and Book ElI74?. Latteur Elfl7l. Ibarra (l?7B?, lnoue L Al (I979?) The class of I-way `IBM languages is closed under intersection and union but not coepleentation. The class of I-way D?t languages is closed under intarsaction. union and coiplenentation. Proofa First 0 all. i a DSH vith q states does not halt then it lust perfori q consecutive stationary operations without decreenting any counter or increnenting an epty counter. Since this condition can bs detected with additional finite nelory. we can asause that a DS)I always halt with its input hcad on the right endoarker. This iniediately yields the closure 0 the I-way DSM languages under conplenentation. The closure 0 both classes under intersection follows fron Ibarra's parallel `2 eachine constrection (ace Theoren 2.10) vith appropriate choices of final etaten: ninilarly for union in the detereinistic case uniog the above observation. nnion in the nondetereinintic case in trivial. Finally r1 but not L1 in acceptable by none 1-vay NSM vhere L1 n ( S v t (O.l)+ ? (Corollary 2.9.1). 0 Lost Z (Baker and Book (l97?). Latteux E1977). Inouc AL AL (l97fl) The clan. of 1-vay NSH lantuases in cloned under concatenation. hoo+oeorphisu and inverse hononorphino+. 0 I The clean of 1-vay DSM lannuases is cloned under inverne honoeorphisn hut not hoeonorphin1. Proof: Closure uoder inverse honoiorphisa folloyn by the etnodard argunent. Let t n ( u01vAr021 S u.v.V.X a (a.b) . lvi n lvi. a (a'.b'1. ?? ? and let h be the "prisa-erasing' hoeoeorphism. Then ? ie?recoo+ninable by a 1-vay l-DSM. but if h(?) in recognizable by a 1-vay DSM then no in L1. a contradiction. 0 s (Baker and Book CiglAl. lnoue AL at ?l979)) The dense. of 1-vay lISM and 1-vay DSM languages are both not cloned under Kienne *. Let L4 n ( snbn : n ? 0 1. Then L4 is acceptable by a 1-vay l-DS?. but Baker sud Book Ei97?J ehoved that if L4 :5 recognizable by a I-way NSfl then no is every r.e. set. a contradiction to Theor? 1. The argunent unes the facts that (I) every r.e. net is the hoioeorphlc image of the net of valid `3 coIputations .f a CM. and (2) such sets of valid coeputations can ha constructed fre tbe re0?lar sets and L: usins inwerse boaoaorphisa and intersection in conjunction with Leinas I and 2. 0 1 (Inous AL AL El?79)) The class 0 1-way 115K languages a closed under reversal. ftnflL: Use Ibarra's reverse sinulator construction (see theore 2.10). O umma L the class of I-way flSM languages 5 not closed under resersal. ProoF: Let L? 1 ( 0t?0t,0tI???40ta : a ? 0. t. t1e ??. t1 ? 0 ). a then L5 is recognizable by a I-way l-DSM. Suppose L? La ale recognizable by sons I-way DSM M. flow LIagine running M on the infinite tape t t t 0 ? ? for sons sufficiently large t. Clearly since M accepts arbitrarily long finite prefixes of this tape it will keep aoving its input bead to tbe right. After so's finite initial segient has been scanned. the counters will have settled down. that is. they will either never change again. or keep increneing. no natter how long we continue running N on the intinite tape. tben within each segment of O?s. the states assu.ed by H tom a periodic sequence. and we can choose two sesnents which exhibit the sane periodic behaviour on a subsegnent O?. Kow we do a 1transfer5 operation to get v2 fron `Il as follows: t t t w1 : 0t? ..?O 1. .1010 v2 : 0?1..4O???1 o+.1O?+?SO?. `a Since M accepts v1. and M reaches the right endiarker I with the sane coafiguration after scanning vl as after scanning v2? M? accepts v2 also. a contradiction. (I ?--H 1 Let M be a l?i'ay lISM. Then p(L()i)) La acceptable by a 1-way flSM. nence the clasaea 0 I-way )IS? and I-way flS)( languages are both closed under persutstion. Let the input alphabet 0 I be T a ?5I?????5t? By Theoree 3. La a s.ilinear set and hence definable by a formula in Presburger aritheetic. By eliniUtion of quantifiers (see. for exaiple. Inderton (1972. Theoren' 32?J). vs can effectively construct a quantifmr-free extended Presburger formula $(x??????xt) with variables xl. ..?. x?. such that a ( (n1.....nt) : o+(n1.....nt) is true 1. Then p(t(M)) a (vcTC : o+(nv(a1).???snw(at)) is true ). Mow an atenic extended Preaburger formula is of one of the forms (I) b1y1 o+ o+ bryr cc1z1 + o+..+c5z5 (2) b1y1o+ o+ b?r nc1:1 + + c5Z5 (nod.) for positive integers b1. o+??? bri c1. .... c5. and a. It is easy to see hov a Ivay DSM can verify these atoaic formulae for values of y1. o+... ??s :1. o+... stored in res counters. Since o+ is a boolean conhination of such atonic formulae. a I-way k-DSfl M' with sufficiently large k can accept p(L(M)) as follows. I' scans each input v. storing sufficiently asny copies of nv(aI)? o+... nv(st) on the counters. At the end of the `s input? )(? coeputes the truth value of each atosaic foraulee and hence of o+. for s',(a1). .... ??5t?? and accepts or rejects v accordingly. The closure 0 the nondetereinistic class under persutation vas obtai?d by Latteux El977?. U L (Baker and Book (1fl4). latteux (Ifli). Ibarra Elfil). Inouc L AL Elfil)) The closure properties 0 the classes 0 1-vay flSX and 1-vay DSM languages are as followas asK DSK intersection T union T T :oaplenent I T hononorphisn T I inverse hoaoaorphisu T T concatenation T I Ileene t I I reversal T I pernutation T 0 CL As can be seen in the proof of Theores 6. there ar? occasions vhen one wishes to ahow that certain languages are lot recogeisable hy any 1--H `F5Y 15K. A counting argunent was u.ed in the case of L1. whereas a nore aL boc argunent involving recursiveness. counter nscbines and language operations was used for L:. these argunents are not as generally applicable as such techniques as the pulping lenas for the regular languages and the uvwxy theorel for the context-free languages. While there does not sees to be a puiping lesma-for I-way ISM languages. one can devise a no?eiborship proof technique that has the sale algebraic flavour. using closure under intersection and sesilinearity. We illustrate t))is technique with a a1np1e exeeple. Consider L6 I ( (0fl1)U ? ?? ? ? `6 Assesses for centradicti..5 that it is recosnizable by so.. i-say `ISM. It La clear that 17 a ( 0n10t1155510tn.i1 a u ? 0. tie 555. t?1 ? 0 o+) La recognizable by a i-say i-DSH. nence L6nL7 is ala. recognizable by a i-say NSM. But L6n? a ( (0D1)fl a n ? 0 ) vith ?sri?h sap i (n25n) a a ? 0 ). which La obviously not sessilinear. contrary to Theorei 3. flence L6 La not a i-way aaSM language. T'.e'?'i?on nrnh1p?. Like finite autoasta and puebdown autonata. I-way ?ISMSa and i-way BsN?s have aany acivable decisLon probleas: Theprc L (Ibarra AL AL (1976). Ibarra (1978)) The solvabLiity of ,arioua decision probicis for i-way NSM?a and l?vsy DSMea are aa follows: 0 NSM eaptLness y finitenesa y containient a: equivalence a: univeree a: diajointness T nsa: T T T v Prnpf: The?noaitive results follow froe?Theoreas 3 and 6. The negative results follow by the sane arguments as for PnA's. 0 More recently. Curari and Ibarra (1980) studied the couplexity of sole of the solvabie decision probicia. By a proof sisiler to the one we used for Leans 1.1. they eetablia?ed Lp?s ? (Curari and Ibarra (19W. Leans 2)) There is a constant c such that for any I-way k-HS? N with a transition rules. L(ll) is noneapty iff M accepts a-a input within ties (ts)ck. 0 Ising this rnult. for any fixed k. they showed be', to construct a 2-way logapace uflt M' that recognixes the encodings cf those A-way b?MSM's which accept nonempty sets. For any legitinte encoding of see I-way usu mi written on its input tape. mi' guesses an input v to mi and simulates mi on v. using the work tape to store a pointer to the state of the simulation as veil as the counters in binary. logarit)nic apace cm the work tape suffices because of Lemna a. nut every 2-way logapace WTh is equivalent to some polynomial time-bounded DTh. Hence: rhpprpm L (Gurari and Ibarra C1980)) Let k be any fixed positive integer. Then the emptiness and diajointoesa problems for I-way k-NSmi'a as veil as the containnent. equivalence and universe problems for I-way b-flSmi's are decidable in polynonial time. 0 On the other hand. if one allows the nuaber of counters to vary. then by a reduction from CIfF-SAT using a technique of Galil (lfl6). it was shown that ?hepr? 1 (Gurari and Ibarra ElSBo. Theore 3?) The noneeptiness problee for I-way nSmi's is mi?-bard. ? asLLtnl ndeE? flnLinn. Finally. we consider miscellaneous models related to the i-way MSmi's and I-way DSfl'a. Using his parallel sachine and reverse sisulator constructions. Ibarra showed that Thporcm It (Ibarra (19701) Let mi be a 2-way k-LSmi for which there is a positive Integer m such that in any computation. mi reverses its input head at most u Limos. Thcn mi has an effectively constructible equivalent I--Hway ?k.l)(m+l)-NSK. `s See the proof of Theore :.io. 0 This simulation iccreaaes the counter requiranents by a factor equal to the m?ber of input passes elininated. fly a different simulation that accepts by searching for a valid coaputation. ye can construct an equivalent 1-vay aachine that only double. the counter requireents no aatter vbat a is: xL? IL Let I be as in Theore 10. Then I has an effectively constructible equivalent 1?vay 2k-lISI. We can construct coaputation strings for I as in the proof of Theorem 3. Zn this case. the string really encodes an (m+l)-rov array. each roy representing the computation that takes place during one of the 5+1 passes of the input. instead of the counting bead movenents. ve nov encode increments and decrements to the counters. The toys are "padded? so that the operations that take place on the sane input square in different passes are aligned vertically. Local validity is defined and verified as before. vbereas global validity nov refers to the equality of the total increment to the total decrenent for each counter and is checked vith the aid of 2k counters. Hence a simulator I? vith 2k counters can accept an input v in onc pass by guessing a conputation string. checking that it is valid. and matching its encoded input against v. 0 it is easy to .odify the above argument to establish the same result for a more general class of machines. nanely 2-vay HSM'a vhose input head can only cross the boundary betysen any pair of adjacent symbols on the input 11 tape at lost I tiles for sole positive integer I. This stronger result was also obtained independently by Curari and Ibarra Ll9SO?. ge could viev 115)115 as auglentations of IlFA1s with I-reversal counters. Sililer augientations can be eade to other classes of autonsta. Thus Ibarra E1978) shoved that ?flA's augiented with I-reversal counters accept only senilinear languages and hence have decidable siptiness and finiteness probleas1 using the sale type of valid conputation arguments as in Theoren II. In fact. the sale arguments can be generalised to shov that for many classes C of 5veakn I-way nondeterministic automate. the corresponding classes C' of the sees autonsta augeented with I-reversal counters have the folloving properties: (I) For any M' in C' with input alphabet Z. one can effectively fied an alphabet A. a deterninistic eachine M in C vith input alphabet A. a seailinesr co-utative language 5 over A and a hoionorphisn ha such that (2) The class of languages accepted by nachines in C' is the smallest class that (a) contains the class of languages accepted by the (deteriiuistic) sachines in C and (b) is closed under homomorphisa and intersection with seailinesr coamutati?e languages. (3) Suppose the machines in C accept only languages with effectively constructible seiilinear Parikh lapS. Then so do the machines in C11 and cl has decidable emptiness and finiteness problems. loo (4) The clas. of languages accepted by eachines in C. is closed under persutation. r.?tic? that if Cl) hol?.. then (3) follows imiediately. and (2) will follow provided we also have closure under bomomorphism and intersection vith scnilinear commutative languages for the augmented class. However. these closure properties are obvious for nost sutomata with I-way I-head input: nondeterminism suffices for honomorpbism. whereas membership in a semilinear connutative language can be checked with extra counters as in Lenna 7. rurthermore. for such automats. (4) is trivial since the augmented automaton can simulate the original machine on a guessed input. vhose composition it records in the counters. If the guessed input is accepted. the simulator accepts the true input if it has the same conposition. Thus for automate with 1-way I-head input. it is only necessary to verify (I). This 5augmentation scheme" gives an abstract characterization of the power of I-reversal counters. It can be verified easily for ? : the class of PflA?s. As an illustration. we verify it for C?= the class.of I-way 2--Htape Hfli's with finite bounds on work tape head reversals: ? The class of i-way 2-tape finite reversal-bounded HTh'. obeys the au:centation scheme above. Hence the augmented machines accept only languages with effectively constructible semilinear Parikh maps. and have decidable nnptiness and finiteness problems. Prpp?: fly the preceding observation.. we only need to prove (I). We first define valid computations for the augmented nachines. Let H? be a I-way 101 2-tape Imi with a botsnd of I On work tape bud rewersala. ausieted with k I-reversal counters. As in the proof 0 Theore 11. a ?putation string' encodes an (s+l)-row array. each row representing the computation that takea place in one of the?a+l passes over the work tape. `adding La done to align the operations that take place on the see work tape cell in different pasHe. whereas input head novenents and counter increnents and decrenents are encoded like the head novenenta in the proof- of Theorem 3. Thus the input strema is encoded in the computation atring ii- a 5winding' pattern. A. before. for such an array we can check local validity with finite nenory. The aachine M is constructed to accept locally valid computations that have been `unwound5 into a linear chronological aequence. It does ao by making one pass over its input and reconatructing the array on its work tape. Thus M can be determiniatic. and need only make a reversals on ita work tape. It is easy to define a senilinear comnutative language S to select those linear sequences that encode a total increment equal to the total decreent for each counter. Then L(N') is.a homonorphic image of L(?)nS. The last assertion follows from the fact that the unaugmented machines accept lansuages with effectively constructible seilinear Parikh laps (Creibach E1978s)). D The auLmentation scheme also applies to C 5 the class of L?&?s to yield characteri?ations for the class of Ivay USM languages (which forn a "fixed pojnt1I under the augnentation). flowever. since the semilinear connutative languages are exactly the pernutations of the regular sets. and the class of I-way NS? lsn?uages is closed under intersection and pcrnutation as well as homonorphisn. we obtain 102 Zhcnua ? Let M be a l?ay ?SM. Then there are effectively constructible regular sets a and S and hososorphisa h sucb that L(M) I b(snp(S)). lance the class 0 l?vay flSN languages La the sealleat class 0 languages tbat contains the regular sets and is closed under perautations intersection and honosorphisa. 0 Sisilar characterirationa can be obtained using the sa.e argussenta. U (Ba?er and look Elfl4?) The claaa of 1-vay MIM languages La the sealleat clean of languages that contains L4 e ( a?b? : n ? 0 ) and La closed under honoicrphisn. inverne hoionorphisus intereectioc vith regular sets and intersection. 0 Thpprp ? (Latteuz Cl977?) The class 0 1-vay XSM lansuages La the seallest class of languages that contains v E (a.b) : n?(a) n?(b) 1 and is closed under hononorphisi. inverse hosoaorphiai. interaectioa vith regular sets 4nd intersection. Alternatively it can be characteri:ed as the s?llest class of languages that contains the seuilinear conautative languages and is closed under boaoiorphisu. inverse boscnorphiau. intersection vith regular sets and periutation. 0 Bovever. these char?cterizationa do not seens to generaLise to acheisa sL'ilar to the one Va have obtaine?. Vs conclude this section vith a brief sention of l-?ay blind CM'S (IcK's) and partially blind Ok's (POk's). Creibach (IflOc) shoved that 1-vay Isli's are equivalent to l?ay lCll's. This can be proved as in 103 the 2-way case (Theoress 3.5). She also showed that neither uodel loses any coaputing power when restricted to operate in linear tile or La p.tpa?-pil?l?p? i.e. in such a vay that the input head loves at least once every q operations for Sole constant q. and that each La strictly weaker than the I-way quasirealtine PCM aodel. It La not known whether 1-way PCM?s accept only recursive sets. and this question was shown to be related to the solvability of the reachability problel for Vector addition systens. We suio+ari:e the properties of i-way PC)j'e. Frol Creibach El978c? we see that unlike I-way flSM?s. they can accept nonsemilinear languages. 5.5. L5 ( 0n?0l s u. a ? 0..? 2n ? On the other hand. we can show that they also share lany coason properties with I-way NSM'a. Thus trivialLy the class of languages they accept is closed under intersection. union. hoaoaorphisu. inverse hoaonorphisa and concatenation. Closure under pereutation can be shown by the 5515 argunent as for (A) of the augnentation scheas. Finally. by Ibarra?a constructions vs obtain closure under reversal and equivalence to 2-way PCN's with finite bounds on input head reversals. 5 ? pnn1icst?pn ? nrp?r? schp?eg We now consider an application of FDA's augnented with I-reversal counters. abbreviated `tPSH's (DPSM?s if deterainistic). to the theory of wwj pchp?ei For coupleteneas. we sive a brief review of the relevant notions of this theory. Proofs of standard results nentiones ii this review or used .iu the subsequent developaent can be found La Creibach El975a?. A progras scheas is an abstract progre in the sale way that a 104 sentence in a language of first-order predicate logic La an abstract sathematicel assertion. Ilassely. they boti contain ..n?nrarnre?ea symbols. and hence can assume different meanings depending on the meanings assigned to these symbols. In the case of program schemes. this abstraction allows us to study the properties of control structures in programming independent of particular domains in which actual conputations take place. The underlying langusge of a scheme consists of the following synhols: Cl) fini:ely many v.?s?1Ps. o+??? xx. (2) finitely many fnns??n??. c1. o+... c1. (i1) (i1) (3) finitely many Functon i.??.rs? ? o+ .... . and (i1) (A) finitely many nr?die?te lerrers? Q1 ? o+??? Vhere no confusion will arise. we shall simply say f'icerlnna and prea'r.tPe. The auperacripta on the functions and predicates indicate their sr?t1'ps L.e. the numbers of arguments to which they are applied. Predicates are allowed to have any nonnegative CritiCs but functions must have positive arities. since zeroary functions have already been introduced as constants. for simplicity. arity superacripte will be omitted in the sequel since they can be determined from the context. Terr?s and s?pr?l'c Fn?..1pp are constructed from the above symbols just as in first-order predicate logic. They in turn are used to forn the basic instructions of the schemes: the s?si?nr?en? and the ?. It turns out that for the study df aba?ract control structures. it nakes no difference if we restrict ourselves to very simple terms and atomic formulae. Thus assuming that each instruction in the sc!:eme has a unique 105 1haL denoted L. a assi??emt is 0 tbe fon Li I ? vhere I La a variable and t La a term which is a constant. a variable. or a function applied to variables. vhueas a test is 0 tbe form L: Q(y1.? o+`?n? L1.L2 where Q is an n-ary predicate. y1. o+... ?n are not necessarily distLact variables. and L1 and L2 are the labels 0 the li? and AAl?--HmLa ?f the test. Notice that a teat with L1 a L2 ia really a _____________ trsnsfr to L1. If L1 and L2 are diatiuct. we say the test is a hr?nebin liiL. A pro*ram icbp?e La then einply a liat of aasignnents and tests. ended by a unique labelled HALT instruction. We shall assume that all variables are used' for input. intermediate computations. ad th output. We shall also assume that the i instruction in a program scheme has the nuneric label i. so we can sinply identify the ith instruction with the integer i. A program scheme becomes a nrp?rnm when the underlying language is given an i'nrprnr.tsripn as in first-order predicate logic. Specifically. an interpretation J consists of a noneapty domain over which the wariables may range. and an assignment 0 5 member c? of to each constant c. a function f?: (nJ)fl ? to each u-ary function letter . and a function qJ? (tJ)n ? (tn&?.li1u) to each m-ary predicate letter.Q. The resulting program is denoted (P.J). rach assignment of values in to the variables is called a ? of the program (P.J). Mathematically. this is a function mapping the variables into nJ If 0 is sucb am assignment. then 0(x) denotes the value assigned to the variable I. As soon as iniLial or inaLLt values are assigned to the variables. a lO? coeputatioc 0 the progra (P5J) can proceed in the obvious step-by-step manner. and the usual notions of halting and divergence apply. In case the coaputation baits. the final values contained in the variables are ta?en to be the n?.rp?.r of the progra for the given input. In the theory 0 prograss scheaes. we are interested in the varying behaviour of progreas resulting froi varying interpretations of the sale schesse or schenes. Thus we consider schematic generalisations 0 properties of concrete prograna. For instance. a scheme is said to e?nvpr5p if it baits for all input under all interpretations. whereas two achenee with the sane underlying language are said to be eg.ss?.less? if under each co-on interpretation. for each co-non input they either both diverge or both halt with the sane output. Alnost all such properties of schenes are undecidable. In fact5 they are undecidable even for schemes whose underlying language consists of cne unary function. one unary predicate. and two variables. Hence even schemes over very snail underlying languages can be exceedingly conpiex. However. there is a large class of schemes. over arbitrarily rich underlying languages. which are nuch nore tractable; these are the LUL schenes. Before we can define a free scheme. we have to introduce a few ucre notions. Let the scheme P be the list of instructions 115 o+??5 I, We shall identify the instruction 1k with the integer ?. Then ? is a a.'fc...or of j if either (I) j is an assigunent5 and k a j+l. or (2) j is a test. and one of its exits is k5 i.e. k is one of the transfer labels of j. A sequence of not necessarily distinct instructions ?1 55Jn of P is a aCl a-an if for t a l? o+... n-l. it+i is a successor of If in addition j1 a j? the sequence to called a mh. i.e. a path is an initial segient. The sequence is rpnlSa.bla if it is an iwtLLna aarn?nep of cone coeputation of P under some interpretation Je i.e. if it is tbs esquence of the first n instructions followed by the program starting fron some initial state. Obviously. every reslizable sequence aust be a path. We eay P is LUL if every path in it ie realisable. The constraint of freeness dreetically reduces the complexity of program schemes For instance. convergence to decidable for free schemes. Unfortunately0 freenese itself is not a decidable property. since the Post Correspondence Problem is reducible to the freeneas problem. flowever. this reduction brea?s down when restricted to schemes with only one unary function (and no functions of higher arities). It was therefore not tnown whether freeness is decidable for such restricted schemes. and the question appeared as an open problem in Creibach E1975a. exercise 3.4?. Mere we show that the answer La affirnative. even if the restricted schemes are endowed with an auxiliary pushdown store as described below. Our proof reduces the freeness problem of such schemes to the emptiness problem of NPSN's. shown decidable by Ibarra El97S? (also see the sugmentation scheme in Section ?). A program scheme ?ugmented with 5 pushdown store is a scheme whose underlyins language contains an additional hidden jta v.ri?hia D and which has two additional types of basic instructions used to nanipulate PS LI PCSh(x) LI 1 ? POP. and 108 vbere x is a variable. icr essphasis. we shall sosetiass refer to the old. mom-stack variables as imp1t var4.hI.. p is bidden because it does not appear explicitly in the scheme and cannot be used to construct terse in the underlying language. Under an interpretation J. a state of the program (P.3) nov includes. besides an asaignnent 0 of values from to the simple variables. an assignment of a finite puabdown list of 3 values from D to p. This List muat be empty for initial states. When a o+PU5U(x)' instruction is executed. the current value of x is added to the top of p. the value of x remains unchanged. tIhen an "x ? POP1' is encountered. the action depends on whether p is empty. If p is empty. the instruction is treated as a "no-op". i.e. the scheme simply passes on to the next instruction. Otherwise the topmost value is removed fron p and stored into x. wiping out the previous content of x. Successors. segments. paths. realirability. and freeness can be defined as for unaurnented schemes. us now describe an alsorithn which decides freeness for the class of schemes augmented with a pushdovn store but restricted to only one unary fuction letter f. From now on. unless othervise specif&'ed. all schemes we consider are asauced to be in this class. We also assume that these schemes contain no constants. since constants behave exactly like variables that are neve? assigned to. For such a scheme P. the algoriths searches for a path p which cannot be an execution sequence for any input under any interpretation. As in the case of most decision problems in schema theory. it suffices to consider only the Uprhrnnd or 1n?ernr.?A?1png Intuitively. a !(crbrand interpretation is one vhoae domain contains exactly one object for each possible ?l?an,? of an object", I" i.e. for each to:. of the underlying language. and Iboso nasigneonts to tbe function letters are such that tbe only functional relations aaoq the objects are those Laplied syntactically by their eases. serially. a Ierbrand interpretation J is an interpretation such that (I) the doesin is the set of all teris. in prefii notation. of the underlying LanguageS (2) the value assigned to the constant c is the tori c itsolfs (3) for each n-ary function letter f. and elesents tl? o+? ta of f (t1. tn) ft1 ???n Thus different Herbrand interpretations of the sacs language can dUfer only in the assignments to the predicate letters. lotico that for a schese P of the type being considered. the donain of a Ierbrand interpretation is the set of strings I : n ? 0. x iso variable of?). For a Uerbrand interpretation J. the uMwL In?r?.I L& of the progras (P.J) is the one which assigns the tori xj to the variable and the eupty list to p. Standard argunents in scheus theory then show that a schene P is not free iff it contains a path which cannot be an execution sequence of P under any Uerbrsnd interpretation J starting froi the cenonical initial state. One last piece of notation will help sicplify our discussion. Suppose p : ?l????T is a path in a scheno P. J is an interpretation of P. and ?oo??o? is a state of the progral (?.J). The fp???b1p o+r.e??t?nn of (P.J) sterting fron (c0.p0Y i? the coiputation along p startin? fron the given state. which obeys the assignment. PUSH and POP instructions in p. but ignores the test instructions. i.o. tates the branches dictated by ? 110 irrespective of the alaigossents to the nredicatea under J. If p ta understood, we use and p1 to denote Lhe value assignments to the simple variables and to p after forcible execution of ii.. it starting fros the canonical initial state under lone )jerbrend interpretation. This notation is unambiguous since clearly it does not latter which particular `ierbrand interpretation is used. Thue li is aimply x and 00(x) p0?is the empty list. whereas oT(x) ia the final value of x after the forcible execution of p has been completed. We are now in a position to define a founp1' to the freeness of a scheme P. This is a path p o+ j1 ?1T for which there are an n-ary predicate letter Q. 2n not necessarily diatinct variablee ?1' o+?" 7a' o+... y??. labela r ? a, r' ? a'. and an integer T', I ?? C T. auch that (1) is the branching test Q(y1.....70) r.s (2) j?. is the branching test ??7i''???'7n'? r'.s' (3) o+??c(y?I) ? 0??7k? for k o+ I. ..., a. i;ote that it ia possible to have 1T a 1T'' Informally. a countegaxeapla is a path vhich. if forcibly executed for the ca?onicsl input under a Herbrand interprettion. will apply the same predicate to the asass 1(erbrand values in two distinct occurrences of branching tests. The following lenana shows that counterexamples indeed possess the property implied by their name ?-? L A scheme P has a counterexs1,ple iff it is not free. Ill If P baa a counterexanpie p. than by definition. tbe last instruction in p has two distinct succeasora r. a. Clearly. p concatenated with r or a is not realizable. Conversely. suppose P is not free. Than it baa a path p which is sat realizable. A proper initial segment of p muat tben be a counteraxeple. as otherwise we can construct a ?erbrand interpretation under wbicb P follows p. 0 The task of our algorithm is then to decide the existence of counterexanpies for the schemes under consideration. Clearly. for a scheme r e Il? o+I?? we can construct a nondeterniniatic machine which racognisas the counterexemples for P froa r where r = (1... .Fi. Such a machine guesses the two distinguished occurrences of branching tests and then verifies that its input p satisfies the counterexeple conditions with these guessed occurrences by computing and comparing the appropriate lierbrand values usini forcible execution of P along p. Now the puabdown store of P can be simulated by a normal pushdown store with a finite alphabet. whereas each variable of P can be simulated by sone finite memory plue a counter since each l1erbrsnd value can be coded as a count n and a variable neme x representing fnx. Thus a PDA augmented by a finite nunber of counters suffices. However. the forcible execution requires nonconstant reversals o\a the counters. and FDA's (even DPDA's) augmented by nonconstant reversal-bounded counters do not have a decidable emptiness problem. Fortunately. it turns out that by extending the technique of hp?bw.r? =bsrt.,tipn used to treat assignment statements in progrem verification (see Greibach E1975a. Chapter S. Section Dl). we can construct an NPSH to accept the reverses 0 the counterexamples. the 1l? decidability of essptinaaa for WPSM's then isaplies the decidability of freenesa for the scbeies under consideration. We reaark that we could have accepted the unreversed counterexaples by guessing. for each argument of the two distinguished tests. a chain of assigccenta in the path that builds up a Herbrand valuc and puts it in the target variable at the appropriate distinguished test; however. this approach is cot as transparent as the deterninistic "backward unravelling' approach that we adopt here. In processing p1 to determine whether p is a counterexsnpls. it is necessary to guess (I) the distinguished branching test besides the final instruction of p. and (2) for each POP instruction. whether it is encountered with p e.pty in the forcible execution of p. The corractness of these guesses is verified datereinistically. and pi is accepted iff correct guesses exist for it. We can separate the nondeterninistic tasks from the detercinistic ones by incorporating the guesses into the input. so that the processor is responsible only for the deterministic verificatlon. With this purpose in mind. we nodify our definitions of segnents. paths and counterexamples. First of all. our alphabet is extended to a : r u ( ? : j is a POP or a test 1. A capped POP is intended to be one executed with epty p and hence equivalent to a "no-op"; it will be called an irnnr?s POP. An uncapped POP is intended to be one executed with nonempty p; it will be called an hnrn?reA POP. A capped test is intcnded to be the distinguished 113 branchins test other tbaa tbe final insiraction Ii a enuirersiaple. The hoaoaorphisu hi ? r* resoves caps fre. capped synbols. A sirtig p o+ S1?? over ie a ac-aL if for t 5 I. o+. tia b(at.1) is a successor of h(st) It is a n.?)' if. in addition. (1) h(s1) 2 1: (2) forcible execution of P alone b(p) vith as initially apty p vill isnors.or honour POP instructions as indicated by p. Ii ii and ?t can then be defined for paths as before. p a cl o+?at is a ?p?nrere?mnnIe if it is a path for which there are an n-ary predicate Qa 2n variables y1. o+??? y5. y!. o+... y0?. labels r. 5. re. ?s with r ? a. ? ?e? and an integer I. c t such that (1) at is the uncepped test r5a (2) at. is the capped test Q(y?.....y01) i05s' (3) cH10(y?s) 2 c?(yk) for k a l? .... a (4) ?t? is the only capped test in p. It is obvious that Lesna I still holds with these 5500 defieitioas. A machine ii which recognizes reverses of counterexaseples ire seenag * a must perfora the following tasks for each input p a at...a1: a (I) Verify that p is a path. (2) Check that at is an uncapped branching test. leember its predicate q and arguments ?i? o+... 7us (3) Chec? that there is exactly one capped test at.. This vust be a branching test with predicate Q. Issember its argusents 7'js o+... (4) Compute <)?1(y?) and oI1L?(y?I) and verify that they are identical. for b 114 I. o+??. 0. Clearly the aoat `Iportant task is the coiputation of ?(y?) end in (4). go shall therefore basin by describing so algoritha for thLs teak. This algoriths is called the Atotl s?s?,tinr.pn ?rp.rne1 abbreviated ?. Let the schene P have a variables xl. 111. x11 a single stack variable o+. and a single unary function letter f. ? vill also have a finite nunber of predicate letters. but these can be left unspecified. The corresponding nsP has the folloving variables: (1) `al' o+??` each of `rhich can hold a string in (2) v1. o+.., v11 each of vhich can hold one of the 5+1 naaes "x15? o+.`. "z o+, "2?. (3) ?. a stack `ahose alphabet is 2(l?111?1) g ??, The synbols in 2(11111121 are called UL .v'ahq?a or amply iaLai A is the i.nor. in??entnr, Vs sball use ells to denote the result of pushing the eleasot a onto the stack S. and act to denote the concatenation of the strings 5 and t. Initially. each holds the enpry string. each Vk holds the nane and ? is eapty. 3Sr then reads its input string1 which lust cone fron . one synbol at a tins. and checks that it is the reverse of a sernent. The detection of a synbol that violates this condition will cause SSP to abort. Otherwise BSP also takes one of the following actions for each synbol. depending on the instruction the synbol represents: (11) Capped or ?capped test. aa3 Pc further action. (B2) Ii ? Ii. For all k such that vk a o+i?S? set vk a The reeaining Vke as veIl a. all and ?. reitia i-basted. ?fl3) xi ? fzj. For all k such that vk a set vk a ad ` ?cf. All other ut? Vk and ? are unchansed. (B4) PUSH(xj). If Z in ?p?y. no further action. If ? baa Aon top. abort. OLhcrviae I baa a set symbol S at tbe top. ?q it. ad for all k in S. act v? a ?xis (15) Isnored xi ? POP. If 1 ha. a set symbol at the top. abort. Otherwise. pushAon 1. (16) Ronoured x? ? POP. Let 5 : ( ? I vk `Ixi'1 ). 5 asy be the sapty set. For all ? in 5. eat Vk a "a5. Push $ on 1. Motice the effect of PUSU ie to pop I and. conversely. the effect of POP is to puah symbols onto I. A etrina ia a?canr.? by IS? if it does not cause IS? to abort. We now describe ad verify the function of IS?. Throughout the following discussion. let p a ?l????? and let pI be the input to IS?. As long as 1SF does not abort. we let uk(t). v?(t) and at denote the value. of u? vk and 1 after proceseing 5T? 5te1 We shall also use the 116 vector notation vbaa it I. unnecessary to refer to Uk' vke %(t)5 v?(t) individually. For exnple. g(t) a (u1(t).....u1(t)). Thus are tbe initial values0 and ?g(O),?(O),?0) are tba final 5 values -. provided p is accepted -- of (?,t,:). For a nonnesative integer d0 (d) denotes the (d+l)at entry from the top of the puabdown Similar notations are employed for the entries of other list pusbdown lists. Informally0 suppose p1is accepted by flSP. Then p is a segment of ?. Tbe entries of :? register the POP instructions in p that do flat remove entries made by PUSH instructions in p in a forcible execution of h(p). We call these the unr?stchpd POP instructions of p. The set symbols on correspond to the unmatched honoured POPs0 wheresa the A entries correspond to the unmatched ignored POPs. (?otice that all ignored POPs are unmstcbed.) Clearly0 among the unmatched POPs0 the honoured ones Bust precede the ignored ones. Hence vill consist of set symbols on top of A's. Such a value of 2 is said to be Adnissibis. For an adnissible 2'. we use 1LL1(2') to denote the pushdown list obtained by Asleting the A's from 2'. We shall also use I?I to denote the length of a pushdovn list ?. Then 2o sives, for any interpretation. a necessary and sufficient condition on a stack PC such that for any assignment 000 forcible execution of h(p) starting from the state (00,p0) will ?qnfn?m La a. i.e will honour or ignore POP instructinns as indicated by p. Homely. p0 Bust be r??ps?1h10 to 2o? which means that (I) lsets(20)l ` p0I and (2) Iaets(20)I Ipol if 2o contains a? For convenience. we eball simply say (2ooPo) are compatible. 117 lutuitively. (1) .eans tbst us lust start vitb aufficiostly lany sntriu in p0 to satisfy the unuatched bonou?ed POPs. and (2) leans rust if tear. are to be ignored POPs, then p0 cannot contain any "excess1 entries. Under any interpretation. if (20.p0) are conpatibie. and forcibis execution of h(p) starting vith the atate (c0,p0) ends in the state then the vaiuea (tL(O).?O),2O) give the reistions between (r0.p0) and The above informaL description wiLL nov be formuLated precissiy and proved in the foiioving 1?as. Again. we need only consider Merbrsnd interpretations. Le?ms 2 As icog 5 55? does not abort. the foLLowing conditions hoLds (1) 2 is adnisasbie. (2) For each k. vk s "21 iff St is in sole set on 2. (3) Any St can be in St lost one set on 2. These conditions can be estabLished by a straigbtforuard induction. They trivisiLy boLd initially. The inductive step is siuply a case aulysis `of 56?. The cruciaL properties of 55? are that it never pushes a A on top of a set synbol (see (BS)) and that once a set 5 containing St is pushed onto 2. vk is set to "2". thereby prohibiting St fron neiberehip in future sets pushed on 2 until 5 ?,as been popps? and Vk reset to sons variabLe name (see (54) and (56)). 0 a I Suppose p : 5l'??5T' and 55? accepts p with final valuss (1L(O).X(O).20) for (`L.X.2). Consider any Herbrand interpretation. and Let p0 be a puebdown List of,iierbrsnd vaLues. (I) If (20.p0) are incompstL'ble. then for any assignnent oO? forcible LIS executica alcoa h(p) starting vith (c0.p0) viii not confori to p. (2) If (r0.p0) are compatible. then for any assignment 005 forcible ezecution along h(p) starting vith (oosoo) viii confora to p end result in ?0t??t? such that for each k I. o+... o+. (i) if v?(O) = then or. abusing notations. 0T?'k? : ?(o)coo(vt(o))I (ii) if ? 20(d) for Cone d ? 0. then uk(o)oP0(d). flotice that Lenma 2 guarantees that (i) and (ii) are autually ezelusive and exhaustive and that the d in (ii) is unique. whereas the assumption of compatibility guarantees that ?0(d) in (ii) is veil-defined. I:nnL: The proof proceeds by induction on the length T. In ?he base case. ? I ? and p is the null string. so flSP accepts right after initialisation of (g.x.2) to ()L(0).X(9).20). Nov is empty. so for any P0. (20.p0) are compatible. Hence (I) is vacuous. and it is trivial to verify (2) ((ii) of (2) is also vacuous). The inductive step proceeds by case analysis of the first instruction a1 cf p. The general strategy in each case is as follows. Since IS? a accepts p . it also accepts ST with final values Vs cam establish the apprbpriste relations between (iL(l)??(l)?2i) and (M(0).x(0).20). by el-Lining the action of flSP for a1. Then to prove (1). assume (20.p0) are incompatible. There are two alternative ceseal l1? (a) Execution 0 b(a1) starting vitit (o+0.p0) does not eonoxs to a1. ii which case (1) is already established. (b) Execution 0 b(a1) starting with (oo.Po) conforis to a1. resulting ii Then we chow that (??.P?) incoapatibla `iplies (31.p1) incompatible. Co that by induction. a nonconfomity arisqs in tue execution of h(a2???aT) starting vith (o1.p1). To prove (2). we must show that execution 0 h(a1) starting with (o0.p0) conforms to a1. resulting in (ol?Pl') such that (Z1.p1) are coepatibla. Then by induction. execution of h(s2 aT) starting with (oi.P?) conorma to a2.. 5T? and the relations (i) and (ii) bold for (o1.p1). ?0T??T?? and Further manipulation then establishec (i) and (ii) for ?Ob??0?? ??T??T?? and We nov carry out the cace analysis of a1. We only do the cases (55) and (56). which involve stack cha?es. (El) PUSR(x?). Ilo nonconfornity ceo arise in the - executini of a1. end the resulting (o1.p1) satisfies 0 1 0 PI o+ 0o(x?)llpo. We consider three subcases depending on S.,bf? (&)t is eupty. Then (iL(O)??(O)??o) I Since and are both epty. (?0.p0) aa wall as (?1.p1) are conpatible. lience (I) holds vacuously. For (2). the conformity assertion and (i) follov issiediately by induction. vbereae (it) is vacuou.ly true since is o+pty. ?fl?22? (A): ?? baa Aon top. This is innossible. as BSP vould bave aborted. S'h?.se (?: baa a ?t 5 on ?op. Then SII?o ? vk(l) if k ? 5 vk(O) 2 ?Xi' if k c 5. Since Isets?Z1)I IseL.(?0)I+1. jp1 : Ip0I+l. and 120 cocteins a A if! contaLne a we see that (20.p0) ste compatible iff (21.p1) are coipatible. Thus (1) (alternative (b)) and the conformity assertion of (2) are establLshed. For ti) of (2). assune vk(O) o+ 1 k c 5. then q 2 ? snd k a So CT(xk) 2 u?(l)0Pi(O) inductLon %(O)?o(xi) substitution 2 ?(O)??(Xq) q 2 If k ? 5. then v?(O) 2 v1L(l) 2Xqfl (It is possible to bave q Again oT?'k? ??(l)Or?(Xq) induction 2 ??(O)?c(Xq) substitution. For (ii) of (2). assu:e k a N0(d). Then ? a Hence 0T?'k? `Lk(l)0P1(d+L) induction I2' a .k(0)cPo(d) substitetten. (sS) 1?nored i? ? POP. `Since flSP does not abort0 contains oniyA5s. Th? a a(1) All1. So I?te(?0)I a Isets(l1)I a0. and vs kcov tbat baa a? If (l0.p0) are incoipatibie. it lust be the case that 1001 ? 0 fleuce a nonconfornity arises innuedietely on executini b(51)e establishing (1) (aiternetive (a)). Next suppose (?0.p0) are conpatibie. Then in fact p0 is empty.' hence execution of h(a1) ia okay. and results in (?1?p1) : As isets(21)l a 0 a 1p11. (l1.P1) are coipatible. so by Lnductioao+ the conformity assertion of (2) holds. as do (i) and. lacuously. (SI) Unnoured xi ? POP. We have. for 5 a I k I v?(l) a 51?ft )? a slili a u(l) vk(O) a u?a if k a 5 a vk(l) otberviss0 There are tvo eubcases0 depending on vhetbsr La epty. Spih?nss (&)s PC is epty. Then (l0.p0) lust be inconpatible. and (I) hoida because the POP could not be honoured (alternative (a))0 `rhereas (2) is vacuous. 123 LLhw (I): 1p0i ? 0. Then the PO? could indeed be honouced. resulting is (o1.Pj) such that 5 p0(0)11p1 01(1k) ? oo(1k) if k 5 i 5 p0(o). Eoy 1p11 ?. Ip0I-1. Isets(Z1)I a Isets(?0)I--Hl. and 11 has a A iff has a So (?1,p1) are coopatible iff (?0,p0) are-coapatible. Thus by induction, (I) (alternative (b)) end the conforsity assertion of (2) bold. rot (i) of (2). suppose vk(O) Then us nust have k 4 5. v?(l) v?O) `.1 o+? and q 5.i. s. q 0t?1k? ? %(l)C0i(Xq) induction 5 ?(O)0Oo(Xq) q 5 i. ror (ii) of (2). suppose k e ?f d `0. then in fact k E 5. v?(i) 5, `o+x?' So or('k) 5 ua(l)?l(Xi) induction uk(c)0P0(O) substitution d 0. %(O)OP0(d) Otbervise d ? 0. so k a z1(d?l). and hence 0T?'k? 5 ?(l)co1(d-l) induction substitution. 5 ut(o)oPo(d) This c?pletes the argunent. 0- In fact vs shall only sake use of Lensa 3 in the special case in I? vbich p0 is the epty list. o+. The converse to Leessa 3 for this special ease. which is also needed t. establish the correctness of our algoriths. will be proved next. We nerely resark that there is also a nore general converse to Lena 3. I---H ? Suppose p o+5T is a seguent of ? such that i. a Herbrsnd interpretstiou. forcible execution of b(p) starting with for see assigonent ?? conforns to p. Then fis? accepts p . with I ??5 where q is the nunber of ignored POPs in p. ProoF: By induction on the length T of p. The base case T 5 0 holds trivially. Nov suppose T ? 0. We again establish the inductive step by a ease snslysis of the first instruction of p. Obviously ?i cannot b? an honoured POP. Hence we have two cases: (1) `i is a test. an assignment. or an ignored POP. Clearly ixecution of h(a1) results in a state and execution of h(a2???sT) starting fross confores to ?2???'T fly induction. BSP accepts 5t? with ? where q' is the nuiber of ignored POPs in ?2? o+5t it is easy to verify. by exeining the action of BSP for ale that fiS? accepts PS with as stated. ??? `I is a PUSH. There are three subcases. aMhwA (&) The entry pushed by `1 is not popped subsequently in 52???5T Then there can be no ignored POPs in 5? 5r as p is never epty. Purtheriore. it is obvious that execution of b(a2 5T? startiq vitb 124 (oos4) also conforis to ?:? o+5t since no bonoured POP uses the entry pushed by a1. Benee by induction. BSP accepts 5T ??2 with 1 Th?n nSP also accepts pa with ? as required. Subesse (1) The entry pushed by ?l ?? removed by a? Again there can be no ignored POPs in p. and since B$P can only abort when its input contains ignored POPI. we see that pt Iust be accepted. Furthermore. notice that the PUSH and POP instructions of p form a balanced psrenthesas structure. with a1 matching a?? lience flSP. in processing pa? will pop. for each PUSH, the set pushed by its matching POP. Rence is empty as desired. Sube,?s1 (? The entry pushed by a1 is removed by a? for sone t C T. un can split 5l"'5T into two parts. 5l"?5t and a ".5 t+1 ?5 each executing correctly iron an empty p. For 51...at. the sane ressoning as in Subcase (fl) shows that it has no ignored POPs. and that its reverse is accepted by flSP with empty final 2. Furthermore. flSP will push a set for St which is not popped untiL a1. By induction. BSP accepts a?'"5t+l with final ? containing ??? where q is the number of ignored POPs in 5t+l'?'5T and hence also the number in p. Clearly. BSP. when stsrted on 5t'?'51 with?a 5 of will perform the sane actions as with empty initial ?. since the set pushed for "shields" the A entries until ?I' Hence SSP accepts pR with 20 5 as required. D BSP can be easily modified to accept the reverses of counterexamples for P. First of all, we imagine that the underlying lenguage of P has. in addition to the "real1 variables Xl? o+??? Xn? fl additional "history" 5 * variables xl? ??s Xne which of course do not sppear explicitly in P. A I,, ISP La constructed for P oser this angu?tnd underlying lagiage. with * t uks vk corresponding to 4 and vith the alphabet 0 ? extended to 2jI. .`.5n.l'....??*1utf?). Code is added to perfore the following additional tasks for input at...alI (Al) Check that at is an uncapped branching test. Abort if it is not; otherwise reuciber its prodicate Q and argulents ?l? o+??? (A2) On seeing the first capped branching test at.. check that it has predicate Q. If not. abort. Otherwise. reasuber ita argunents ??. .5 ??`. and then process the instruction as though it `isre tbe sequence of the following I instructions: t I ?I I I I ?I. n n (A,) Abort if' a second capped tees is encouetered. (A4) If the starting instruction of P is encountered. i.e. if b(a5) 8 I for sons t. the progra stops reading any further input. If it has not encountered a capped test5 or if ? contains a eat syibol. abort. Otherwise. it checks that for each k a l? o+... n5 if 7k is Ilk and is 1?k5 then t ui?(t?l) : u 3k and v (t-I) o+ ik vtik(t?l) 120 It vill bait in an accepting state if all these conditions bold. and in a nonaccepting state otherwise. As usual. the input ?r ?l is accepted iff the progrsa halts La an accepting state after reading a1. Notice that after (A:) baa been for any j. ezecuted. no vk,or v; will contain To see that this progral accepts the reverses of counterexauples. Ye lake use of Leises 2. 3 and ? concerning nsp. If p ?t????t is a counterelsupla. then it is a path. In particular. it is a segient. and aiscution of h(p) under a Merbrand interpretation starting with the 1' canonical initial state (co.?) conforms to p. So by Lonna 4. p1 will be accepted by IS? with a of A's. lience by L?na 2. for all k. a ?? and v*(O) a ???. By definition of counterexauples. (AL) and (A:) will be performed. but not the abort instruction (A3) When o+I is encountered. (Aa) is invoked. Since (A:) ha. been perforsad and has only A's. the abort conditions in (A&) do not arise. Now by definition of counterel-pi55. for each k. if ?? is and vk' is 1?k? `r? have 0li4,?2?k? S But clearly ??(Xjk) : a. c??(x ) s CHt(xC ) T Lk By Leuna 3. ?NT(xik) : u. (0)?U(w(o)) I uL (o)ov (0) and ?(x??) ? Lk Oik k a u5j?(O)OW??(O)s .5 since neither Lk nor 3k La on lenca u?(o) 5 u5j?(O) and vik(O) I a go by (A4). vs knov the prograu accepts p Conversely. suppose the progre accepts p . ThLs clearly st-a that p La an initLal segient and BSP accepts p1 vLth ?? containing only A's. `lance (??.+) are cospatible. so executinn of h(p) starting vith conforas to p. shoving that p La a path. The acceptance of pa by the progre also guarantees the existence of a unique capped branching teat Q(Y?s??.y?') astcbing the uncapped branching test Q(y1s???sy?) of ?. It reaaina to shov that a ??H(y?) for k a ?? .`.. a. If 7k La Xjk and 7k' La XjkS since ob?i(y?') a ??(Xjk) ` d'T?"ik?5 vs need only prove c?li(xa ) a o'l(x ). T But by Lena 3. n'l(xt ) a ut (o)ov' (0) T ?k ?k ?k Ii and r?(xi ) a u (o)cv (0). ? Lx it Co the equality of the Left band sidea La guaranteed by step (A4). Finally. vs argue that the above progre can be `Ipleented as a flPS?. ? La of courae just a norial pushdovn store uitb a finite alphabet. The variables vks va can be ainulatad by finite usacry. `rhereas uk? uke can be ainulated by counters since they hold strings ovar Furthereore, the progras only Lncrenants the counters until step (A&) La reached. Then it aiaultaneously decranents all countera to zero to deternina vbich onee are equal. Clearly. for a acbasse ? vith a variables. 2n I-reversal counters suffice. and Va have proved L For a progre scheae ? witb a variables. a pusbdovn store. a 128 single muir, functiom and any number of predicate.. tre cam effectively construct a DPSM vith 2m i-reversal counters which accepts the empty set iff I is free. Hence freeness is decidable for such schemes. 0 Ve have not estimated the complexity of the above decision procedure in its full generality. Ilowever. we know that for each positive integer b. it runs in polynonial time for the class of unaugmented schemes which have at most k variables and whose predicates have at most k argument pisces. This is because for such a class. the i-way 2k-DSN for each scheme can be constructed in polynomial time. and the emptiness problem for i?way 2k-DSM's is decidable in polynonial time (Theoren 4.8). The construction we gave can be modified to show that the value language of a monadic free augmented scheme with a single output variable is context-free. This is a natural extension of the result that monadic free unaurnented schemes with one output variable have regular value languages (?ee Creibach (l975a. Theorem 3.14)). Also. from our construction it is easy to see that both results generalise naturally to scbemes with more than one output variable: the value languages are acceptable by the corresponding nondeterministic nultitape automate. Chapter ? Pinite `ewersal-Bounded Multitape liaits Ast?ta 0 ?nr,nauer?po In this chapter. we study finite reversal-bounded usaltitape finite autossata. We first show. with the help 0 the results of the prewioms chapter0 that when restricted to unery input tapes. the lansuases (which are now sets of tuples of tapes) accepted are ezactly the unary encodinse of the Presburser relations. This is true whether the eodel is determiniatic or nondeterministic. end even if the model is aucnented with finiLe reversal-bounded counters end either an unrestricted pushdown store or a finite reversal-bounded work tape. or if the heed reversals are restricted to simultaneous rewinds. Methods are 5iven for constructins machines to reconize the unary encodinge of the Presburser relations. with or without nondetersinisi. It will be seen that input head reversals are necessary for the deterministic osodel. but not for the nondeterninistic model. The lest section deals with the classes of determiniatic end nondeterministic nultitape rewind automate with arbitrary input siphabets. In each case. a characterization in terms of the correspondin? I-way machines is aiven. Hierarchies based om the nueber of rewinds are also established. When restricted to unary input tapes. the deterministic hierarchy stands but tiLe nondetereinistic one collapses. 1. flpF.ni?inns snd nnroripn The basic eodel we study in this chapter is the nondeterministic finite reversal-hounded nultitape finite automaton. In this model. the 129 130 epnt tapes are read-ocly. and each is delilited by the lef? and right endearkers ? and S. Furtheriore. there is a finite bound on the nuiber of tiles the input head on any tape can reverse direction in any colputation. We shall be particularly interested in two restrictions of the basic o+odel. nalely the restriction of the input to a unary or single-letter alphabet. and the restriction 0 reversals to zmnli. which are instructions that ajiultaneously reset all beads to the left enduarkera of their respective tapes. We no', establish sone notation for this chspter. The prefix o+`unary? indicates that the input is restricted to a unary alphabet. For a nonnesative integer a. vs use the prefixes "n-revsrsal" and `?revind" to indicate a reversal or revind bound of a. respectively. Wnen we are not concerned with particular rewind bounds. we shsll refer to a o+ultitape FA restricted to rewinds as a r?u1?? su?p?.??n. abbreviated IA. The asanings of NRA and DF& should be obvious. We shall see that allowing nonconatant tounda on the nuaber of rewinds does not increase the pover of an IA. flence an IA will always be finite tewind-bounded. 2. c??.??n r?. rpfnen2shlp n.rv __________ In this section. we show that for each class of finite reversal- bounded unary-input eachines introduced in the previous section. the lan?uages accepted are exactly the unary eocodin:s of the Presburger relations. ?? L If S ? 11k is a Presburger reletion. then the language L a ( (a?1.....a?) s (n15....?)?c a ) is accepted by Cone k-tape DIA. aja fly elinination 0 quantifiers. we know tbat there La an extended quantifier-fras Preshurger formula o+(xlsssssxk) La the vartables xIs o+?ss xk such that 6 I ( (n1s??ssn?) : o+(n1ss??sn?) is true ) (for aisaples ate Enderton tl972. Theoran 32E)). Clearly it suffices to consider an 6 for which the corresponding o+ ia an atosic formula. since the class of k-tape DRA languages ib closed under intersection. unioa and coeplement (nosenbers E1965, 1967)). Such a o+ is cf one of the two forns (I) b0 + b1y1 + .5. + b?y? a c0 + c1a1 + + c0a5 (cod i) (2) b0 + b1y1 + ... +b?y? cc0 +c1z1 +??+c5z5 where t??sSSSsY?) and (:i55555Z?J are diejoint subsets of (x15....?J5 b1. 5555 brs c1c o+??. c5 and a are positive inteters. and b05 c0 are nonnegative integers at lesat one of which La zero. For an input (a?1s....a0k). a 1-way k-tape DIA w can decide whether (n1sssssn?) ?atiafies o+ as follows. For a formula of fern (1). )( can use its finite atnory to compute the residues nod n of both sides with one pass over each input tape. So suppose the formula is of form (2). fly dividing both aides by the L?! of (b1sssssbr.c1sssssca)s we obtain an equivalent relation over N of the form - a o b1 + b c c0 + + .5 + c r I a where b05 c0 are nonnegatiwe rational nunbera5 and b15 555? brs e1s 555? c5 era positive in?sgera. For any natural nunber values assigned to the x?5 each aide represents a nonnecative rational nunbar. X can connare these rational nuabsfl as follows. For the left band aides it counts a 132 one for esery b1 squares 0 the 71-tape. until ul c b1 squaree are left. It then store. the residue in its finite lelory. and resumes the b1 counting ?y marking off b2 squares of the y2-tspe until u2 < h2 squares are left. etc. The Left hand value is then represented as a sum 0 the rational number u u - -1 r b0 + --H ... + --H b1 br and the total number 0 counts 0 one perormed on the y1--H. o+... 7r tapes. Similarly for the right hand side. Nov M cen use its finite menory to handle b0. c0 and all of the at nost r+s fractional residue.. and it can compare the integer counts on the two sides by alternating between the two counting processes until one side is exhausted. At this point. M need carry on the counting for the other side for at most th0i + Lc0J + r + a + 1 more ones to decide whether the formula holds. 0 Ve?. ? Let .M be a finite reversal-bounded unary k-tape NIA augmented by a finite reversal-bounded work tape and finite reversal-bounded counters. Then there is an effectively conputable Preaburger set 5 ? Nk such that n1 nk ((a ..a ) I (ni.sn?) c 5). ProoF: (similar to arguments in Ibarra ?l978. Section 6)) Let X have r finite reversal-bounded counters. We shall construct a machine X' with one input tape over the alphabet ? : (a15. ?55k? such that 51n1 ??a?? : (a?1 nk .....a ) e L(?) ). ii' is a finite reversal-bounded I-way 2-tape ?mi augmented by 2k+r 133 counters. Ia a single seam. it checks that its input is of the f?rss mi 1k a1 o+??1k a and for each i it bade mi o+mto On. 0 the two oountere assigned to the ith tape of M. These two counters cam obviously simulate a finite reversal-bounded read-only unary tape using fimitely many reversals. with the empty statuses of the counters corresponding to the detections of ? and $. Ilence ?(? can aimulate :: ?? desired. with the wort tape and the remaining r counters of ?? simulatins the work tape and the r counters of H. By Theorem 3.4.12 o+(L(M?)) satisfies the requirements for S and is effectively computable from M'. D A similar argument yielda L??. I Let u be a finite reversal-bounded unary k-tape ura augmented with an unrestricted puibdown store and finite reversal-bounded counters. Then there is an effectively computable Presburger set S S ik such that nI nk L(N) = ((a 5.a ) : (niesn?) 55). This strengthens Corollary 3.1 of liarrison and Ibarra Ll965?. fl Thpprem I The class of unary languages accepted by each of the following classes of machines is equal to PR. the class 0 unary encodings of the Presbureer relations: (1) DRA?s (2) NRA'a (3) finite reversal-bounded multitape n?A?s (4) finite reversal-bounded nultitape iFA's (5) finite reversal-bounded aultitape iFA?s augmented with a fimite reversal-bounded work tape and finite reversal-bounded counters (6) finite reversal-bounded multitape LTA's augmented with an unrestricted pushdown store and finite reversal-bounded counters. 13? Z:anL: Ve have tbe folloving inclusions: ? (2) ? 4 (5) ? PI (1) ? (3) ?(4) ? (6) 4 PI The inclusione involving PR are by Lennes 1. 2 and 3; the rest are by the definirione of the sachinee since finite revinde euffice. 0 "?.rb L Ilgot and Rutledge tl?64) proved the folloving result ihich Le similar to our Theores is the clase of unary languaeee accepted by deterministic 1-vay multihead multitape FA'a (arr.n??henpd a-? -?b.-.i La filgot and Rutledge's terminoLogy) ie exactly PR. To go from a Preeburger relation to an automaton. they use a proof similar to that of our Lens 1; in the opposite direction. they u.s an inductive proof that depende on the determinism of the machines. it is easy to see that `:e can use our techniques to strenethen zigot and Rutledge's result by introducing nondeterminism and an auxiliary puebdova store. etc. Ilotice that over arbitrary aiphabeta, Elgot and Rutledge1e machines are atrictly more powerful than DRa's. 0 3. s??eripn aL r.vp?1,1p in this section. we consider the possibility of eliminating head reversals for finite reversal-bounded unary multitapa rA's. We shov that this is always possible for the class of nondeterministic autosata but not for the class of deterministic automata. Th.prem L Every finite reversal-bounded unary k-tape MIA `5 has an effectively computable equivalent i-way unary k-tape ?FA `5'. fly Theorci 2.1. we can compute a semilinear set S such that j3? Suppose ul IlL L(M) o+ ( (a .....a ) a a I ). r Sc u (v vbere a ??? iO+j3:itijvij a tij ? 0 J vij . To recognias L(M). all M' has t? do La t. (1) guess an i a (l.'??.r); (2) read off portions of the k tapes according to tba k-vsctot ILca (3) repeatedly guess sole j 5 ?1'????5i? and read off portions of the k tapes according to the k-vector vi?. M' accepts if all beads are positioned on their respective $ after soce step (2) or (3) has been cos?leted.o+ it halts in a nonaccapting sta?e if the detection of a $ prevents the coapletion of coca step (2) or (3). This proof is a sachine version of the proof of Harrison and Ibarra (1968. Leiia 3.2). 0 It is easy to show that Theoree I does not hold with L'FA replaced hi ViA. For ezacple L.c ( (an.an) a n ? 0 ) u 1 (afl.a2n) a n ? 0 ) is acceptable by a I-reversal 2-tape DIA but not by any I-way 2-tape VIA. We conjecture that for each n. there is an (c+l)-reveraal unary 2-taps ViA with no equivalent i-reversaL unary 2-tape ViA. This vill inply that for each k ? 2. the k-ary Presburger relations fori a hierarchy based on the minicuu nuibera of reversals required for the recognition of their unary encodings by a k-taps VFA. Vs have not yet obtained a proof for this conjecture. & related hierarchy result based on the nuiber of rewinds vill be presented in the nest section. 1,' ?eteminiatic rewind autossata Vere ftrst studied by Rosenberg El'65. 1%?). Although by definition such an autoeston can zerforn any nunber of rewinds in an arbitrary coiputation. Rosenberg pointed out that one can always ilpose a rewind bound equal to the nunber of states in the finite control. This follows fron the simple observation that if in 5015 computation. the sutonaton enters the sante state after two distinct rewinda. then the conputation is in an infinite loop and hence cannot lead to acceptance. Hence we can restrict our discussion of dete?inistic rewind autonata to those with finite rewind bounds. This holds true for nondeterainistic rewind autonata as well; in this case we use the fact that if an input is accepted by a nondeterninistic rewind autonaton. then there is an accepting conputation in which the nachine enters a distinct state each tins it rewinds its tapes. Without loss of generality. we can assume that rewinds and halts only take placs vhen all input heads are positioned on their respectivo $. Clearly. in?between rewinds. a DRA (respectively NRA) behaves exactly like a Iway nultitape DFA (respectively NFA). Fros this observation. we derive the following characterization of the k-tape DRA (respectively lIRA) languages in terms of the I-way k-tape nFA (respectively NFA) languages. Th?nr?? L (Rosenberg (l?6?. l967?) ror each k. the class of k-tap?e DRA languages is the smallest faszily of languages which contains the I?sy k-tape DFA languages and is closed under intersection and union. Proof: That the class of k-tape bRA languages is such a fanily is obvious. To show that it is the smallest such. let ?I be a k-tape DRA with q states 137 o+1a ?2? 5555 o+q where ?i is the iuitial state and o+q is abe unique accepting state. For eacb pair of states a?5 s?5 let L1j be the set of k-tuples of tapes on which Ms when started is state witb all beads on ?. will ubys its beads to o+ and then rewind icto state or bait is state a?5 Then each Ljj is accepted by a l?vay t-tane ?FA. But t--Hl L(M) a u n L. r:l Lriro+l where the union is taken over all finite sequences i15 iis o+55s it of distinct integers fron (l.....q) such that i1 a l? it I q. and a? o+ 2 are not halting sta?es. So L(M) is in each fasity of languages t--Hl which contains the i-way k-tape uFA languages ad is closed under intersection and union. 0 tbeprp? ? For each k. the class of t-tspe h? languages is tbe ?lleIt fanily of languages which contains the I-way t-tape NFA languages and is closed under intersection and union. Sane as for Theores 1. 0 Ne&-t we show that the languages recognized by Via's fore a bierarchy besed on the nunber of rewinda. This hierarchy result bolda e,en if we restrict the languages to a unary input alphabet. L?n?. L Given any 2k distinct positive intecera o < II < o+2 < .5. < k5 2 the lansuage : ( ?5Z,5?? I y s v ... y y I o+2?Z ) is recognizable by a k-rewind 2-tape VFA. l's fly induction on k. using the binary search technique. Clearly. for k I ?? "a can progra a 1-vay 2-tape DFA vbich ebecks that Ix the input is of the fori (aX.a ) by alternately soving its first input bead 1 square and its second input bead Ii squares. lor tbe inductive step. `,a first construct two (k-l)-revind 2-tape DiA's ?? and 5," which recognize the languages 5 ( (a1.a7) : y : o+1x V o+.. V y : o+2k-i1 ? s ( (5X?0?) s y I 12k.l+1x V ... V y I o+2k1 ? reapectively. Tbau M. using instructions as in the case k I O? can decide in one scan of its input (5X.aY). whether (1) y c n2k?lx? (2) y I I2k?lx? or (3) y ? I2k?1X If (2) holds. M baits in an accepting state. Otherwise it revinds its beads and transfers control to ?? or ?(? depending on whether (1) or holds. (3 Lenna I shows that k revinds are sufficient for the recognition 0 Lk by 5 D%L. Our next lenla shows that k rewinds are also necessary. This is of course an autonata-theoretic version of a lover bound result on the nunber of conparisons required for testing neibership in an ordered table 0 length 2k We shall first analyse the behaviour of an n-rewind unary 2-tape DFA M in a single seen on 1tsufficiently long1 input tapes. Without loss of generality. we can essule further that 131 (1) H novel at least one of its beads in every operationi (2) H al?ays novel both its beads off their ? in its very first operation and in tbe first operation after a revindt (3) M will perforn eiactly 1 rewinds in every conputation. Since the input tapes are unsty. vs can represent an input to N as a pair (z*y) of nonnegative intesers. for convenience1 vs shall calL the tapee of fl its i-tape and y-tape. and the corresponding beads its i-bead and y-head. abbreviated and U?1 respectively. Suppose )I baa q states. Tben on sufficiently long input (x.y). say i ? q. y ? q. M will repeat a state in any conlecut?ve q operations. Since by assunption (2) above PI will be seeing the lane input synbols on the tapes after tbe first operation. this neans ?I will enter a periodic sequence of operations. with period q. until at least one of Ri1 Ry reaches its $. In each period. let ? nova a distance of ox squares and Hy a distance of y squares. If either ni or ny is 0. then intuitively )I baa derived no information ibout ?. On the other hsnd. if ax and ny are both positive. then for (i1y) such that 1 ?? q. y ?? q. and ? is sufficiently different Ii reaches $ first if end only if ?1 Al fron Al y ?. Hence informally. vs can say K has nade a coaparilon between and ?. This observation is of course the intuitive basis for the correspondence between a scan of 11 and a conparison in a search of an ordered table. By assuuption. if one bead reaches o+ before the other does. M will sinply nova the 5lagging' bead to its $ to conplete the scan. in an ultinately periodic sequence of oparationa with period ? q if that bead is sufficiently far away. Suppose 5k is a sat of 2? distinct positive "slopes": a ( n1 C ... C n k 140 Then o+(?) denotes the PreaburSer formula 7 a ?1? ? V 7 a l2kx lot any positive integer q. let p a E(q+l)!?2. We say a set A s is if (RI) there are infinitely many x such that pjx and (1.11x) a A: (n2) there is a Positive integer K such that for all I. 7 CM. us v a I (the set of all inteers). if z. 7. x+pu. y+pv ? r. (x.y) a A. and ? v+nv ? ?2?5 x+pu then (x+pu.y+pv) a A. linally. ve say a 2-tape DRA M v.r?fiep o+(Sk) sa a .`??? A nL )I2 if for all (x.y) in A. M accepts (x.y) iff (x.y) satisfies 1tnc a Let k. q be positive integers. For any set Sk of 2k positive slopes and any (S??q)?hard set A S ?I2. no (?--Hl)-revind 2-taps DIA M vith q states can verify o+(Sk) on A. Pr?nf t By induction on k. For )L 1. assume. for contradiction. that M is a l-'ray 2-tape DIA vith q states that verifies o+(S1) on some (S1.q)--Hbard set A. As before. let p : E(q+l)i?2. and let K be the constant in condition (H2) for the (S1.q)-hardness of A. Consider any sufficiently large 1 ? K+p such that pix. and (x.m1x) a A. Then since A is (S1.q)-hard. (x.?x) a A also. Hence X accepts?both (x.m1x) and (x.m2x). Now recall the analysis of the bebaviour of N on sufficiently large input if either ox 0 or ay a ?? then clearly (x.n1x+p) is also accepted by M since it causes N to halt in the sane state as for input (x.m1x). This is a contradiction since (x.n1x+p) a A and 141 a1?p a C Ca I x 2 for sufficiently large x. lance vs can ass-a than ax and 7 are lots positive. Clearly we aunt have either ni c o+r C a2. ax ax ax Suppose a1 ? Ax Then for sufficiently large x. M on input (x.a1x) will exhaust its y-tape with lix still ? 2p squares fron $. fly a punping arguaent. we sea that II on (x-p.n1x) will halt in the sane state as on (x.a1x). lance v also accepts (x-p.n1x). Now n1 C