D Vu Rigioniero

Linear-Time Limited Automata

Keywords:

he time omplexity of 1Elimited utomt is investigted from desriptionl omplexity view pointF hough the model reognizes regulr lnguges onlyD it my use qudrti time in the input lengthF e show thtD with polynomil inrese in size nd preserving determinismD eh 1Elimited utomton n e trnsformed into linerEtime equivlent oneF e lso otin polynomil trnsE formtions into relted modelsD inluding weightEreduing rennie mhines @i.e.D oneEtpe uring mhines synttilly fored to operte in linerEtimeAD nd we show exponentil gps for the onverse trnsformtions in the deterministi seF

1. Introduction yne lssil topi of omputer siene is the investigtion of omputtionl models operting under restritionsF pinite utomt or pushdown utomtD for instneD n e onsidered s prtiulr uring mhines in whih the E ess to memory storge is limitedF yther kinds of restritions follow from (ner nlyses of the omputtionl resoures n strt devie requires to reogE nize ertin lngugesF por exmpleD in the se of uring mhinesD lssil This is an extended version of results presented in [1] * Principal corresponding author * * Corresponding author Email addresses: bruno.guillon@inria.fr (Bruno Guillon), prigioniero@di.unimi.it (Luca Prigioniero) Preprint submitted to Elsevier December 27, 2021 omplexity lsses suh s PD NPD LogSpaceD etc. re de(ned y introduing limit on the mount of resouresD nmely time or speD t disposl of the modelF sullyD suh limittions redue the expressive powerF por instneD it is wellEknown tht oneEtpe nondeterministi uring mhines operting within spe ounded y the length of the inputD nmely linear bounded automataD pture extly the lss of context-sensitive languagesD see e.g. PF henomen like thisD where limiting n strt model redues its expressiveness to the level of some stndrd lssD re of gret interestD s they provide lterntive hrteriztions of lnguge lssesF enother exmple of this kind hs een oserved y rennie in IWTSF re indeed proved tht deterministi oneEtpe uring mhines operting in linear time reognize extly the lss of regular languages QF he result hs lter een extended to the nondeterministi se RD SF rereD operting in liner time mens tht every omputtion hs length linerly ounded in the input lengthF sn prtiulrD linerEtime mhines re neessrily hlting ! see S for investigtions of lterntive liner time restritionsF fy Hennie machine we refer to nondeterministi liner ounded utomton operting in liner timeF he oveEmentioned result implies tht every rennie mhine is equivlent to some (nite utomtonF prom the opposite point of viewD this mens tht providing two-way nite automata with the ility to overwrite the tpe ells does not extend the expressiveness of the modelD s long s the time is linerly ounded in the length of the inputF roweverD r•² showed tht it is undeidle given deterministi liner ounded utomton to hek whether it works in liner time over ll input stringsD nmelyD whether it is tully rennie mhine TF o void this drwE kD he proposed vrint of rennie mhineD lled weight-reducing Hennie machineD in whih the time limittion is synttiF sn this modelD eh visit to ell should overwrite its ontent with symol in deresing wyD with respet to some (xed order on the working lphetF es onsequeneD the numer of P visits of ell y the hed is ounded y some onstnt @i.e.D not depending on the input lengthA hene the devie works in liner time over every input stringF fy ontrst to rennie mhinesD the d-scan limited automata @or simply d-limited automata A introdued y rirdD restrit nondeterministi liner ounded utomt y llowing overwriting of eh tpe ell during its (rst d visE its onlyD for some (xed d ≥ 0 UF gontrry to weightEreduing rennie mhinesD the hed is still llowed to visit ell fter the dEth visitD ut it nnot rewrite the ontent nymoreF his llows to use superEliner timeF reneD limited automata @nmelyD dElimited utomt for some dA live midwy etween linE er ounded utomt nd weightEreduing rennie mhinesF rird proved thtD for eh d ≥ 2D dElimited utomt reognize extly the lss of contextfree languagesF re furthermore showed the existene of n in(nite hierrhy of deterministi dElimited utomtD whose (rst level @i. exp [11] ≥exp [11] Figure 1: Relationships between the main models studied in the paper. Here, lt and wr mean linear-time and weight-reducing, while d1-la and (d)hm stand for deterministic 1-la and (deterministic) Hennie machine, respectively. Deterministic and nondeterministic two-way automata with common guess are denoted by 2dfa+cg and 2nfa+cg. Dotted arrows indicate trivial connections while thick arrows indicate our results.

Preliminaries

sn this setion we rell some si de(nitions nd nottions useful in the pperF sn prtiulrD we ssume the reder fmilir with notions from forml lnguges nd utomt theory @seeD e.g.D PAF qiven set SD #S denotes its rdinlity nd 2 S the fmily of ll its susetsF qiven n lphet ΣD we denote y |w| the length of string w ∈ Σ * D y w r the reversl of w nd y ε the empty stringF por lnguge L ⊆ Σ * D L r denotes the reversal of LD omputtion pth strting from the initil stte q 0 with the hed on the (rst tpe ell @i.e.D snning the left endmrkerA nd ending in (nl stte q ∈ F fter violting the right endmrkerF he lnguge epted y A is denoted y L (A)F e 2nfa A is sid to e deterministic @2dfaAD whenever #δ(q, σ) ≤ 1D

nmely L r = {w r | w ∈ L}F Denition 1. A twoEwy nondeterministi (nite utomton ( 2nfa) is a quin- tuple A = (Q, Σ, δ, q 0 , F ), where Q is a nite set of sttes, Σ is a nite inE put lphet, q 0 ∈ Q is the initil stte, F ⊆ Q is a set of (nl sttes, and δ : Q × Σ → 2 Q×{-1,0,+1} is a nondeterministi
for ny q ∈ Q nd σ ∈ Σ F st
A = (Q, Σ, Γ, δ, q 0 , F ),
where Q, Σ, q 0 and F are dened as for 2nfas, Γ is a nite working lphet such that Σ ⊂ Γ, δ : Q × Γ → 2 Q×Γ ×{-1,0,+1} is the nondeterministi trnsition funtion where Γ denotes the set Γ ∪ { , } with , / ∈ Γ the left and the right endmarkers as for 2nfas. Moreover, for each transition (q, γ, d) ∈

δ(p, σ), we have γ ∈ Γ \ Σ and if σ ∈ Γ \ Σ then γ = σ.
sn one moveD ording to δD A reds symol from the tpeD hnges its stteD reples the symol just red y new symolD nd moves its hed one position kwrd or forwrd or keeps it in pleF roweverD repling symols is sujet to some restritionsD whihD essentillyD llow to modify the ontent of ell during the (rst visit onlyF ehnillyD symols from Σ shll e repled y symols from Γ \ ΣD while symols from Γ \ Σ re never overwrittenF sn prtiulrD t ny timeD oth speil symols nd our extly one on the tpe nd extly t the respetive left nd right oundriesF Acceptance for 1-las s well s deterministic 1-las re de(ned extly s for 2nfasD nd T the lnguge epted y given 1-la A is denoted y L (A)F he following resultD whih is instrumentl for our lter proofsD gives simE pler form of 1-lasF Lemma 1. For each n-state 1-la, there exists an equivalent 3n-state 1-la using the same working alphabet, which performs stationary moves exactly when rewriting a cell content. Furthermore, the conversion preserves determinism.

Proof. pirstD y using stndrd tehniquesD eh sequene of sttionry moves followed y nonsttionry move n e repled y nonsttionry trnsitionF his opertion does not inrese the size of the 1-laF ine in every epting omputtion the lst trnsition performed y ny 1-la is right move from the rightmost ell of the tpeD this modi(tion elimintes ll the sttionry movesF eondD we n split every rewriting step into two stepsX (rst sttionry step during whih the input ell is rewrittenD followed y seond redEonly nonsttionry stepF his yields liner inrese of the size of the devie onlyF wore preiselyD for eh stte q ∈ Q nd eh diretion d ∈ {-1, +1}D we rete new opy (q, d) / ∈ Q of qD whose interprettion is to dely the hed move dF henD eh rewriting trnsition (q, γ, d) ∈ δ(p, σ) is repled y two trnsitions ((q, d), γ, 0) from p on σ nd (q, γ, d) from (q, d) on γF where Q denotes the set of sttes of AF e pir (p, q) elongs to τ z X if nd only ifD strting from stte p with the hed snning the lst symol of z XD A my reh stte q one ell to the right of z XF pormllyD to Q × QD the iEth ell of the portion storing the tle τ z X will ontin 1 if µ(i) elongs to τ z X D nd 0 otherwiseF es onsequeneD we do not store ll the tles orresponding to eh tpe position ut suolletion of themF wore preiselyD we only store tles τ z X for tpe ontent pre(xes z X of length multiple of n 2 F husD updting the tles should e done lok y lok rther thn ell y ellD for deomposition of the input into loks of length n 2 F @e onsider the ell ontining the left endmrker s omplete lokD while the lst lok ontining the right endmrker my e shorter thn n 2 FA hen A is deterministiD τ z X is prtil 1 funtion from Q to QF sn this 1 In the deterministic case, the image associated with p by τ z X is undened if one of the two following cases of the computation starting in z • p • X occurs: either, after a nite IH se it is possile to improve the oveEdesried onstrution y storing the tles τ z X on the n ells following the lst position of z XF he input is therefore deomposed into loks of length n rther thn n 2 F roweverD the lphet used to store the tle hs size n + 1 rther thn 2F sndeedD the iEth ell of the portion storing the tle will ontin the imge of the iEth stte of A

L n = {x 0 x 1 • • • x k | k ∈ N, for eh i : x i ∈ {a,
τ z X = {(p, q) | z • p • X * z X • q}F ith the informtion of τ z X D B
y τ z X if de(nedD or speil symol ⊥ / ∈ Q otherwiseF 3.2.
= n nd T = Q ⊥ where Q ⊥ = Q ∪ {⊥} for ⊥ symol not elonging
to QF woreoverD we (x mpping ν from {0, . . . , -1} to Q de(ned for eh index i ∈ {0, . . . , -1} s followsX number of steps, no successive transition is dened (incompleteness of A), or the computation eventually enters a deterministic loop (non-haltingness of A). readFromTable strts from nd ends in the (rst position of the lok onE tining x with stte p given s rgument nd returns stte q suh tht (p, q) ∈ τ z F elterntivelyD it my return the error symol ⊥ if no suh q exists or if its internl omputtion filsF xeverthelessD for eh stte q suh tht (p, q) ∈ τ z D the proedure my return qF huring its omputtionD the suroutine visits ells of the lok ontining x onlyF IQ simulateLeft strts from nd ends in the lst position of x @respF of y if y = εA with stte p given s rgument nd returns stte q suh tht (p, q) ∈ τ zx @respF (p, q) ∈ τ zxy AF elterntivelyD it my return the error symol ⊥ if no suh q exists or if its internl omputtion filsF xeverthelessD for eh stte q suh tht (p, q) ∈ τ zx @respF (p, q) ∈ τ zxy AD the proedure my return qF huring its omputtionD the suroutine visits ells of the lok ontining x @respF of the portion of the tpe ontining x yA onlyF hen the simulted 1-la is deterministiD it is possile to implement oth suroutines in deterministi wyF he implementtions of these suroutines re desried in etion QFPFQF where i ∈ {0, . . . , -1} is the position in the snned lok of length nd s ∈ {l, r} is equl to l @respF rA if the hed is snning position in the left @respF rightA lok of the windowF e suppose tht the omponent is updted t eh hed moveF sing this omponentD A n void moving to the left of the urrent windowF wore preiselyD from reltive position (0, l) @i.e.D the leftmost position overed y the windowAD when kwrd move of A from p to q hs to e simultedD A lls the proedure readFromTable with rgument qD in order to (nd stte r suh tht (q, r) ∈ τ z D where z is the ontent of the tpe to the left of the windowF reneD it simultes not only the kwrd step from p to qD ut lso omplete omputtion segment to the left of the windowD nmelyD it informtionD whih is required to determine the symol to write on the ellD hs een gtheredF wore preiselyD when A moves its hed to the frontier ell @vine WAD it stores pir (p, q) in its (nite ontrolD suh thtX p ∈ Q is the stte entered y A in the simulted omputtionD when visiting for the (rst time the orresponding ellY IS q ∈ Q ⊥ is either ⊥ or stte suh tht (ν(ρ), q) ∈ τ zx D where zx denotes the ontent to the left of the right lok of the window @i.e.D the lok of the frontier ellA in the simulted omputtionF he sttes p nd q re stored in two vrilesD respetively nmed frontier-State nd tableStateD whih re updted through two lls to the suroutine simulateLeftX from one ell to the left of the frontierD to updte frontierState @vine RAY from the lst ell of the preeding lokD to updte tableState @vine UAF yne A hs updted the vriles frontierState nd tableStateD it moves the hed to the ell t reltive position (ρ, r) @vine WAD nd reds the input symol 34 move head rightward until reaching position (i, s) t reltive position (i, s)D nd updtes the vrile var to the vlue qF xotie tht the diret simultion is deterministi if A is deterministiD sine the proedure readFromTable is deterministi in this seD y vemm PF roweverD this nive pproh might fil euse the diret simultion my enter loops nd never hltF sn order to hndle this issueD we need to detet omputtionl loopsF e proeed s followsF sf (p, q) ∈ τ zxy then this n e witnessed y diret simultion whih never repets on(gurtionF sn prtiulrD the sme stte nnot e entered twie t the sme positionF ine the proedure simulateLeft opertes in redEonly window of size t most 2 D ny repetitionEfree omputtion hs length ounded y 2 n @ounting the lls to the suroutine readFromTable s single moveAF reneD y using lok of size 2 nD stored in the (nite ontrol of the simulting devieD we n enfore the proedure to hltF ynly runs tht hlted efore this time limit my return stte while killed runs will return ⊥F xotie tht the lok yields polynomil inrese of the size of the simulting mhine onlyF IW vet us fous on the implementtion detils of simulateLeft given in roeE dure PF he suroutine strts y storing the vlue (i, s) of the urrent reltive position @vine IVA nd the clock to 2 n @vine IWAF efter thtD A simultes A y reding the (rst trk of the snned ell nd using the trnsition funtion of the simulted mhine @vines PI nd PPAF he next simulted stte rehed y A is stored in the vrile var @vine PQAF sfD y inompleteness of the trnE sition funtion of A no stte existsD var gets vlue ⊥ nd the proedure ends fter moving its hed rightwrd to the position (i, s) from whih it ws lled @vines PRD PS nd QRAF sn se right move from reltive position (i, s) is detetedD the proedure ends without moving rightwrd @vines PT nd PUAF sf left move from the reltive position (0, l) is detetedD A lls readFromTable in order to simulte the omputtion segment to the left of the window @vines PV nd PWAF ytherwiseD A n diretly simulte the trnsition performed y AX the simulting mhine moves its hed ording to the simulted trnsition @vine QIAF efter eh simulted move 2 of AD the vlue of the clock is dereE mented @vine QPAF sf fter 2 n simulted moves the routine hs not hltedD then it updtes the vlue of var with ⊥D moves the hed rightwrd until rehing the reltive position (i, s)D nd hlts @vines QQ nd QRAF reneD implementing simulateLeft requires only polynomil numer of sttes in nF Lemma 3. The subroutine simulateLeft can be implemented using 12 n + 2 states, not counting the global variables var, relativePosition, and relativeFrontier. Furthermore, it is deterministic if A is deterministic.

II

w ∈ (Γ \ Σ) * , x ∈ (Γ \ Σ) , y ∈ (Γ \ Σ) * , u ∈ Σ + with |yu| = , and v ∈ Σ * . if = n 2 then ν(i) is the stte p suh tht µ(i) = (p, q) for some stte q @rell tht µ is (xed ijetion from 0, . . . , n 2 -1 to Q 2 AY if = n then ν(i) = q i D ssuming Q = {q 0 , . . . , q n-
simultes z X • p z • q • X * z X •
σ ∈ Σ ∪ { } @vine IHAF sf σ = then A enters (nl
Proof. sing vemm PD the implementtion of simulateLeft given in roE edure P is deterministi when A is deterministiF purthermoreD it uses the following stte omponentsF e inry stte omponent is required for keeping trk of the llEmode 2 Here, we consider the simulated computation segments to the left of the window, which are recovered through call to readFromTable (Line 29), as single moves. PH in whih the proedure is opertingF woreoverD sine the mode lso deE termines the position from whih the proedure is lledD nd euse the reltive frontier @stored in the vrile relativeFrontierA is not modi(ed during the exeution of the proedureD no further stte omponents re neessry for storing initil vlue (i, s) of relativePositionF e stte omponent of size 2 n is required for storing the vlue of the clock @we do not need to store the vlue 0D s the devie n diretly enter filure stte when derementing the lok from vlue 1AF e stte omponent of size 3 storing the three internl modes of the proE edureD nmely the min mode nd the two suEmodes resulting from the lls to the routine readFromTable @vine PWA y vemm PF yne filure stte for eh llEmode is required for moving the hed rightE wrd until rehing the initil position (i, s) when the proedure fils @vine QRAF reneD the totl numer of sttes required for implementing simulateLeft e onsider 2dfa vrint C simulting AD whih strts from nd ends in some spei(ed positionF e ssume tht it hs ess to the vriles rel-ativePosition nd relativeFrontierF st silly performs n unloked version of PP roedure P in whih the filure stte @vine QRA hs een thrown wyF purE thermoreD we ignore the lst updte of varD when the imge q of p y τ zwX is foundF e n suppose tht C never performs sttionry movesF sndeedD on the one hndD A does not perform ny sttionry move when working on frozen symols y ssumptionF yn the other hndD without inresing the size of the devieD we n eliminte the sttionry moves possily resulting from the lls to the suroutine readFromTableD y using lssil tehniquesF woreoverD C n e implemented using 3 sttes onlyD not ounting the vrile varD ording to vemm P @one stte for the min modeD nd two dditionl sttes for the lls to the suEroutine readFromTableAF ememer tht X is the symol writE ten t reltive position (i, s) nd let R(X) = {r | ∃q, δ(r, X) = {(q, X, +1)}}F en accepting conguration of CD is on(gurtion in whih the hed is poE sitioned t reltive position (i, s) @thus snning XAD the internl stte orreE sponds to its min mode @i.e.D not to ll to readFromTableAD nd var ontins stte r ∈ R(X)F yserve thtD lthough we dropped the lst updte of var with respet to roedure PD it is possile to reover it from the hlting point of CF snE deedD this vlue is either q ∈ Q if C hlted in n epting on(gurtion with var storing r ∈ R(X) suh tht δ(r, X) = {q, X, +1}D or ⊥ otherwiseF xotie tht C does not use the endmrkers ut rther the reltive positionD to ensure tht the hed stys etween (0, l) nd (i, s)F sn prtiulrD the initial conguration c I of C is t reltive position (i, s) with the stte orresponding to its min mode nd var storing pF he min issue for dpting ipser9s onstrution to our seD is tht the trE get on(gurtion c F is initilly unknownF sndeedD it is the role of simulateLeft to (nd the imge q of p y τ zwX @when de(nedAF sn order to solve this issueD we pply the ipser simultion of C for eh vlue r ∈ R(X) of varF fy tkE ing suh r9s in orderD we only need 4 internl suEmodes for the simultionD s in ITF sndeedD if for some trget on(gurtion c F (r) the simultion does not (nd c I D then it hlts in on(gurtion tht enodes c F (r)F sn prtiulrD var ontins r nd n thus e updted with the next vlue from R(X)F sf no suE PQ essor of r existsD then C n never reh n epting on(gurtionD nmely c I is in none of the trees rooted in the c F (r)9sF husD our proedure updtes var with the symol ⊥ nd hltsF sf otherwise the on(gurtion c I hs een found during simultion strting from some c F (r)D then the diret exeution of C hlts in c F (r)F husD it is enough to diretly simulte C from c I nd to upE dte var ording to the stte r whih is reovered when the exeution hltsF wore preiselyD one C hs rehed c F (r)D our proedure reds the symol X nd updtes the vrile var whih ontins r ∈ R(X) with the stte q suh tht δ(r, X) = {(q, X, +1)}F e now evlute the size of this deterministi version of simulateLeftD whih works independently of the hosen tle enoding @i.e.D for ny T, AD so long s A is deterministiF Lemma 4. If A is deterministic, then, independently of the encoding of the Shepherdson tables on the tape, the procedure simulateLeft can be implemented deterministically using 30 internal states, not counting the global variables var, relativePosition, and relativeFrontier.

Proof. e evlute the implementtion desried oveF es in the impleE menttion given in etion QFPFQD we need inry omponent for storing the llEmode of the proedureF his omponent is su0ient to reover the strtE ing position (i, s)D possily y reding the vlue of relativeFrontier whih is not modi(ed during the exeution of the proedureF hen the 3Emode utomton C given ove is simulted (rst timeD y ipser9s onstrutionD using 4 suEmodesF sf the simultion sueeds then C is simulted seond time in order to reover the vlue to store in varF ytherwiseD no further stte is neededD s filure neessrily ours t position (i, s) from whih var is updted to ⊥ without moving the hedF husD not ounting the glol vriles relativePositionD relativeFrontierD fron-tierStateD nd tableStateD we otin tht 2(12 + 3) sttes re enoughF PR 3.3. Properties of A sn this setionD we stte the min properties of the 1-la A tht hs een otined from A y the simultion de(ned in etion QFPF xotie tht severl simultions hve een desriedF e di'erentite them only when requiredF Lemma 5. A is equivalent to A.

Proof. e (rst prove tht

L (A) ⊆ L (A )F gonsider n epting omputE tion c = c 0 , c 1 , . . . , c t of A on some input w = w 1 • • • w m ∈ Σ * D where c 0 = q 0 • w nd c t = x • q F D for some q F ∈ F nd x = x 1 • • • x m ∈ (Γ \ Σ) * F
e n extrt from c the sequene c j1 , . . . , c jm of on(gurtions in whih the hed is snning symol of ΣD nmelyD for eh i ∈ {1, . . . , m}D c ji =

x 1 • • • x i-1 • p i • w i • •
• w m for some stte p i F xotie tht p i is neessrily the (rst stte entered t position i in cF woreoverD sine y ssumption A hs the form given in vemm ID we hve

c ji+1 = x 1 • • • x i-1 • p i • x i w i+1 • • • w m for some stte p i F sn prtiulrD (p i , x i , 0) ∈ δ(p i , w i )
is the sttionry trnsiE tion whih is performed when overwriting the ontent of the ell t position i during the omputtion cF por onvenieneD we de(ne c jm+1 to e the (rst on(gurtion of the form

x 1 • • • x m • p m+1 • for some stte p m+1 F e lso set x 0 = D x m+1 = D p 0 = p 0 = q 0 D p m+1 = p m+1 D nd p m+2 = q F F por eh i ∈ {0, . . . , m + 1}D we hve (p i , p i+1 ) ∈ τ x0•••xi F
he simulting 1-la A reovers c y suessively storing the sttes p 0 , p 1 , p 1 , . . . , p m+1 , p m+1 , p m+2 in its internl vrile frontierStateD while visiting the orresponding ells from left to rightF wore preiselyD for eh i ∈ {0, . . . , m + 2}D when A enters the iEth tpe ell for the (rst timeD the vrile frontierState ontins the stte p i F st is routine to show y indution thtD t eh itertion of the while loop in roeE dure I @vines Q to ISAD s soon s the left lok of the urrent window enodes the orret tleD the two lls to the suroutine simulateLeft n reover the right informtionD nmely frontierState is updted from p i to p i+1 on vine RD nd tableState is updted from ν(ρ) to q on vine UD where q is suh thtX 4 Though the model is motivated by special behaviors of 1-las whence the nondeterministic pre-computation is naturally thought as being one-way left-to-right, there is no reason to impose this. Here, the marking is uniform meaning that each cell is independently marked by a nondeterministically-chosen symbol of ∆. This operation is connected with existential set quantication in monadic second order logic, see, e.g., [13]. QH frontier is n e expressed y speifying the sttes tht re entered extly when visiting tpe ell for the (rst timeF sn order to simulte suh 1-la @with input lphet Σ nd working lphet ΓA with 2fa+cg @with ommon guess lphet ∆AD it is indeed enough to (rst guess the working symols tht will e written on the tpe t the end of the omputtion @thusD setting ∆ = ΓAD nd then simulte the 1-la in redEonly mnnerD using the symol omponent in Σ when the ell is visited for the (rst time @whih is determined y the urrent stteA or the symol omponent in Γ otherwiseD while heking tht the guessed symols orrespond to the symol overwritten during the simulted omputtionF xotie thtD so otinedD the resulting devie is 2dfa+cg @respF is hltingA when the soure 1-la is deterministi @respF hltingAF gonerning the onversion of ritrry 1-las @i.e.D not knowing where the frontier isA into equivlent 2fa+cgsD it is nonEtrivil onsequene of our min onstrution tht with polynomil inrese of the size onlyD this n e hievedF Theorem 3. Each 1-la (resp. deterministic 1-la) admits an equivalent halting 2nfa+cg (resp. 2dfa+cg) of polynomial size.

if T = {0, 1} then either q is stte r suh tht (ν(ρ), r) ∈ τ x0•••x k D or q = ⊥Y PS if T = Q ⊥ then q is the imge of ν(ρ) y τ x0•••x k if de(nedD or
Proof. fy vemm VD A knows where the frontier isF reneD y pplying the oveEgiven onversionD we n otin n equivlent 2fa+cg of polynomil sizeD whih is hlting y vemm UF purthermoreD if A is deterministiD then the resulting devie is 2dfa+cgF sn the nondeterministi seD this lst result is of prtiulr interestF sndeedD 2nfa+cg9s n e seen s prtiulr ses of 1-lasF @st is not the se for 2dfa+cg9s with respet to deterministi 1-lasFA reneD heorem Q gives kind of norml form for nondeterministi 1-lasF sn prtiulrD it is esy to modify suh 1-la in order to reognize the reverse of its epted lngugeF Corollary 1. Each 1-la A can be transformed into a nondeterministic 1-la A with a polynomial increase of the size, such that L (A ) = L (A)

  e.D orresponding to deterE ministi 2Elimited utomtA hs een lter proved to oinide with the lss of deterministic context-free languages VF @ee W nd referenes therein for further onnetions etween limited utomt nd ontextEfree lngugesFA glerlyD 0Elimited utomt re no more thn twoEwy (nite utomt hene hrterize the lss of regulr lngugesF gner nd ehsung extended this result to the se d = 1X 1Elimited utomt reognize extly the lss of reguE lr lnguges IHF prom tht pointD the question of the ost of their simultion y lssil (nite utomt hs een studied y ighizzini nd isoni in IID where tight doulyEexponentil simultion y deterministi oneEwy (nite uE tomt is provedF his ost redues to single exponentil when strting from deterministi 1Elimited utomtonF woreoverD n exponentil lower ound hs een otined in IPD for the simultion of deterministi 1Elimited utomt y nondeterministi twoEwy (nite utomtF vike dElimited utomtD 1Elimited utomt n operte in superEliner time @cf. ixmple IAF his ontrsts with rennie mhines whih operte in liner time y de(nitionF he question we ddress in this pper is whether this ility of 1Elimited utomt with respet to rennie mhines yields gp etween Q the two models in terms of the size of their representtionsF e show thtD with polynomil inrese in sizeD eh 1Elimited utomton n e trnsformed into n equivlent linerEtime 1Elimited utomtonD orD lE terntivelyD into weightEreduing rennie mhineF purthermoreD we re le to otin deterministi devie when the originl mhine is deterministiF e lso show tht the 1Elimited utomt resulting from our onstrutions hve speil struture tht n e exploited in order to otin equivlent 1ElimE ited utomt in whih n initil memoryless phse overwrites eh tpe ellD i.e.D the devie initilly performs nondeterministi leftEtoEright pss over the tpe during whih ll the ells re independently overwrittenF imilr ehvE iors hve een onsidered in the ontext of regular transductionD euse of their orrespondene with glol existentil qunti(tion in monadic second order logicD see IQ in whih the uthors de(ne n opertion lled common guess orresponding to nondeterministi memoryless overwriting of the tpeF reneD s onsequene of our min resultD eh 1Elimited utomton n e simulted y two-way automaton with common guess of polynomil sizeF st follows tht reversing 1Elimited utomtonD i.e.D trnsforming it into nother one reognizing the reverse of its epted lngugeD hs polynomil ost onlyF his fils in the deterministi seD for whih we exhiit n exponentil lower oundF es onsequeneD we otin exponentil lower ounds for the simulE tion of deterministi weightEreduing rennie mhines or deterministi twoEwy utomt with ommon guess y deterministi 1Elimited utomtF he results re summrized in pigure IF he pper is orgnized s followsF sn etion P re gthered the min de(niE tions nd nottions needed in the susequent setionsF he min onstrutions used for proving our results re detiled in etion QD while the results re (

  trnsition funtion where Σ denotes the set Σ ∪ { , } with the two special symbols , / ∈ Σ respectively called the left and the right endmrkers. he input is written on the tpe surrounded y the two endmrkersD the left endmrker eing t the position zeroF reneD on input wD the right endmrker S is t position |w| + 1F sn one moveD A reds n input symolD hnges its stteD nd moves the input hed one position kwrdD forwrd or keeps it in position depending on whether δ returns -1D +1 or 0D respetivelyF purthermoreD the hed nnot violte the endmrkersD exept t the end of omputtionD to ept the inputD s now explinedF he mhine accepts the inputD if there exists

  b} n , for some j = 0 : x j = x 0 }F e deterministi 1-la A n my reognize L n s followsF st (rst sns the ftor x 0 D overwriting eh input symol with mrked opyF henD A n repets surouE tine whih overwrites ftor x i with some (xed symol D while heking in the mentime whether x i equls x 0 or notF his n e hieved s followsF fefore overwriting the jEth symol of x i D (rstD A n D with the help of ounter modE ulo nD moves the hed leftwrd to the position j of x 0 nd stores the unmrked snned symol σ in its (nite ontrolY seondD it moves the hed rightwrd until rehing the position j of x i D nmelyD the leftmost position tht hs not een overwritten so frF et this pointD A n ompres the snned symol @i.e.D the jEth symol of x i A with σ @i.e.D the jEth symol of x 0 AF fy setting foolen )g to true when omplete ftor x i hs mthed x 0 nd (nlly heking tht the input string hs length multiple of nD A n n deide the memership of the input to L n F st is possile to implement A n with numer of sttes liner in n nd #Σ+1 working symolsF ine for eh position of ftor x i D i > 0D the hed hs to move k to the ftor x 0 D we oserve tht A n works in qudrti time in the length of the input stringF 3. Linear-Time Simulations of 1-las sf linerEspe uring mhine n visit tpe ell only onstnt numer of timesD it neessrily works in liner timeF gonverselyD uring mhines workE ing in liner time @i.e.D rennie mhinesAD hve een shown to visit eh tpe V ell only onstnt numer of times during omputtion QF his ontrsts with the se of 1-lasD whih n use qudrti timeD s shown in ixmple IF roweverD our min ontriution sttes thtD with polynomil inrese in size of the modelD we n reover the ove propertyD nd therefore otin equivlent 1-las working in liner timeF 3.1. Main ingredients 3.1.1. Local window space bound he key ide to otin liner time oundD is to ensure thtD in ny omE puttionD the simulting devie works on virtul window of (xed size tht is shifted long the tpe in oneEwy mnnerF wore preiselyD in the omputtions of our simulting 1-lasD there exists onstnt K not depending on the input lengthD suh thtD for ny two tpe ells t distne KD the leftmost one nnot e visited fter hving visited the rightmost oneF sn this wyD it is possile to ound the numer of visits of eh ellF sn our simultion we divide the input word into loks of some (xed length D given y some polynomil in the numer n of sttes of the simulted 1-laF henD our virtul window overs two suessive loksD i.e.D K = 2 F he length is hosen in suh wy thtD one overwrittenD lok on the tpe my ontin the su0ient informtion for reovering the ehviors of the simulted mhine tht my our on the left of the windowF hesriing nd storing this informtion is the purpose of the following susetionF 3.1.2. Shepherdson tables sn IID the uthors presented onstrution to simulte ny 1-la A y (nite utomton BD using lssi ides from the simultion of twoEwy utomt y oneEwy utomt IRF he min ingredient ws to store in the (nite ontrol of BD trnsition tle desriing the possile ehviors of A tht my our to the left of the urrent hed positionF ine the prt of the tpe to the left of the urrent hed position hs neessrily lredy een visitedD its frozen ontent elongs to (Γ \ Σ) * ∪ {ε}F reneD the oveEmentioned ehviors to the left of the urrent hed position re redEonly omputtionsF o represent themD for W eh word z X ∈ (Γ \ Σ) * with |X| = 1D we onsider reltion τ z X ⊆ Q × QD

  hs no need to red the prt of the tpe ontining z XD tht isD to move its hed leftwrdF purthermoreD given string x ∈ (Γ \ Σ) * D we n onstrut τ z Xx from τ z X y snning xF por onvenieneD we set τ ε = ∅F e denote y n the rdinlity of QF sn IID the tle of size n 2 orrespondE ing to the reltion τ z X ws stored in the (nite ontrol of the simulting 1nfa B nd it ws updted t eh stepF his yielded n exponentil numer of sttes for storing the 2 n 2 possile tles thus implying n exponentil size of B with respet to AF his lowup ws shown to e neessry in the worst se for the onsidered simultionF rereD s our simulting devie is 1-laD we tke dvntge of its ility to write on the tpeF e indeed store the tle τ z X onto the n 2 ells following the lst position of z XF pormllyD (xing ijetion µ from 0, . . . , n 2 -1

  Construction of the simulating 1-la A yur simultion omines the two ides disussed previouslyD y storing suolletion of the hepherdson tles on the tpeF e tully present severl simultions trnsforming 1-las into equivlent linerEtime 1-lasF he most generl one produes nondeterministi 1-la from nondeterministi 1-laF he other ones produe deterministi 1-la from deterministi 1-laF he vrious onstrutions re very similr nd di'er only in some si routines nd in the enoding of the hepherdson tlesF e (rst present their ommon glol struture nd then we speify their di'erenesD when detiling the lowElevel implementtion of the si opertions nd suroutines used for the simultion in etion QFPFQF o this endD we now (x some onvenient nottionsF vet A = (Q, Σ, Γ, δ, q 0 , F ) e the soure 1-laF fy vemm ID modulo liner size inreseD we suppose tht A performs sttionry moves extly when overE writing ell ontentF yur gol is to uild linerEtime 1-la A = (Q , Σ, Γ , δ , q 0 , F ) equivlent to AD whih hs polynomil size with respet to to the size of AF vet denote the size of the loks in the tpe deomposition disussed oveD nd let T denote the set of symols used to enode the hepherdson tles on tpeF pormllyD either = n 2 nd T = {0, 1}D orD possily if A is deterministiD

Figure 2 :

 2 Figure 2: Typical description of the window during a computation of A: m denotes the length of the input word, the current frontier occurs in the right block as rst position of u,

  1 }F huring omputtion of our simulting 1-la A D the frozen ontent of the tpe n e viewed s divided into two trksX the (rst trk ontins the symE ols overwritten y A in the simulted omputtionY the seond trk ontins the enoding of the hepherdson tles τ z X F e thus (x the set of working symols to e the produt of Γ \ Σ nd T D i.e.D Γ = ((Γ \ Σ) × T ) ∪ ΣF es previously explinedD the ehvior of A will e lolly restrited to window of ounded widthF et ny time in omputtion of A we onsider virtul window whih overs two suessive loks in the tpe deomposition desried oveF he right lok overed y the window ontins the leftmost ell tht hs not een visited so frD to whih we refer s urrent frontierF he ontent x of the left lok overed y the window elongs to (Γ \ Σ) ∪{ }F he ontent of the right lok overed y the window n e deomposed into yu with y ∈ (Γ \ Σ) * nd u ∈ Σ + ∪ Σ * suh tht |yu| = unlessD possilyD ours in uD in whih se |yu| ≤ F he frontier is on the (rst position of uF e typil sitution is depited in pigure PF sn order to simulte AD the linerEtime 1-la A overwrites eh lok with word x ∈ (Γ \ Σ) whose projetion on Γ \ Σ is the word x written y A on IP the orresponding lok in the simulted omputtionD nd the projetion on T is extly the enoding of the tle τ z D where z is the ontent of the tpe to the left of the orresponding lok in the simulted omputtionF @sn pigure PD z = w when onsidering the left lok overed y the windowD whose frozen ontent is xFA oughlyD in the simulting omputtionD when the frontier ours t the (rst position of lokD A hs to (ll this lokD ell y ellD with the enoding of τ zx D where x @respF zA is the projetion on Γ \ Σ of the ontent x of the preeding lok whih is overed y the window @respF of the ontent z of the tpe to the left of the urrent windowAF o this endD it hs redEonly ess to the left lokD whose ontent x gthers ll the required informtionD nmely τ z nd xF sn prllelD A should lso reover the simulted omputtion of AF es soon s the right lok is ompletely (lledD the window is shifted to the rightD in suh wy tht it overs the lok just treted @s left prtA nd its suessor @s right prtAF 3.2.1. Auxiliary procedures readFromTable and simulateLeft yur simultion uses two suroutinesD readFromTable nd simulateLeftD whih re lled in order to reover some vlue from τ z D where z is tpe ontent pre(x in the simulted omputtionF sing the oveEgiven nottions @seeD e.g.D pigure PAD we suppose tht the virtul window overs two suessive loksD the left one ontining x ∈ (Γ \ Σ) ∪ { }D nd the right one eing prtilly (lled with pre(x y ∈ (Γ \ Σ) * of length less thn F e denote y z ∈ (Γ \ Σ) * ∪ {ε} the tpe ontent to the left of the window in the simulted omputtionF

  rD where z X = zF sn ddition to the reltive positionD A stores in glol vrileD nmed relativeFrontierD the reltive position of the urrent frontierD to whih we refer s relative frontierF ine this position lwys ours in the right lok of the windowD it is enough to represent it s n index ρ ∈ {0, . . . , -1}F wuh IR Procedure 1: main /* the variables relativePosition and relativeFrontier are not indicated and are supposed to be automatically updated; in the following, current symbol designates the symbol currently read by the head */ 1 frontierState ← q0 2 tableState ← ν(relativeFrontier) head rightward until reaching position relativeFrontier -1 9 move the input head one cell to the right 10 if current symbol = then 11 let (q, γ, 0) = selectTransition(frontierState,current symb ) 12 frontierState ← q 13 if frontierState = ⊥ then Reject 14 write(γ,tableState) 15 tableState ← ν(relativeFrontier) 16 simulateLeft(frontierState) 17 if frontierState ∈ F then Accept else Reject like the reltive position omponentD we suppose tht it is updted eh time ell is visited for the (rst timeF yserve tht suh updtes re inrements modulo F snrementing ρ = -1 mens shifting the window y ells to the rightF sn prtiulrD this implies to updting the reltive position y swithing it from ( -1, r) to ( -1, l)F snitillyD the hed is snning the left endmrkerD whih is onsidered s the left lok of the urrent windowF reneD the initil reltive position nd reltive frontier re ( -1, l) nd 0D respetivelyF sing oth the reltive frontier ρ nd the reltive position (i, s)D A n ensure tht entering ell for the (rst timeD my e done only one ll the

  mode in whih it lls the suroutine simulateLeft with rgument frontierState from the urrent positionD nd eptsD fter violting the endmrkerD if the updted vlue of frontierState is (nl stte of A nd rejets otherwise @vines IT nd IUAF sf σ = then A simultes sttionry overwriting trnsition of A @vines II to ISAF pormllyD it selets trnsition (p , γ, 0) ∈ δ(p, σ)D where p is the stte stored in frontierStateD updtes the vrile frontierState with p D nd overwrites the ell ontent with (γ, h) where h ∈ T is de(ned s follows ording to the vlue q ∈ Q ⊥ of tableStateF sf T = {0, 1} then h = 1 if µ(ρ) = (ν(ρ), q) nd h = 0 otherwiseF sf T = Q ⊥ then h = qF st then repets the proedure with the updted reltive frontierF sn the se ρ = -1D the window is shifted to the rightD in suh wy tht the hed is positioned on the rightmost ell of its left lokF his is formlly done y setting the reltive position to( -1, l) nd the reltive frontier to 0F3.2.3. Implementation details for the auxiliary operations and proceduresThe operation selectTransition yur suroutines simulateLeft nd main use si opertion nmed selectTransition @vines II nd PPAF his opertion tkes stte p ∈ Q nd symol σ ∈ Γ s rgumentsD nd returns tuple (q, γ, d) ∈ δ(p, σ)F hen no suh trnsition existsD it returns (⊥, σ, 0)F xotie tht the opertion is nondeterministi onlyIT if A is nondeterministiFThe operation write sn our simultionD A overwrites symols in Σ with symols in (Γ \ Σ) × T y performing n opertion nmed writeF his opertion tkes two rgumentsDγ ∈ Γ \ Σ nd r ∈ Q ⊥ F hen T = {0, 1}D it ompres r to the stte q suh tht µ(i) = (ν(i), q)where i is the index of the urrent reltive positionF sf r = q then the symol (γ, 1) is writtenD otherwise @inluding the se r = ⊥A the symol (γ, 0) is writtenF hen T = Q ⊥ D the routine simply overwrites the ontent of the urrently snned ell with (γ, r)FThe subroutine readFromTable his suroutine ws introdued in etion QFPFIF st is used to prevent the hed of A to move to the portion of the tpe on the left of the urrent windowF st is lwys lled from the leftmost position of the windowF sn prtiulrD this position is the (rst one of frozen lok x ∈ (Γ \Σ) D supposed to ontin on its seond trk the enoding of the tle τ tht desries the possile omputtion segments to the left of the windowF he routine tkes glol vrile var s rgumentD initilly ontining stte p ∈ QF he proedure opertes in two modesF pirstD it moves the hed rightwrd until rehing position i of x suh tht ν(i) = pF eondD it moves the hed kwrd to the (rst position of x nd hltsF hen swithing from the former to the ltter mode t position iD the vrile var is updted with n element q ∈ Q ⊥ D whih is dedued from the snned symol (γ, t) ∈ (Γ \ Σ) × T D nd the urrent reltive position iD s now explinedF sf T = {0, 1} thenD ording to whether t equls 0 or 1D q is equl to ⊥ or is the stte suh tht µ(i) = (ν(i), q)D respetivelyF sf T = Q ⊥ then q is equl to tF sn the nondeterministi seD suh position i is nondeterministilly hosenF sn the deterministi seD howeverD A n selet the position i deterministillyF sndeedD when T = Q ⊥ D there exists extly one i suh tht ν(i) = qF yn the other hndD when T = {0, 1}D severl suh indies my existD ut t most one is suh tht the symol (γ, t) written t the orresponding position stis(es t = 1D y determinism of eF sn this ltter seD IU when no suh i existD the proedure sets the vrile var to ⊥F husD the routine deterministilly (nds this positionD nd returns the imge q ∈ Q ⊥ of p y the functional tle τ written on xF Lemma 2. The procedure readFromTable can be implemented using 2 states, not counting the global variables var and relativePosition. Furthermore, the implementation is deterministic whenever A is deterministic. Proof. sn ll the ses desried oveD the proedure needs only one stte to move the hed rightwrd until (nding the orret informtionD nd seond stte to move the hed k to the initil positionD nmely to reltive posiE tion (0, l)F he reovered informtion is diretly stored in varF The subroutine simulateLeft his suroutine ws introdued in etion QFPFIF st is used to updte the vriles frontierState nd tableState efore visiting the frontier ellF reneD the routine hs two llEmodesX one for updting frontierState strting from one ell to the left of the frontierY the other one for updting tableState strting from the rightmost ell of the left lok of the windowF vet us denote y var the vrile to e updted nd y (i, s) the reltive poE sition from whih the routine is lledF vet zxy ∈ (Γ \ Σ) * e the projetion on (Γ \ Σ) ∪ { } of the tpe ontent up to the strting positionD with x orE responding to the left lok of the urrent windowF huring the omputtionD simulateLeft hs ess to the ontent of the window up to position (i, s)F st silly performs diret simultion of A on the orresponding prt of the tpeD nd uses the proedure readFromTable in order to simulte omputE tions tht our to the left of the windowD s explined oveF woreoverD if rightwrd trnsition (q, γ, +1) ∈ δ(r, γ) from the lst position of zxy hs to e simultedD then the proedure hlts without performing the right moveD nmely IV Procedure 2: simulateLeft(var) /* the variables relativePosition and relativeFrontier are not indicated and are supposed to be automatically updated */ Input: a variable var in read/write mode, initially containing a state in Q Output: halts with var containing a state or the special symbol ⊥ 18 let (i, s) = relativePosition 19 clock ← 2 n 20 while var = ⊥ and clock > 0 do 21 let γ ∈ Γ \ Σ be the rst track symbol of the currently scanned cell 22 let (q, γ, d) = selectTransition(var, γ) relativePosition = (i, s) and d = +1 then 27 break 28 else if relativePosition = (0, l) and d = --1 33 if clock = 0 then var ← ⊥

is 2 •

 2 (2 n • 3 + 1)D not ounting the glol vriles varD relativePositionD nd relativeFrontierF 3.2.4. Sipser's simulation hen the simulted 1-la A is deterministi it is possile to use (ner implementtion of simulateLeftD thus voiding the sizeEexpensive lokF his (ner implementtion is n dpttion of onstrution due to ipserD tht voids deterministi loops in deterministi uring mhines y lever kwrd simultion ISF e version for 2dfas hs een presented in ITD where it is shown tht liner inrese of the size is su0ient for simulting ny 2dfa with hlting equivlent oneF e (rst rell the min ides of this simultion nd then we show how it n e dpted for implementing the proedure simulateLeftF PI vet B e 2dfaF ithout loss of generlity @see ITD vemm QFIAD we n suppose tht B nnot perform sttionry movesD tht it hs extly one (nl stte q F D tht eptne is mde y entering q F t the leftmost positionD nmely on the left endmrkerD nd tht furthermore no trnsition n e performed from tht pointD i.e.D from stte q F reding F henD given n input word wD we onsider the conguration graph G of B on wD nmely the direted grph suh tht the verties re the on(gurtions of B on w nd there is n edge from c to c if c c F sn prtiulrD w is epted y B if nd only if there exists pth in G from the initil on(gurtion c I to the unique (nl on(gurtion c F F vet us fous on the onneted omponent of c F F ine B is deterministi nd euse c F hs no suessor y ssumptionD this omponent is tree rooted in c F F woreoverD w is epted if nd only if c I ours in this treeF reneD y performing depthE(rstEserh in the treeD one n hek whether c I is in the omponentD nd thus deide whether the word w is eptedF his depthE(rstE serh ide n e implemented deterministillyD strting from c F D using four opies of eh stte onlyF his yields (4 • #Q B )Estte hlting 2dfa whih is equivlent to BD where Q B denotes the stte set of B ITF st should e notied tht when c I does not elong to the treeD the simulting hlting 2dfa hlts in on(gurtion tht mthes the root c F fter hving tried ll its sutreesF e shll dpt this onstrution to our seD for implementing the proedure simulateLeftF xotie tht the diret simultion of A on the orresponding frozen portion of the tpe is redEonly deterministi omputtionF ememer tht simulateLeft n operte in two llEmodesF vet us (x one of these two modesF e denote y var the vrile to updteD y p its initil ontentD y (i, s) the strting reltive positionD nd y ρ the reltive frontierF vet zwX e the ontent of the tpe to the left of the strting positionD with z eing the portion to the left of the window nd |X| = 1F

  ⊥ otherwiseY where k is the rightmost position of the left lok of the windowF gonverselyD updting frontierState in A is done only y performing diret simultion of A tht my red some tle τ D whih hve previously e writE ten on the frozen ontent of the tpeF fy indution on the frontier positionD we n prove tht τ is reltion inluded in τ x0•••x k-D where k is the rightE most position of the left lok of the windowF @e further hve τ = τ x0•••x k- when A is deterministiFA reneD every stte reovered through readFromTable nd simulateLeftD orrespond to stte tht n e entered y A from the orresponding on(gurtion t the orresponding positionF husD for eh E epting omputtion of A D one n (nd simulted epting omputtion of AD whene L (A ) ⊆ L (A)F e hve shown how A simultes A in hlting mnnerD y shifting virtul window to the right during its omputtionD nd y restriting lol hed moves to the urrent window of size 2 F e now evlute the size of A F e point out thtD s long s A is deterministiD the two possile enodings of the hepherdson tlesD nmely using T = {0, 1} nd = n 2 or using T = Q ⊥ nd = nD re possileF por othD the ipser simultion yields smller size inrese with respet to the lok trik used for the generl seF hough in the deterministi seD the smllest simulting 1-la is otined y omining the seond enoding with ipser simultionD it should e notied tht using the (rst enoding yields smller working lphetD whose size does not depend on nF Lemma 6. A has polynomial size with respect to A. More precisely, we obtain the following simulation costs: Sipser/ = n O(n 4 ) (n + 1) • #(Γ \ Σ) PT Proof. he set of working symols of A is Γ \ Σ = (Γ \ Σ) × T F sn oth nondeE terministi nd deterministi sesD the (nite ontrol uses severl omponentsX the vrile relativeFrontier of size Y the vrile relativePosition of size 2 -1 @the vlue ( -1, r) is never usedD sine the reltive position is lwys to the left of the reltive frontierAY the vrile frontierState of size n @the vlue ⊥ is unneessryD sine upE dting frontierState with ⊥ implies rejeting the inputAY the vrile tableState of size n + 1Y the stte omponents used to implement simulateLeft of sizeX 12 n + 2 using the lok @generl seD see etion QFPFQAY QH using ipser9s onstrution @deterministi se onlyD see etion QFPFRAF sn oth sesD the size inludes the two suEmodes used in the implemenE ttion of the routine readFromTableD cf. vemm PF vet us now evlute the time used y the simulting mhine A F Lemma 7. In every computation of A , each tape cell is visited a number of times which is bounded by some polynomial in the size of A. Proof. vet us (x ell cF es A is loopEfreeD eh time the hed visits c it must hve di'erent stte or di'erent tpe ontentF e tpe modi(tion etween two visits of c is restrited to ells from the right lok of the urrent window ontining cF he numer of suessive tpe modi(tions in window is ounded y F sndeedD fter overwritings the window is shiftedF he ell c my our in two suessive windowsX (rst in the right prt ndD fter shifting the windowD in the left prtF husD the numer of visits to the ell c is ounded y 2 n D where n is the numer of sttes of A D whih is polynomil in the numer of sttes of A s seen in vemm TF he numer of visits to eh ell is hene ounded y polynomil in the size of AF es onsequeneD A opertes in liner time with respet to the input lengthF PU e n oserve thtD y the use of the stte omponents relativePosition nd relativeFrontierD our simulting 1-la lwys knows where the frontier isF oughlyD this mens tht A does not use the metEinstrution move rightwrd until (nding the leftmost ell tht hs not een visited so fr whih ws used y the 1-la desried in ixmple IF Lemma 8. A knows where the frontier is, namely, there exist special states that are entered exactly when visiting a tape cell for the rst time. Proof. sn roedure ID when entering the frontier ell @vine WAD the simulting devie enters prtiulr mode from whih the ell is snned @vine IHA in order to simulte sttionry overwriting trnsition of A @vines II to ISAF reneD we n exhiit the set of sttes orresponding to this speil modeF 4. Main Result and Consequences e re now le to stte our results s onsequenes of the properties of A stted in etion QFQF ee pigure I for summry of these resultsF 4.1. Main Result: Conversion into Linear-Time 1-Limited Automata yur min result shows tht operting in superEliner time is not essentil for 1-lasD if llowing polynomil inrese in the numer of sttesF Theorem 1. Each 1-la (resp. deterministic 1-la) admits an equivalent lineartime 1-la (resp. deterministic 1-la) of polynomially larger size. Proof. e strt with 1-laF fy pying liner inrese of its size nd preE serving determinismD we trnsform it into n equivlent 1-la A whih performs sttionry moves extly when rewriting ell ontentD y vemm IF hen we pply the ove onstrution in order to otin the 1-la A equivlent to AD y vemm SF sf A is deterministi then so is A F fy vemm TD the size of A is ounded y some polynomil in the size of AF fy vemm UD A opertes in liner time in the length of the inputF PV 4.2. Conversion into Weight-Reducing Hennie machines vinerEtime 1-las re prtiulr ses of rennie mhines @i.e.D linerEtime liner ounded utomtAD heneD it follows from the ove result tht ny 1-la n e trnsformed into rennie mhine with polynomil inrese of the size onlyF sing vemm UD we n tully otin the stronger result tht the 1-la n e trnsformed into weight-reducing Hennie machine of polynomil sizeF snformllyD weightEreduing rennie mhines re rennie mhines in whih eh overwriting is deresing with respet to some (xed order on the working lphetF es onsequeneD fter overwriting ell with miniml symolD suh mhine nnot visit the ell ginF ee T for forml de(nition nd study of the modelF Theorem 2. Each 1-la (resp. deterministic 1-la) admits an equivalent weightreducing Hennie machine (resp. deterministic weight-reducing Hennie machine) of polynomial size. Proof. pollowing TD vemm RD it is enough to modify the 1-la A otined y the ove onstrutionD in suh wy tht eh time frozen ell is visitedD it is overwritten with opy of the frozen symolD tht enodes the numer of visits to the ellF ineD y vemm UD the totl numer of visits of ell in omputtion of A is ounded y some polynomil in the size of AD the trnsformtion yields n equivlent weightEreduing rennie mhine whih hs polynomil size with respet to the simulted 1-laF purthermoreD the onverE sion lerly preserves determinismF 4.3. Conversion into Two-Way Automata with Common Guess ome 1-las hve prtiulr ehviorD whih n e deomposed into two phsesF sn the (rst phseD they nondeterministilly rewrite the ontent of the whole tpe during leftEtoEright trversl of the inputF henD in the seond phseD they perform twoEwy redEonly omputtion over the overwritten tpeF o formlly de(ne this kind of 1-lasD we introdue the following modelF PW Denition 3. A 2nfa (resp. 2dfa) with ommon guess ( 2nfa+cg, resp. 2dfa+cg) 3 is a tuple A, Σ, ∆ where Σ and ∆ are two alphabets and A is a 2nfa (resp. 2dfa) over the product alphabet Σ × ∆. he model is imed to reognize lnguges over ΣF sts dynmis is de(ned s for twoEwy utomtD ut nondeterministi preEomputtion initilly mrks eh input symol with symol from ∆F 4 reneD the redEonly utomton A hs ess to oth the input symol nd the guessed dditionl informtionF he lnguge eptedD denoted L ( A, Σ, ∆ )D is de(ned s the projetionD deE noted π 1 D of L (A) on the lphet ΣD i.e.D L ( A, Σ, ∆ ) = π 1 (L (A))F sn other termsD word is epted y A, Σ, ∆ if for some guessD the enrihed word in (Σ × ∆) * is epted y AF e point out thtD due to the ommon guessD 2dfa+cg9s re nondeterministi deviesF vet us detil the onnetion etween 1-las nd 2fa+cgsF st is esy to turn 2fa+cg into n equivlent nondeterministi 1-la of the sme sizeD y simply guessing nd writing the symols from ∆ when visiting the ells for the (rst timeF st is however a priori not ler whether onverse trnsformtion with resonle size ost existsF he min issue for suh onversion is thtD t ny time during omputtion of 1-laD position of the tpe is identi(ed s eing the leftmost ell tht hs not een visited so frD nmely the urrent frontierF sn prtiulrD 1-la n use metEinstrutions mking use of this identi(ed positionD suh s move the hed rightwrd to the frontier ellD s it is the se in ixmple IF xeverthelessD when 1-la does not use suh kind of instrutionsD tht isD if it lwys knows when it enters ell for the (rst time @efore snning its ontentAD then it is esy to onvert it to n equivlent 2fa+cg of similr sizeF pormllyD the property of lwys knowing where the 3 2dfa+cgs also correspond to synchronous two-way deterministic nite veriers [17].

  1-la AD we n otin n equivlent 2nfa+cg y heorem QF fy repling left move y right move nd vice versa on eh trnsition of its underlying utomtonD we n otin 2nfa+cg of sme sizeD whih reognizes L (A) r F his 2nfa+cg n in turn e viewed s nondeterministi 1-laF 4.4. Lower bounds gonerning the size ost of the simultion of 2dfa+cg y deterministi 1-laD using the lnguge L n from ixmple ID we n prove n exponentil gp in the deterministi seF Theorem 4. Let L n be the language of Example 1. HenceL n r = {x k x k-1 • • • x 0 | k ∈ N, for each i : x i ∈ {a, b} n , for some j = 0 : x j = x 0 }.Then, 1. L n r is accepted by a 2dfa+cg, a linear-time nondeterministic 1-la, or a deterministic weight-reducing Hennie machine of size polynomial in n; 2. any 1dfa recognizing L n r requires 2 2 n states; 3. any deterministic 1-la recognizing L n r requires O(2 n ) states. Proof. ixmple I desries deterministi 1-la reognizing L n D whose size is liner in nF fy pplying heorems P nd QD we respetively otin equivlent deterministi weightEreduing rennie mhine nd 2dfa+cg of polynomil sizeF foth models n e trnsformed with t most liner inrese in sizeD in orderto ept the reverse of the lngugeD thus proving stem IF por oth modelsD it is indeed enough to initilly move the hed to the right endmrkerD nd then simulte the twoEwy devie in opposite diretionD tht isD repling left moves of the hed y right ones nd vice versaF sn the se of 2dfa+cg this yields onstnt inrese of the size of the model @only one stte should e dded for the initil modeAF sn the se of weightEreduing rennie mhinesD sine during the initil trversl of the input the ells should e overwritten in deresing wy QP @in order to preserve the weightEreduingness propertyAD we should in ddition dd fresh opy of eh input symol to the set of working symolsF sing simple distinguishility rgumentD we n prove stem PF pinllyD stem Q n e dedued from this previous point nd the exponentil upper ound for the size ost of the simultion of deterministi 1-la y 1dfa given in IIF P tF iF roproftD tF hF llmnD sntrodution to eutomt heoryD vnguges nd gomputtionD eddisonEesleyD IWUWF Q pF gF rennieD yneEtpeD o'Eline uring mhine omputtionsD snformtion nd gontrol V @TA @IWTSA SSQ!SUVF R uF dkiD F mkmiD tF gF rF vinD heory of oneEtpe linerEtime uring mhinesD heorF gomputF iF RII @IA @PHIHA PP!RQF S qF ighizziniD xondeterministi oneEtpe o'Eline uring mhinesD tournl of eutomtD vnguges nd gomintoris IR @IA @PHHWA IHU!IPRF T hF r•²D eightEreduing rennie mhines nd their desriptionl omE plexityD inX vee PHIRD olF VQUH of veture xotes in gomputer ieneD PHIRD ppF SSQ!STRF QQ U F xF rirdD e generliztion of ontextEfree determinismD snformtion nd gontrol II @IGPA @IWTUA IWT!PQVF V qF ighizziniD eF isoniD vimited utomt nd ontextEfree lngugesD pundment snformtie IQT @IEPA @PHISA ISU!IUTF W wF uutriD qF ighizziniD wF endlndtD hesriptionl omplexity of limE ited utomtD snfF gomputF PSW @PA @PHIVA PSW!PUTF IH uF F gnerD qF ehsungD gomputtionl gomplexityD hF eidel uE lishing gompnyD hordrehtD IWVTF II qF ighizziniD eF isoniD vimited utomt nd regulr lngugesD snternE tionl tournl of poundtions of gomputer iene PS @HUA @PHIRA VWU!WITF IP qF ighizziniD vF rigionieroD vimited utomt nd unry lngugesD snE formtion nd gomputtion @PHIWAF doi:https://doi.org/10.1016/j. ic.2019.01.002F IQ wF foj«zykD vF hviudD fF quillonD F enelleD hih lsses of origin grphs re generted y trnsduersD inX sgev PHIUD olF VH of vsssD PHIUD ppF IIRXI!IQF IR tF gF hepherdsonD he redution of twoEwy utomt to oneEwy uE tomtD sfw tF esF hevF Q @PA @IWSWA IWV!PHHF IS wF ipserD rlting speEounded omputtionsD heoretil gomputer iene IH @QA @IWVHA QQS ! QQVF IT F qe'ertD gF wereghettiD qF ighizziniD gomplementing twoEwy (nite utomtD snfF gomputF PHS @VA @PHHUA IIUQ!IIVUF IU gF eF upoutsisD redite hrteriztions in the polynomilEsize hierrE hyD inX vngugeD vifeD vimits E IHth gonferene on gomputility in iuE ropeD gii PHIRFD olF VRWQ of veture xotes in gomputer ieneD pringerD PHIRD ppF PQR!PRRF QR

Acknowledgments e re very indeted to qiovnni ighizzini for suggesting the prolem nd for mny stimulting onverstionsF References References I fF quillonD vF rigionieroD vinerEtime limited utomtD inX hgp PHIVD olF IHWSP of veture xotes in gomputer ieneD pringerD PHIVD ppF IPT! IQVF


Sébastien Clerbois
email: sebastien.clerbois@ulb.be.

Nadine Mattielli
email: nmattiel@ulb.ac.be.

Antoine Triantafyllou
email: antoinetri@gmail.com.

Gaël Brkojewitsch
email: gaël.brkojewitsch@gmail.com

THE ROMAN GRANITE QUARRIES IN THE TYRRHENIAN SEA DURING THE IMPERIAL PERIOD: A TECHNOLOGICAL STUDY

Keywords: Stone extraction, Roman Quarries, Archaeology, Technology, Tyrrhenian Sea

Granite is a highly valued material under imperial Rome, particularly the production of monolithic columns, used in both public and private architecture. In the western Mediterranean, the main quarries are located around the Tyrrhenian Sea. The Romans were looking for a particular stone, i.e. leucocratic granodiorite, with colors and textures similar to that extracted from the Egyptian quarries of Mons Claudianus, used for many imperial programs. The extraction of large columns in such a hard material requires proper organization and techniques. This paper aims to study the granite exploitation of granite in the Tyrrhenian Sea from a technological point of view, along the entire chaîne opératoire, from sites prospection to extraction, block cutting and production of finished objects. This contribution also seeks to understand how geological patterns have been advantageously exploited by quarrymen, and to identify sets of technical features to explain their origin and systematics, in a local and regional context. In the absence of absolute dating, technology is also useful to make phasing hypotheses, given that many of these quarries have been used from antiquity to the present day. From a methodological point of view, the approach combines technology and geological observations to produce a holistic study of the stone, from its characterization to its exploitation.

INTRODUCTION

The production of granite monolithic columns, particularly valued in imperial architecture, is at the heart of Roman-style luxury. On one hand, the great imperial programs, particularly from the Antonine period (EDMUND 2007) (RÖDER 1959;RÖDER 1965;BESSAC 1986, KOŽELJ 1988;KOŽELJ, WURCH-KOŽELJ 1992;BESSAC 1996;KOŽELJ, WURCH-KOŽELJ 1998;BESSAC 2000;2014;BABIST, VÖGEL, GNIRß).

Nevertheless, except for the Mons Claudianus case studies (PEACOCK, MAXFIELD 1997), theses quarries have never been surveyed with stratigraphic excavations and, hence, with a detailed archaeological investigation, particularly in the Tyrrhenian Sea. This is most likely due to their location on coasts, islands or peninsulas making them difficult to access.

In addition, erosion processes in coastal These ones can be identified as thresholds and millstones, attesting that these particular objects were also extracted.

These millstones do not correspond to the Roman typology and would evidence a subsequent exploitation of the quarry in modern or contemporary times .

In Nicotera, several large basins were observed in addition to the columns (FIG. 7), possibly contemporary. In San Bainzu, a punctual extraction in a part of the quarry produced some tympana, probably during the modern times (FIG. 8).

In Municca, blocks of a very particular format, which we believe to be quay borders, were also extracted during modern or contemporary times (FIG. 9).

C. A SINGULAR MODUS OPERANDI?

The quarrying techniques widely used in the Roman times to produce granite monolithic columns consist in cutting the block at a given dimension on three sides using extraction trenches. This block is then extracted from the bench using a series of sockets (called «emboîtures» in French; translations based on ABDUL MASSIH, BESSAC 2009). These sockets are intended to receive the wedges, that will be driven into the stone until it cleaves along a straight line (FIG. 10). In order to produce a column, the quarryman had to either extract a parallelepiped block which was used to carve a column once extracted, or to shape the column directly on the bench. These two techniques have been highlighted and described in the imperial quarries of Mons Claudianus (PEACOCK, MAXFIELD 1997, 177-216).

In the Tyrrhenian quarries, such a modus operandi is however poorly documented. If we can distinguish at least two phases of

Similarly, in the

  , exploited these rocks on a colossal scale and sublimated the stone through monumentality. Several examples include e.g. the columns of the Ulpian basilica in the forum of Trajan or the Corinthian columns of the Pantheon built under Hadrian, with impressive proportions (shafts of 12.5 m high, 1.5 m in diameter at the base and 69 tons each). These imperial commissions contributed to popularize the use of granite in architecture among the elite of society. On the other hand, granitic rocks, that were assimilated to marbles by the Romans, contributed to the taste of the elite for the polychromy due to the lithological variety of the quarried stones (DE NUCCIO, UNGARO 2002; BRADLEY 2006). Indeed, either in public or private Roman architecture, granite columns offered beautiful color variations from white to grey, pink or red, with subtle speckled patterns due to grainsize and heterogeneous compositions enhanced by polishing. This stone trade is supported by the large amount of granite quarries during the imperial period. These quarries were foro) in the eastern desert of Egypt (Aegyptus), those of Kozak Dağ, in northwest Turkey (Marmo Misio, Mysia), of Hadjret-en-Nous (Algeria, Mauretania Caesariensis) or, among others, those of the Strait of Bonifacio (Corsica-Sardinia) in the western Mediterranean Sea.

  the authors have taken part in a Collective Research Program (PCR, 2017-2020) promoted and funded by the Ministry for a holistic understanding of stones' exploitation. Their research was focused on the study of granite quarries scattered throughout the islands of the Lavezzi archipelago in Corsica, including the large quarry located on the contiguous islands of Cavallo-San Bainzu. As part of this program, in addition to the Corsican quarries, namely those of Cavallo-San Bainzu and Lavezzu (I Becchi and Cala Giunco) located in the Lavezzi archipelago, a large panel of known granite quarries in the Tyrrhenian Sea was visited for comparative purposes. The latter ones include those of North Gallura (Punta Falcone, near the town of Santa Teresa di Gallura. We also visited the Calabrian (Italy) quarries of Parghelia and Nicotera, within the Capo Vaticano (FIGS. 1-2) although our understanding of these exceptional sites is partial due to the invasive vegetation and the absence of heritage maintenance. The Sardinian quarry of Cala di l'Ea, on Capo Testa, and those of Elba and Giglio (FIGS. 1-2), are more complex because of their apparent reexploitation during medieval and modern times. These case studies require an indepth field investigation and will therefore be the subject of a separate publication. Our study aims at documenting and studying the visible traces of extraction in these quarries; exploring and conducting a technological study of these markers, witnesses of former extraction techniques, provide a robust scientific basis for any further archaeological interpretation.

Felsberg(

  FIG. 14). In general, the negative imprints of these furrows' trenches are visible on most of the working faces of the studied quarries (FIG. 15). Why shaping columns from granite's parallelepipeds after their extraction? In terms of profitability, this choice probably implies more work. On the other hand, the separation between the phase of block's extraction and the shaping of the columns induces a division of work which most likely allows a better work organization and eventually a good profitability. The work of shaping a granitic column is long and tedious. Shaping columns directly into


Elodie Pillon

Mourad Messaadia

Anne Louis

Proposition of assessment model for open innovation adoption in SMEs

-Used methodology:

However, open innovation is not a universal character and must be adapted to the SME's profile. In this work, we propose to identify factors that affect the open innovation adoption capacity in SMEs.

  model for open innovation adoption in SMEs Elodie PILLON 1 & 2 , Mourad MESSAADIA 1 , Anne LOUIS 1 1 CESI LINEACT -1 rue Marconi -76130 Mont-Saint-Aignan -France ² NIMEC Caen -3 rue Claude Bloch -14075 Caen -France 1 -Problem statement: For SMEs, it is difficult to access to the resources needed for innovation. Also, developing collaboration between SMEs and various entities has become indispensable for SMEs. The concept of open innovation emphasizes the importance of resources from inside and outside the firm boundaries in the aim to capture and create value (Chesbrough, 2006).

-Adoption factors of open innovation:

-Conclusion:Implementing open innovation within a

structure entails significant impacts on the organization itself and on its management (Dodgson, Gann, & Salter, 2006) Also, establishing the appropriate complementarity of internal and external resources is critical in unlocking innovation.

The implementation of the change requires an experimental field where the best solutions need to be identified.

In this context, we identified factors that impact the open innovation adoption capacity in SMEs.

-Perspectives:

We would like to validate the proposed model through a survey where each question will be the translation of each indicator.

Also, the positive or negative impact of some indicators was not determined and need to be studied. Our future case studies will help us to identified their impact.

This model will be used to develop a tool for SMEs to assess their ability to adopt an open innovation process.

Strategy Knowledge

Organization Environment