Linear cellular automata and Fischer automata

LinearCellularAutomataandFisherAutomataKlausSutnerCarnegieMellonUniversityPittsburgh,PA15213sutners.mu.edu~sutnerAbstratWestudythesizesofminimalnitestatemahinesassoiatedwithlinearellularautomata.Inpartiular,weonstrutalassofbinarylinearellularautomatawhoseorrespondingmini-malautomataexhibitfullexponentialblow-up.TheseellularautomatahaveHammingdistane1toapermutationautomaton.Moreover,theorrespondingminimalFisherautomataaswellastheminimalDFAshavemaximalomplexity.Byontrast,theomplexityofhigheriteratesofaellularautomatonalwaysstaysbelowthetheoretialupperbound.1IntrodutionEverylinearellularautomatonanbeassoiatedwitharegularlanguageL()ofnitewords:L()istheolletionofallnitesubwordsofongurationsthatariseafteroneappliationoftheglobalmapoftheellularautomaton.Disussionsofthelanguagetheoretiaspetsoflinearellularautomataandsosystems,inpartiularwithrespettotheirrelationtothetopologyofthespaeofongurations,anbefoundin[8℄,[10℄and[7℄.Inthispaper,wewillstudytwomeasuresofomplexityassoiatedwithL()thatarebasedonminimalnitestatemahinesofaertaintype.TherstissimplythesizeoftheminimalautomatonforL(),or,equivalently,thenumberofleftquotientsofthislanguage.Fortheseondmeasure,oneanexploitthefatthethelanguagesL()arenotonlyregularbutalsofatorialandtransitive.Asaonsequene,thereisadeterministi,transitivesemiautomatonthataeptssuhalanguage,see[3℄.Werefertoanydeterministi,transitivesemiautomatonasaFisherautomaton.WewillshowthatthereisanaturalembeddingoftheminimalFisherautomatonintotheminimalautomaton.Infat,1theminimalFisherautomatonturnsouttobeastronglyonnetedomponentoftheminimalautomaton.Theomponentisharaterizedbythefatthatithasexitsonlytothesinkoftheminimalautomaton.Theotheromponentsoftheminimalautomaton,iftheyexist,onstruedassemiautomata,aeptpropersubsetsoftheaeptanelanguageofthewholemahine.ThisexplainsanobservationbyWolframthattheminimalautomatonassoiatedwithalinearellularautomatonmayontainadditional\transientsubgraphs,see[24℄.ItwasshownbyBeauqier[2℄thattheminimalFisherautomatonisalsominimalinthesenseofhomomorphisms:thereisahomomorphismfromanyFisherautomatonforaxedtransitivefatoriallanguagetotheminimalFisherautomatonforthatlanguage.ThisworkismotivatedinpartbyaproblemposedbyWolframin[26℄.TheiteratestofalinearellularautomatondeneadesendingsequeneofregularlanguagesL(t).Wolfram’sempirialstudiesledhimtotheonjeturethattheomplexityoftheselanguagesisingeneralnon-dereasing.Asamatteroffat,itappearsthatformostWolframlassIandIIautomata,(t)inreasespolynomially,butforlassIIIandIV,omplexitiesinreaseexponentially.Atableof(t)forelementaryellularautomataanbefoundin[24℄.Itisnotedinthereferenethat(t)\usuallystaysfarbelowtheupperbound.Toseewhatthisupperboundis,notethatthereisatransitivesemiautomatonB()thataeptsL()whoseunderlyingdiagramisadeBruijngraph.ThisdeBruijnautomatonhaskw1statesandkwtransitionswherekisthesizeofthealphabetandwthewidthoftheloalmapofthelinearellularautomaton.Hene,ifwelet()besizeoftheminimalautomatonforL(),weimmediatelyobtaintheupperbound()2kw1.Itfollowsthattheiteratesofobeythebound(t)2kt(w1).LetuswriteF()forthesizeoftheminimalFisherautomatonforL().FromourembeddingresultforFisherautomata,wehaveF()().EqualityoursonlyinthetrivialaseF()=()=1,i.e.,whenL()=.Byompatness,thelatteronditionisequivalentwiththeglobalmapoftheellularautomatonbeingsurjetive.Thus,fornon-surjetiveglobalmaps,wehave1F()()2kw1:Wewillonstrutafairlylargelassofbinaryellularautomataofarbitrarywidththatshowsthatbothboundsaretight:fortheseellularautomatatheorrespondingminimalautomatonhassize22w1,andtheorrespondingminimalFisherautomatondiersinonlyonestate,thesinkoftheminimalautomaton.Theellularautomataareonstrutedfromapermutationautomatonbyhangingthelabelofonetransition.Thus,theyhaveHammingdistane1tothenearestpermutationautomaton.WewillseethatanyellularautomatonwithHammingdistanelargerthan1failstohaveFisherautomataofmaximalsize.Itisquitestraightforwardtoshowthatinpartiulartheiteratest,t2,ofanynon-permutationautomatonallmusthaveHammingdistanelargerthan1tothenearestpermutationautomaton.Therefore,theregularlanguages2assoiatedwiththeseellularautomataexhibitarelativedereaseintheiromplexity.Ingeneral,thereappearstobearatherloseonnetionbetweentheHammingdistaneoftothenearestpermutationautomaton,andthesizeoftheminimalautomaton,butweareurrentlyunabletogiveadetailedanalysis.NotethataellularautomatonwhosedeBruijnautomatonB()isapermutationautomatonissurjetive,infat;theglobalmapisopen.SurjetivityoftheglobalmapisalsoequivalenttoastrongbalanepropertyofB():everywordhastohavethesamemultipliityinB(),see[4℄and[16℄.Inpartiular,thenumberoftransitionsinB()labeledbyanypartiularsymbolinthealphabetisthesameasforanyothersymbol.ItwassuggestedbyLangtontousethesimplenumerialparameter():=kwk0kwasameasurefortheomplexityofaCA,see[13℄,[12℄,[11℄andalso[14℄.Herek0:=j1(0)jisthenumberofwordsmappedtothequiesentstate0bytheloalmap.Langtonstudiedrandomlygeneratedellularautomataanditappearsthatautomatawhose-valuesareneararitialva