; TeX output 2003.04.10:1355Y[n썍YٓRcmr71ǼN cmbx12UPDATEٚSCHEDULESOFSEQUENTIALDYNAMICALSYSTEMSk4$K`y cmr10REINHARDUULAUBENBACHERANDBODOP*AREIGIS6 $- cmcsc10Abstract.\`Sequential_,dynamicalsystemshavethepropGerty*,athattheupGdatesofstatesof $individualNcellsoGccursequentially*,sothattheglobalupdateofthesystemdependsonthe$order oftheindividualupGdates.Thisorderisgivenbyanorderonthesetofverticesof$the depGendencygraph.Itturnsoutthatonlyapartialsuborderisnecessarytodescribe$thepglobalupGdate.[&Thispaperde nesandstudiesthispartialorderanditsin uenceonthe$globalUUupGdatefunction.s- cmcsc10Introduction*XQ cmr12Thetheoryofsequenrtialdynamicalsystems(SDS)was rstintroSducedin[1,2 ,3],Ėwiththegoalpofprorvidingamathematicalfoundationforcomputersimulations.-SuchafoundationwillallorwarigorousmathematicalanalysisofavXarietyofquestionsthatariseinsimulationpractice.ManrylcomputersimulationscanbSerepresentedintermsofsequentialdynamicalsystemsa(forcomputationalpurpSoses. BydesignSDSacarrymoreinrternalstructurethan,|sayV,cellularlautomata.AsaresultitispSossibletoprorvelgeneralresultsaboutSDSlrelatingtheirstructuralupropSertiestothedynamicstheygenerate.zThisrepresenrtsanimportanrt rststeptorwardanunderstandingofhorwloScalpropertiesofasystema ectglobaldynamics.*In9V[6]wregeneralizedthenotionofasequentialdynamicalsystem,Mandde nedtransforma-tions0ofSDS.Sucrhtransformationsarecompatiblewiththeinternalstructureandinduceatransformation<oftheassoSciatedstatespaces,^thatis,arecompatiblewiththedynamicsgen-erated?brythesystems.OneimpSortantrolesuchtransformationscanplayisasmathematicalformalizationsofasimrulationofoneSDSybyanother.SuchimpSortantpracticalquestionsashorwtoreducethedimensionofasimulationcanbSephrasedinthiswayV.TransformationsalsoallorwthestudyoftherelationshipbSetweenstructuralchangesinasimulationtotheresultingcrhangesinthedynamics.AsecondrolefortransformationsisinastructuretheoryofSDSasthe rststeptorwardaclassi cation.%FVorinstance,?in[6]itwrasshownthateverySDScanbSeuniquelydecomposedinrtoaproSductofindecomposableSDS,whicrhcanthenbestudiedindividuallyV.FinallyV, a}thirdroleisincomparingSDSwithotherinrterestingobjectsincomputerscienceusedforsimrulationsandascomputationaldevices.ThiscanbSedoneverywellinacategoricalframewrork,>Rand 1sKeywords: xsequentialdynamicalsystem,ymorphismofpGographs,posetmodelsofgraphs,yupdate schedules. ': cmti10Date[:UUF*ebruary19,2003. u 2000IMathematicsSubje}'ctClassi cation.Primary:37B99, 68Q65,93A30;OeSecondary:18B20,37B19,68R01.*Y[썍-o cmr92t˾REINHARDTLA9UBENBACHERANDBODOP:AREIGISn썹Recallfrom[6]thatasequenrtialdynamicalsystemisafunction Q3g cmmi12fQ:k2cmmi8nUR#u cmex10Y ㇍Si|{Ycmr8=1ki, !", cmsy10!knURY ㇍Si=1kid;!Constringsoflengthn,withenrtriesintheithcompSonentcomingfromaspSeci edsetkidڹ.&WVesimplywritekg2n d:=URQ*n U_i=1kidڹ.8ThisfunctionfQ:URkg2n ~J!Ӟkg2n isobtainedfromthefollorwingdata:č(1)%a,@ cmti12depffendency35graphFnonnvrertices;(2)%a(collectionofloffcallOupdatefunctions(fi#:kg2n |#!kg2nm,8Oi=1;:::ʜ;n,whicrh(changeonly%theithcoSordinate,andwhoseinputsareconrtrolledbythegraphFƹ,(3)%an_upffdateschedule ,consistingofawrordinnlettersa1;:::ʜ;an ٹfromthesetof%vrerticesVF ofFƹ.Thefunctionf꡹isthecompSositionofthefidڹ, intheorderspeci edbrytheupdatescrhedule .(MoredetailscanbSefoundinthenextsection.)*Itfwrasshownin[4]thatthegraphFVisimplicitintherestofthedata,ŊusingaGaloiscorrespSondencebetrweencollectionsofloScalfunctionsandgraphs,*9constructedin[5].oThus,ifexpSedienrt,thispartofthestructureofanSDSmaybSeignored.The=vfoScusinthepresenrtpaperisontheupdatescrhedule .1KRecallthattheglobalupdatefunction2oftheSDS¹isgeneratedbrycompSosingthelocalupdatefunctionsintheorderprescribSedbry .PartoftheworkrepSortedin[2,3 ]concernedtheextenttowhichchangesintheupSdatescrhedulea ecttheglobalupdatefunction,respectivrelyV,theresultingdynamicstructure.2(Inלconrtrastto[6]andthepresentpapSertheupdatescrhedulein[2,3 ]istakentobSeRapermrutationoftheindicesofthenodes,lratherthanageneral nitewrordinasubsetofithoseindices.)nItwrasshownthatsomechangesintheupSdatescheduleleavetheglobalupSdatefunctionuncrhanged.ThisissimilartoadistributedcomputationinwhichcertainstepscanbSecarriedoutinvXariousorders,whereasothersneedtobedoneaccordingtoaprescribSedgscrhedulesothattheendresultremainsunchanged. +WVewantto ndpropSertiesofan5upSdatescrheduleonwhichtheglobalupSdatefunctiondependsandotherpropertiesthatcan freelybSecrhangedwithoutchangingtheglobalupSdatefunctionandthusthedynamicbSeharviorofthewholesystem.WVe?shorwinthispapSerthatthisdegreeoffreedomintheupdatescrheduleisaveryimpSortantaspSect=ofanSDSthatdeservrestobestudiedaspartoftheexplicitstructureoftheSDS.This;leadsustopropSoseanewde nitionofSDS;whicrhincorporatesthisdicrhotomy;oftheupSdatescrhedule.TGWVewillseeinasubsequentpapSerthatsuchachangeleadstoanotionoftransformations[ofSDS[withvrerydesirablepropSerties. NInparticular,x~weobtainacategoricalframewrorkforSDSthatisrichintransformationsandstructure.InordertodescribSeandstudytheorderingofthevrerticesgivenbytheupSdatescheduleweinrtroSduceKthenotionofapffosetYmodelofagraph,canKinrterestingconnectionbSetweenpSosetsandgraphs.8LetFnbSea nitegraph(e.g.,thedependencygraphofanSDS),andlet5 h:URf1;:::ʜ;ng !VFbSe,anupdatescrhedule,i.e.tlafunctionintothesetofverticesofFƹ.tlAnyupSdateschedulea1;:::ʜ;an ѣof)SanSDS)CcanbSerepresenrtedassuchafunction.ThekeyresultofthispapSeristhatУthereexistsauniquepSosetOF andposetmodel :UROF d ~,!ӀVF ofthegraphFritogetherY[썍XoUPD9A:TE!SCHEDULESOFSEQUENTIALDYNAMICALSYSTEMSSϴ3n썹withafunction n:UROF d ~,!Ӏf1;:::ʜ;ng,i.e.aTf1;:::ʜ;ngh + JUR OFhx1 J d!!NVFO;whereF  isinrvertibleFandorderpreserving,fsucrhthat h=UR 2!K cmsy81 ]Z_ O.Thatis,wrecandecompSosethe$upSdatescrhedule 8ointoapSosetmodel /ofthegraphFƦ(calledpffograph)$andanupffdatescheffdule for35thepograph :UROF d ~,!ӀVFO.*SurprisinglyV,it;turnsoutthatthepSograph :UROF d ~,!ӀVF completelydeterminesthedynam-icalsbSeharvioroftheSDS.ConsequentlyV,wecande neSDSswonapSographOF M gF!VF aloneinsteadofonagraphFntogetherwithanupSdatescrhedule .Itkwillturnoutthatthede nitionofmorphismsofSDSdde nedonpSographsbecomesvrerynaturalandstraighrtforward.If:themap isbijectivre,4andweviewthepSosetOF asadirectedgraphviaitsHassediagram,thenU @bSecomesagraphmapwhicrhinducesanacyclicorientationonFƹ.zIn[7,pProp.1]itisYshorwnthatthereisaone-to-onecorrespSondencebetrweenYacyclicorienrtationsonagraphFonBnvrerticesandthesetofequivXalenceclassesofpSermutationsonnlettersforacertainequivXalencearelation. TheequivalencerelationisgeneratedbrymakingtwopSermutationsequivXalenrtiftheydi erbytranspSositionsofadjacentelementswhosecorrespSondingverticesarenotconnectedbryanedgeinFƹ.TheSDSde nedbyBarrettet.al., calledpSermutationSDSinb[6],useanupSdatescrhedulegivenbyapSermutation,thatis,evreryloScalupdatefunction;isusedexactlyonceinthecompSositionthatde nestheglobalupdatefunctionofthe9SDS.Itwrasshownin[3]thatfromanacyclicorientationofFonecanconstructdi erentupSdateWscrhedules ,whichallproSducethesameglobalupdatefunction.=Thatis,anacyclicorienrtationޑofFWcontainsenoughinformationtoconstructtheglobalupSdatefunction.4Thisresult2+wrasusedin[3]toderiveasharpuppSerboundonthenrumber2+ofdi erenrtglobalupdatefunctionsthatcanbSegeneratedbryvXaryingtheupdatescrhedule,qfora xedgraphFjand xedloScalupdatefunctions.InE>themoregeneralsettingconsideredhere,[thepSograph ҹ:OF ]!VF Tistakingtheplaceof4theacyclicorienrtationofFƹ.+WVewillshowthatfora xed itdoSesnotmatterwhatcrhoicewemakeforthecorrespSonding R¹inordertostudythedynamicbeharvior.#TheglobalupSdateהfunctionisindependenrtofthechoiceof .Asacorollaryweobtainaone-to-onecorrespSondence4betrweenpSographswithmelementsonagraphFandequivXalenceclassesofLupSdatescrhedulesf1;:::ʜ;mg8 v!8VFO.TheequivXalencerelationisgeneratedbysettingtrwoDupSdatescrhedules &ӹand 20 equivXalentiftheygeneratethesameglobalupSdatefunctionf J=URf "q% cmsy60 fromanryfamilyofloScalupdatefunctionsf (i)v."T1.*WSequentialdynamicalsystemsandgraphswithupda32teschedule.*FVor>theconrvenience>ofthereaderwrerepSeatthede nitionofsequentialdynamicalsystemsasxusedin[6].0{WVewillrephrasethatde nitionundersomenewpSoinrtsofview.Someofthebasicnotionsareexplainedinthefollorwing}RemarkG?1.1.XLetXbSeasetandletP(X)beitsporwerset.A LetP2(X)|P(X)bSethesubsetofalltrwo-elementsubsetsofX.A(loffopyfree, undirected)graphF2d=(VFO;EF)consistsofasetVF 4ofverticffesandasubsetEF dURP2(VFO)ofeffdges.!ŠY[썍4t˾REINHARDTLA9UBENBACHERANDBODOP:AREIGISn썹LetFnbSeagraph.8A1-neighbfforhoodN@(a)ofavrertexaUR2VF isthesetN@(a)UR:=fb2VFȍO 38O Ofa;bg2EF orV_a=bg:Let-&Z!2bSeasubcategoryofthecategoryofsets.YLet(kg[a]ja2VFO)-&beafamilyofsetsinZ ,e.g.8 nitesets.Thesetkg[a]willbSecalledthesetofloffcal35statesata.8De nenokg VX.;cmmi6FN:=K&YURa2VX.FOkg[a];!Gtheset35of(globffal)statesofFƹ.8IncaseVF is nitewithr>6elemenrtswewrite}Ѝ=kg rNѹ:=URkg[a1]:::k[arb]:WVe\usethefollorwingnotation.:ForastatexV2kg2r۹and\avrertexaV2VF we\writex[a]forthestateofthevrertexaorthea-thcompSonentofxsothatr;xUR=(x[a]ja2VFO)or)x=(x[a1];:::ʜ;x[arb]):Incasethatallkg[a]areequaltoasetk,thisde nitionreducestotheusualde nitionofk2VX.Fresp.8kg2r.*AfunctionfQ:URkg2VX.FNhz! kg2VX.FEiscalledloffcal35atai,2VF if/fG(x)[ajf ]UR=z( x[aj];:6ifDaj\6=aid;ɍ fG2iٹ(x);:6ifDaj\=aid: wherefG2iٹ(x)i=fG2iG ,۹(x[a]ja2VFO)G2kg[aidڹ]depSendsonlyonthestatesx[a]ofthosevXariablesa38thatareinthe1-neighrbSorhoodN@(aidڹ)ofthevertexaidڹ.IfVF is nitethismeansthefollorwing.8AfunctionfQ:URkg2rN h\!kg2r'isloffcal35atai,2VF if}Ѝ';fG(x[a1];:::ʜ;x[arb])UR=(x[a1];:::ʜ;x[ai1AV];fG iٹ(x[a1];:::ʜ;x[arb]);x[ai+1AV];:::;x[arb]);wherefG2iٹ(x[a1];:::ʜ;x[arb])V2kg[aidڹ]depSendsonlyonthestatesx[ajf ]ofthosevrerticesajthatareinthe1-neighrbSorhoodN@(aidڹ)ofthevertexaidڹ.*OneofthefundamenrtalobservXationsisthefollowingeasyfact. Ifa;bU`2VF 3suchthatfa;bg=UR2EF thenfawfbx.=URfb̈́fawiffaandfb areloScalfunctions.>De nition01.2.7LetFGbSeagraph.!Amap h:URf1;:::ʜ;ngn!1VF iscalledanupffdatescheduleof35lengthnforFƹ.8Apair(FS; )iscalledagrffaph35withupdateschedule꨹oraugraphFƹ.De nition1.3.Aseffquential35dynamicalsystem(SDS)ꨟY1 TonaugraphFqFc=URGTFS;(kg[a]ȍ 38 aUR2VFO);(faȍ 38 a2VFO)G}Ѝconsistsofi(1)%a niteugraphFƹ,(2)%afamilyofsets(kg[a]jaUR2VFO)inZ ,38(3)%afamilyofloScalfunctions(faY!:URkg2rN h\!kg2rȍ 38 a2VFO;fawlocalat3 a)inZ .rRemarkj1.4.TheupSdatescrhedule h:URf1;:::ʜ;ngn!1VF عofaugraphF+OofanSDSqFde nesanassoSciatedglobffal35updatefunction꨹oftheSDSFCf J:=URf (1)|:::f (n):kg rN h\!kg r: ff< 1@Subsequently*,UUwewillusetheacronymSDSforpluralaswellassingularinstances.4Y[썍XoUPD9A:TE!SCHEDULESOFSEQUENTIALDYNAMICALSYSTEMSSϴ5n썹FVorAthemomenrtweconsideranupSdateschedulejustasanadditionalstructureofthegraphused|inthede nitionofanSDS.WVewillcallthegraphFMwiththis(orpSossiblyanother)additionalbstructureonwhicrhanSDSbbisde nedthe^bffasisofthegivenSDS.Surprisinglyamapz ]ǹ:J8f1;:::ʜ;ngc!VF عinducesaninrterestingadditionalstructureonthegraphFOthatwrewillsubsequentlystudyV. rh2.2Posetmodelsofgraphs*InthissectionwreshowtherelationshipbSetweenagraphwithupSdatescheduleandanassoSciated 5partiallyorderedsettogetherwithacertainmapinrtothegraphwhichwecallapffoset35modelofFƹ.*LetO?bSeaposet(partiallyorderedset)withorderrelation.8WVede neQqIJVi& msam10Cj%:UR()G *i(asitisde ned)willbSeacyclic,,i.e.Otherearenocycles.Condition(1)meansthat]PtheorderofOF lis\generated"brythegraph.If p߹isinjectivethensomeoftheedgeswillbSeorienrted,"theorientationoftheedgeswillbSetransitive,"andFwiththisorientationwillbSeacyclic.8Elseitmaryhappenthatedgesareorienrtedinbothdirections.Example`X2.4.cAnexampleis <:f1;2;3;4g8!\fa;b;cg=VF 9whereallvrerticesarecon-nectedI\bryanedgeand (1)= (4)=a,a (2)=b,a (3)=c.TThenI\1RB_Mp2RB_Mp3RB_Mp4,a 1RB_Mp3,and2!_Mp4,djandtheedgesfa;bgandfa;cgaredirectedinbSothdirections.~FVurthermoreOF d=URf1;2;3;4g꨹aspSosets,inparticular14but1_Mp*4doSesnothold.De nitionc2.5.Let(FS;OFO; O)bSeapograph.rAbijectivre,Borderpreservingmap $:*OF!nf1;:::ʜ;ngؽiscalledanupffdate"scheduleؽfor(FS;OFO; O).2Thepair((FS;OFO; O); )iscalledapffograph35withupffdateschedule.nNorw%Theorem2.1saysthatwecanconstructapSographwithupdatescrheduleoutofeveryugraph.OZConrverselyG{wecanconstructaugraphoutofeverypSographwithupdatescrheduleintheobrviouswayV.8Thesetwoconstructionsarealmostinversesofeachother.Prop`osition^2.6.rLffetFu۹=(FS;OFO; O; )and(FS;O2UV0bFO; O20x; 20uU)bffe nitepographswithupdatescheffdules9 :aOF p V!8f1;:::ʜ;ngand 20:O2UV0bF p V!8f1;:::ʜ;ngrffesp.zRAssumethat O 21e4= 20x 20 ^1b.Then0NtherffeisauniqueisomorphismofposetsȄ:UROF d ! `O2UV0bF ?suchthat n= 20uUand = O20xs2.rffoof.#RObrviously>O :=s 20%^1 kistheonlychoiceforthismapandsatis es >=s 20uUand =UR O20xs2.'WVe=onlyharve=toshorwthat(oisorderpreserving,sincetheinversemapwillalsobSeorderspreservingbrythesymmetryofthesituation. $Leti;j%2UROFO.SinceOF ¹is nitewreonlyharvetoshorwSiCj%=)URs2(i)(jӹ):SinceVi CjJ)impliesf O(i); (jӹ)gUR2EF wregetf O20xs2(i); O20(jӹ)gUR2EF henceV(i)(jӹ) _(jӹ)URs2(i). Assume;that(jӹ)(i);holds. Thenwrehave (jӹ)= 20uUs2(jӹ) 20uUs2(i)= (i),aconrtradictiontoiCjӹ.8Thuss2(i)UR(jӹ).~(tSowreseethatthepSographwithupdatescrhedule(F;OFO; O; )constructedfromaugraph(FS; )TpbryTheorem2.1isuniqueuptoanisomorphism(ofposets),compatiblewiththeupSdatescrheduleandwiththepographmap O.ZY[썍XoUPD9A:TE!SCHEDULESOFSEQUENTIALDYNAMICALSYSTEMSSϴ7nDe nition*2.7.Let(FS;OFO; O; )and(FS;O2UV0bFO; O20x; 20uU)bSe nitepographswithupdatescrhedule.ADstrffongisomorphismnbSetrweenthesepSographswithupdatescrheduleisanisomorphismofpSosetsȄ:UROF d ~,!ӀO2UV0bF sucrhthat n= 20uU]ڹand = O20xs2.Observre+bthatforastrongisomorphismwehave O 21=} 20xs2 21=} 20x 20 ^1b. Obrviously+bstrongisomorphismsde neanequivXalencerelationandtheabSorveobservationsgivreCorollaryy2.8.ThecffonstructionsgiveninTheorem2.1andProposition2.6de neabijec-tion35bffetweenugraphsandstrongisomorphismclassesofpographswithupdateschedules.'-TheanextpropSositionrelatesthenotionofpographwithupdatescrheduletothepermrutationupSdateEscrhedulesusedbyBarrettet.al..FVoragivengraphF秹onnverticesf1;:::ʜ;ngde nean,equivXalencerelationF {onthepSermrutationsinSn E|asfollows.PlLetn9;202-SnP,denotedbry.@6=_(i1;:::ʜ;inP)andn920ѹ=(i20RA1;:::ʜ;i20RAnP).(Thatis,?&n9(jӹ)=ijf ,etc.)Then.@6Y n920jifthereisa3*k72мf1;:::ʜ;ngsucrhthatij6ƹ=i20RAj4forallj}6=kg;kC#+1andthereisnoedgeinFconnectingvrerticesik >#andik6+1.ȚLetF )bSetheequivXalencerelationgeneratedbythisrelation.ȚDenotebryaSnP= "F qthesetofequivXalenceclasses.VLetAFdenotethesetofacyclicorienrtationsonFƹ.Prop`osition2.9.{[7,Prop.1]Therffeisaone-to-onecorrespondencebetweenAF andSnP=URYP.'-ThenextresultshorwshowthenewconceptsofpSosetmodelandpographwithupdatescrheduleKreducetothecaseofpSermutationupSdateschedulesusedinpSermutationSDS.LetIF denoteQthesetofstrongisomorphismclassesofbijectivrepSographswithupdatescrheduleonFn(thatis, isbijectivre).Prop`osition:2.10.Therffecisaone-to-onecorrespondencebetweenIF andAFO,henceaone-to-one'cfforrespondencebetweenthesetofstrongisomorphismclassesofbijectiveposetmodelsand35SnP=URYP.䍍Prffoof.#RLet~ V(:OF (!FDbSeaposetmodelofFƹ,*3andassumethat ͹isbijectivre.bWVede neanacyclicorienrtationOofF3asfollows..-Letfu;vn9gbSeanedgeofFƹ.Thenuq= O(i)andvË=UR O(jӹ)ٖforsomei;j%2OFO.3/Since isapSosetmodel,wrehavethatiURjiorٖj%i.3/Ifijӹ,then3orienrttheedge(u;vn9)fromutov.Since isonrto,Eevery3edgeofFtisorienrtedinthiswrayV.8Itisstraighrtforwardtoseethatthisorienrtationisacyclic,sinceOF isapartialorder.*If* O20}:tO2UV0bF Dٝ!FѹisanotherpSosetmodelofFѹwhicrhisstronglyisomorphicto Zviaanisomorphism'UR:OF d!O2UV0bFO,thenitisclearthat O20c0inducesthesameorienrtationonFƹ.ConrverselyV,let9ObSeanacyclicorienrtationofFƹ.˻ThenOde nesapartialorderonthevrerticesofFƹ,brysettinguz7e}?'(lK):URj( FO)(lK) @jj Fjhk$a6cmex8eÌ'J!j Gj2idp!f1;:::ʜ;ngЍsatisfy35cffondition(). Prffoof.#R(1)=Sincej Gjhasacoarserorderthanf1;:::ʜ;ngwrehavetoshowthatNe':~j FOj!,'j GjYܹisorderpreserving.|Leti;jm2j FOjbSegivrenwithijӹ.|Thenbryde nitionofthepartialorderonj FOjthereisauniqueconnectedcompSonenrtF(lK)~ιwith F(i); F(jӹ)g2F(lK)sothati;ju2j( FO)(lK) @j.ThrusCe'(lK)5ȹ(i)Ge'(lK)9͹(jӹ)andhenceCe' w(i)Ge' {(jӹ)inf1;:::ʜ;ng.Since'g(F(lK) @)G(lK0)forauniqueconnectedcompSonenrtofGweget.e' (i);~e' t(jӹ)inj( G)(lK0) pjhence~e'v(i)Ne' 25(jӹ)inj( G)(lK0) pjandalsoinj Gj.FBythecompatibilitryofe'(lK)with'g nwegetthecommrutativityofthesquare.(2)*Obrviouslye'(lK)} isorderpreservingandsatis esthecompatibilityconditionofe'(lK)} with'g. Thede nitionofmorphismsofpSographsandofugraphsarevrerysimilar.Augraph, however,conrtainsthecompleteinformationonanupSdateschedule,whereasapSographcontainsonlypartofthisinformation.8ThemainpSoinrtisthatOF andj FOjaredi erentpSosets!|Lemma#&3.4.HLffetFx=G(FS; F VS:f1;:::ʜ;mgo!uVFO)andG2=G(G; G f:f1;:::ʜ;ngo!uVG)bffeugrffaphsandlet'UR:Fc!B"GEwith'=('g;~e' t)bffeamorphismofugraphs.V_Let(FS;OFO; F d:UROFfk! VFO; F ̹:}OF7!Ķf1;:::ʜ;mg)and(G;OG; G :}OG-!VG; G:}OG-!f1;:::ʜ;ng)rffesp.bffethepographswithupdatescheduleasconstructedinTheorem2.1. fThen'inducesa Y[썍10t˾REINHARDTLA9UBENBACHERANDBODOP:AREIGISnmorphism35ofpffographs35suchthatPqH| f1;:::ʜ;mgHj FOjq{fd pάzidHHpOF,{fd ဍά;w& F{󎎍{@VF,{fd$pά-$S% F~0f1;:::ʜ;ngj Gj32fd@ά:źidKOG,32fd p<άm{P G3333@VG<32fd$g`ά-]$i GHOzǠ*Ffe҂Ǡ? ǜEe'H Ǡ*Ffe 9Ǡ? Se'HGǠ*FfeG,Ǡ?3L'gcffommutes.ߛPrffoof.#RSincetheunderlyingsetsofOF Iandofj FOjareequaltof1;:::ʜ;mgandthemap FisA_theidenrtityV,W theA_leftsquarecommrutes.=Thesamesettheoreticargumentshowsthattherighrtsquarecommutes.8WVehavetoshowthat F andi7e'p:UROF d ~,!ӀOG @areorderpreserving.*Let,i;j%2UROF {withi_MpϯjibSegivren.)Thenijiinf1;:::ʜ;mgandf FO(i); F(jӹ)gUR2EFO.)Thrus FO(i)and F(jӹ)areconrtainedinacommonconnectedcompSonentF(lK) s^ofFVandhenceiURjinj FOj.8Thisshorwsthat F isorderpreserving.FVurthermoreUe`' ֹ(i)?fe' (jӹ)`inj Gjandinf1;:::ʜ;ng. Sincef G'e'(i); G'e'(jӹ)g?2EG wre`get~e'v(i)_Mp e UW'͹(jӹ)inOG.8Soi7e'p:UROF d ~,!ӀOG @isalsoorderpreserving.:ߛWVeharvenowprovedthefollowingTheorem',3.5.The$cffonstructionsgiveninTheorem2.1andLemma3.4de neaembeddingfunctorč!a('g;~e' t):(FS;OFO; F)^!3(G;OG; G)>awith'gѹ=idande' ׹(1)=1,eSO' Ź(2)=3,eSO'(3)=2isamorphismofpSographs.SincebSothgraphsharveonlyoneconnectedcomponenrtwehavej FOjUR=f1;2;3gUR=j Gjwiththenaturaltotalorder.8Hencei7e'p:URj FOjn!1j Gj꨹asde nedabSorveisnotorderpreserving.So3themorphism('g;~e' t):(FS;OFO; F) !!&(G;OG; G)3ofpSographsisnotinducedbryanymorphismofugraphsfrom(FS; FO)to(G; G)..IfpapSograph(F;OFO; F)phasanupSdatescrhedule n:UROF d ~,!ӀVF then(F;OFO; F)PUR԰n:=Q((FS; F 18OF )).Sodi erenrtugraphscanhaveisomorphicimagesunderQ.Theyclearlydi eronlyintheirupSdateZscrhedules. ThequestionifQisarepresentativefunctor,i.e. ifforeveryobjectY2URPogn9rSaph49thereisanXF2URU1gn9rSaph.uzwithQ(X)PUR԰n:=Yp,isanswreredinthefollowing.WVeusethefollorwingpropSositionaboutorderedsets.7Prop`ositiong3.8. fLffetE(OUV;)beaposetand(T ;)beatotallyorderedset.Let'w:(OUV;)fk!U(T ;)bffeaposetmap. Thenthereisatotalorder20ionOextendingsuchthat'UR:(OUV;209)!(T ;)35isapffosetmap.Prffoof.#RWVeuconsiderthesetofpairs(U;UB)withUfOI˹andU atotalorderonU@,thatisanjextensionofURjUB,CtheorderonOrestrictedtoU@,sucrhthat'jU o:UR(U;UB)n!1(T ;)jisaDpSosetmap.ThesetSmofthesepairsisinductivrelyorderedby(U;UB)URv(V;VVȹ)Di U6URVand(VVȹ)jU o=UB.8ThrusS hasamaximalelement(U;209)byZorn'sLemma.AssumeqU66=UROUV.Letx2OnxU@.De neUx9:=fu2U@j'(u)<'(x)orG9w2U6:u20#wxg.De nethefollorwingrelation200 onU[fxgwhereu;vË2URU*2pʍuUR200qv()u20#vn9;$uUR200qx()u2UxH;xUR200qv()v(=Ë2UxH;VxUR200qx:)It9iseasytoshorwthatthisisanelementinSb.>Re exivityandsymmetryof200 areclearfromthede nition.#FVurthermoreitisclearbryde nitionthatthisisatotalorderassoSonaswrehaveprovedtransitivityV.jTheonlyimpSortantcasesfortransitivityareu2005x;^x2005vn9,xUR200qu200vn9,andu200vË200x."Theseareeasyexercisesintheaxiomsfortheneworder.Soisthefactthat200 extends.Thenitisclearthat200astheone-elementtotallyorderedsetand'theonlypSossiblemap.ObservreJthattheproSofofProposition3.8isnon-constructivre,&butthatithassucientconstructivre|ingredients,inparticulartheconstructionofU [ʤfxganditsorder,tode neanalgorithmincasethesetsofinrterest(e.g.8SDS)are nite. ݠY[썍12t˾REINHARDTLA9UBENBACHERANDBODOP:AREIGISn썹NorwwereturntothediscussionofpSographs.YCorollary֗3.10.Lffet(FS;OUV; O)bffeapograph.)oThenthereexistsanupdateschedule ۹: Ofk!f1;:::ʜ;ng.Corollary3.11.The35embffeddingfunctorV! xAacmr61:=URf i> x1 j(1)":::f i> x1 j(n)#:kg rN h\!kg r:>֍FVor1anSDS1onapSographwithoutagivrenupdatescrhedule,Cshowever,it1isnotclearhorwtoconstructvaglobalupSdatefunction.JSothefollorwingPropositionanditsconsequencesaresurprisingandimpSortanrt.GY[썍14t˾REINHARDTLA9UBENBACHERANDBODOP:AREIGISnProp`osition24.2.Lffet<*Fm;bea nitesequentialdynamicalsystemonapographF.HLet ;!:OF d ! `f1;:::ʜ;ng35bffeupdateschedules.fiThen9f i> x1=URf i>I{1-d:xPrffoof.#RFVor}alliUR2f1;:::ʜ;ng}letai,:=UR O 21 (i)andbi:=UR On921 ʵ(i).''WVewrant}toshorwfaq1 l>:::Ffan wX=URfbq1 +:::fbn A.*FVoreacrhj{thereisani(=UR n921 ʵ(jӹ))suchthatbj\=URaiOandconverselyV.Claim:VGivrenMj;k2f1;:::ʜ;ngsucrhthatk<jandn9 21 (jӹ)< 21 (kg),thenMf i> x1 j(jv)"yf i> x1 j(k6)%S=Bf i> x1 j(k6)#Lf i> x1 j(jv)(. 8Let?u:= 21 (jӹ)andv{:= 21 (kg). 8Then (vn9)< (u)?and؍n9(u)r<(v).lSincebSothmaps andj.areorderpreservingwregetthatur6vandv6uinthepSosetOF hencef O(u); (vn9)g=UR2EFO. Sowregetthatf i>(u)LMf i>(vI{) =URf i>(vI{)|f i>(u)QbyRemark1.1.*AssumenorwthatwehavealreadyarrangedareorderingoftheupSdatefunctionsuchthattfaq1 :::fan wX=URfbq1 +:::fb8:jY1*fai?l [:::famwherethefai?l;:::ʜ;fam2arethosefactorsamongthefaq1 .v;:::ʜ;fan@thatdonotoSccurasfactorsfbq1M;:::ʜ;fb8:jY1jandwheretheirproSductistakreninthesameorderasinfaq1 .v;:::ʜ;fan ".Letn921 ʵ(jӹ)W= 21 (i)andthrusbj =ai}andfb8:j e>=fa8:i0A.,WVewranttoshifttheloScalupdatefunction ;fb8:j Jѹ==fa8:i 9|intherighrthandsideoftheequationtowardstheleft.GivenkpXwithRlURko x1:kg2rN b0exceptfori1;irb;j1;jsmwhicrh1mayalsobSezero).zWVewillshowfurtherdownthattherearechoicesforfa andfbʹsucrhthatf2Giq1RAa׀fnGiq2*bf2Giq3RAa ~:::fߍGiryb N=uqf2Gjq1RAa bfOGjq2 bf2Gjq3RAa b:::-DfOGjs b Ͷi (i1;:::ʜ;irb)=(j1;:::ʜ;jsn<).4ThisisequivXalenrt(tolabSeingorderpreservingonthepreimageoffa;bgunder .saSincewemaycrhoSosefc=did"forallcd6=a;b,theassumptionf Z#=df̍e 1impliesthataӹisorderpreservingonthepreimageoffa;bgunder .*Norwweshowunderthegivenassumptionsthat&isorderpreserving.Leti;j2Z5OF if$x[a]>x[b];ɍ (:::;qx[b];:::ʜ;x[b];:::)_>if$x[a]x[b];"nwhereapisthelargestprimedividingx[a]andqϹisthesmallestprimenotdividingx[b].FVurthermoreletm6%fb"ܹ(:::ʞ;x[a];:::ʜ;x[b];:::)UR=z( (:::;x[a];:::ʜ;qx[a];:::)Iifx[a]x[b];ɍ (:::;x[a];:::ʜ;px[b];:::)Iifx[a].Y0.dAjsimilarargumenrtholdsfori1]=0and/orir=0.dThisprorvesj)theclaimandthePropSosition.yaCorollarykt4.7.NThe_numbfferofbijectiveorderpreservingmapsOF d ! `f1;:::ʜ;ngisasharplowerjbffoundforthenumberofdi erentupdateschedulesforagraphgivingthesameglobalupffdate35function.[LetNFbSeagraph.WVecalltrwoNupdatescrhedules ; 20;:Z+f1;:::ʜ;ngs!VF )equivXalenrt,f8i forallcrhoicesofloScalstatespaces(kg[a]ja2VFO)andallchoicesofloScalupdatefunctions(fajaUR2VFO)onthegivrengraphFntheglobalupSdatefunctionsf ?andf 0 areequal.㰍Corollary4.8.Therffeisaone-to-onecorrespondencebetweenequivalenceclassesofupdatescheffdules35oflengthnandposetmodelswithnelementsofthegraphF.*!5.%OnthePosetsofPographs*WVeDharveseenthatthestructureofSDSstronglydepSendsontheunderlyingpographs. InthissectionwreinvestigatewhichpSosetscanoccurasposetsinpographs.De nition(5.1.JA}RpSograph}x(F;OFO; O)iscalledrigid,,ifthereisonlyonebijectivremapofpSosets@z n:UROF d ~,!Ӏf1;:::ʜ;ng.&Inotherwrords,bapographisrigid,bifOF Oɹhasauniqueextensiontoatotalordering.*An upSdatescrhedule :tf1;:::ʜ;ng!uVF [of agraphFhҹiscalledrigidifthereisonlyonebijectivremapofpSosets n:UROF d ~,!Ӏf1;:::ʜ;ng,whereOF isinducedby .Prop`osition5.2. Fis35rigidifandonlyifOF Bistotallyorffdered.$ Prffoof.#RThis5follorwsfromthefactthatapSosethasauniqueextensiontoatotalorderingifandonlyifitisalreadytotallyordered.8See[8,p.17].j1Y[썍XoUPD9A:TE!SCHEDULESOFSEQUENTIALDYNAMICALSYSTEMSO/17n썹Thrus}forpSographswithtotallyorderedposetOF ̹wrehaveonlyoneupSdateschedule.'_TheoppSosite"observXationisthatapographwithadiscreteposet(notrwo"elementscanbSecom-pared)hasn2n FupSdatefunctions :UROF d ~,!Ӏf1;:::ʜ;ng.7Theyallgivrethesameglobalupdatefunction.\Examples5.3.(1)| Aqlinear}grapha1;:::ʜ;an ͹withEF =pG rfaid;ai+1AVgjip=1;:::ʜ;n1G 38%〹hasXAarigidupSdatescrhedule (i)=aidڹ.AnXAexampleforsuchanSDSX%isacolumnof%cars2onaroada1;:::ʜ;an whereeacrhcardeterminesitsbSehaviororitsloScalupdate%functionMupSontheprecedingcar.Thisgivresalineargraphandtheupdatescrhedule% ,cannotbSecrhangedwithouttheriskofchangingtheglobalupSdatefunctionofthe%system.(2)%APlinearbgraphwithatleastthreevrerticeshasanonrigidupSdateschedule.!Leta;b;c%〹bSethreeconsecutivreverticesinFawithedgesfa;bgandfb;cg.Considertherigid%upSdate>scrhedule ͹with (i)UR=a, (iM+1)UR=b,and> (iM+2)UR=c.4De ne>newupSdate%scrhedules8e bby8e wd(jӹ)UR:= (j)forj%6=URi+1;i+2and8e wd(i+1)=c,:e wf(i+2)=bꜹanddzȟK %〹bry=dzȟK r(jӹ)UR:= (j)=forj%6=URi;i+1;i+2,Sand=dzȟK r(i)UR=c,dzȟK s(i+1)UR=a,dzȟK s(i+2)UR=b.7Then%itɸiseasytoseethatbSothupdatescrhedulesde nethesameposetO(asconstructed%intheproSofofTheorem2.1).(3)%TheThrypSercubeF= f(x1;:::ʜ;xnP)jxin2f0;1ggwith22n vrerticeshasarigidupSdate%scrheduleMK ă:f1;:::ʜ;22nPg!{uFƹ. `ItiswrellknownthatFisaHamiltoniangraph.%ByvVomittingthelastedgeinaHamiltonianpathwregetarigidupSdateschedule% h:URf1;:::ʜ;22nPgn!1VFO.(4)%It#isaneasyexercisetoshorwthathypSercubes#ofdimensionnjW2#havenonrigid%upSdatescrhedules.(5)%AninrterestingexampleofarigidupSdatescheduleisgiveninExample2.4.Norwweshowthatany nitepSosetO?canoccurasaposetofapograph.Prop`ositionX5.4.d1)GLffetOhbea niteposet.[LetVbeasetand :URO!fgVbeamapsuchthat35iCjimplies O(i)UR6= (jӹ)35foralli;j%2UROUV.fiThentheHassediagrffamaEF d:=URG UTf O(i); (jӹ)g35ji;j%2URO:iCjӟG ade nes35agrffaphFwithvertexsetVF d=URVϥsuchthat(FS;OUV; O)35isapograph.*2)TLffetObea niteposet.ʋLetVbeasetand =p:!OwN!VbeamapsuchthatiaCjiimplies O(i)UR6= (jӹ)35foralli;j%2UROUV.fiThen^҆EF d:=URG UTf O(i); (jӹ)g35ji;j%2URO:i