; TeX output 2002.06.20:1458¥[n썑N cmbx12DECOMPOSITIONٚANDSIMULATIONOFSEQUENTIALDYNAMICALSYSTEMSk4$K`y cmr10REINHARDUULAUBENBACHERANDBODOP*AREIGIS+5э6 $- cmcsc10Abstract.\`SequentialdynamicalsystemshavebGeendevelopGedasabasisforatheoryof $computersimulation.ThispapGercontainsageneralizationofthisconcept.Thenotionof$morphismcofsequentialdynamicalsystemsisintroGduced,formalizingtheconceptofsimulat-$ingUeonesystembyanother.qSeveralexamplesofmorphismsaregiven.qUsingthemorphism$concept,itKisshownthateverysequentialdynamicalsystemdecompGosesuniquelyintoa$proGductUUofindecomposablesystems.o- cmcsc10Introduction*XQ cmr12Computer*simrulationhasbSecomeanimportanrttoolinthestudyofcomplexnaturalandhruman-madesystems,fromthebioSchemicalnetworkunderlyingcellmetabSolismtoroadtracJsystemsinourcities.AJvXarietryofsimulationtoSolsareavXailable,jrangingfromdiscreteevrentsimulationsanddi erential-equations-basedsimulations,tostoSchasticsimulations,andvXarioushrybridsofthese.*MucrhinsighthasbSeengainedintothestructureaswellasthedynamicbSehaviorofcomplexsystemsthroughtheuseofsimrulations,_andtheyprovideanimpSortantbasisforhypSothesisgeneration,^?whicrhG!maydetermineexpSerimentalsetups.NJButsimulationisbyandlargestillan artform,&withlittletheoreticalguidancetoitsdesign,andmostlyadhoScmethodsforthe.analysisoftheresultingoutput. Comparisonofdi erenrtsimulationsofthesamesystemis|dicult,asisthecomparisonofimplemenrtationsofthesamesimulationondi erentplat-forms,BLespSecially5oflarge-scalesimrulations.Many5oftheproblemsassociatedwithsimrulationapproacrhesrequirepSowerfulscienti ctoSols,however,aswellasarigorousmethoSdologyV.There=gexistsascatteredcollectionofresultsandtecrhniquesthatcanbSeconsideredpartofanewlyemerging@ cmti12simulation7'sciencffe.EAnimpSortanrtcontributionisthetheoryofseffquentialdynamicffal Osystemsӹ(SDS),amathematicalabstractionofalargeclassofcomputersimrulations[2,!3 ,!4].SDS!theory!isinrtendedasamathematicalfoundationforcomputersimulationsthatare&represenrtableasdiscretedynamicalsystems.TheoremsabSoutSDS&provideanalysistoSolsforexistingsimrulationsandguidanceforthedesignofnewones.Simulationpracticehasprorvidedtheinspirationforthede nitionofSDSandforthesearchfortheoremsabSoutthem.A fullyQdevrelopSedSDStheorypromisestoprorvideanswerstomanytheoreticalquestions iωff< B ': cmti10Date[:UUJune20,2002. u 2000IMathematicsSubje}'ctClassi cation.Primary:37B99, 68Q65,93A30;OeSecondary:18B20,37B19, 68R01. This[papGerwaswrittenwhilethesecondauthorwasvisitingthePhysicalScienceLabGoratoryofNewMexicoStateUniversity(NMSU),LasCruces,uin2001.=UHewishestothanktheLabGoratoryandallcolleaguesforStheirsuppGortandhospitality*.mtTheworkofthe rstauthorwaspartiallysuppGortedbyfundsfromapartnershipUUinitiativebGetweenNMSUandLosAlamosNationalLabGoratory*. 营o cmr91*¥[썍2t˾REINHARDTLA9UBENBACHERANDBODOP:AREIGISn썹abSoutsimrulations.#=TVotheextentthatthetheoryhasbSeenusedinpracticethispromisehasbSeenful lled.d+IndevrelopingsimulationscienceitisimpSortant,however,thatthetheorybSeguidedbryacloseconnectiontoandintimateknowledgeofsimulationpractice,(justasgoSodsimrulationsrequireintimateknowledgeofthesystemstobSesimulated.*Mostٱsystemsofinrterest,Iwhetherbiological,soScial,ortecrhnical,aretoSolargetobesimrulatedaccuratelyV.kEvren3,ifsuchsimulationscanbSerunonacomputer,ELtheoutputisverydiculttolanalyze.k+Thrus,?thequestionariseshowtoreplacealargesystem,?orlargesimulation,bryustoobservethee ectofstructuralchangesofanSDSonitsdynamicalbSehavior.TheOconceptofmorphismandcategoryofSDSOandothertoSolsusedindi erenrtcategorieswillhelpustoevrentuallydevelopamathematicalstructuretheoryofSDSandbSeableto netunethedynamicbSeharviorofanSDS.OurapproachusestoSolsfromandbringsnewresults&ytographtheoryV,5mdiscretemathematics,anddiscretedynamicalsystemstheoryV.RThecategoricaltoSolsusedinourapproacrhhelpustoasktherightquestionstounderstandtherelationshipbSetrweenstructureandbSehaviorofSDS.In.thispapSerwredescribeamoregeneralconceptofSDS,andwillcallthe\classical"conceptapffermutationSDS(PSDS).FVortheconrvenienceofthereaderwrerecallthePSDSconcept.Letn4g cmmi12ko=UR"!", cmsy10f0;1g.dAnpffermutationsequentialdynamicalsystemn4FEonthesetkg2 2cmmi8n }ofbinarystringsoflengthncanbSethoughrtofasafunction0fQ:URkg n d ~J!Ӟkg nm;constructedfromthefollorwingdata:u9(1)%a nitegraphFnonnvrertices,(2)%aofamilyof\loScal"updatefunctionsfaY!:URkg2n d ~J!Ӟkg2nm,oneforeacrhvertexaofFƹ,which%crhangesonlythecoSordinatecorrespondingtoa,andcomputesthebinarystateof%vrertex%ta.DTheyarefurthermoreassumedtobSesymmetricintheirinputs.These%functions]areloScalinthesensethattheyonlydependonthosevXariableswhicrhare%connectedtoainFƹ.(3)%anp\upSdatescrhedule"n9,whichspSeci esanorderontheverticesofFƹ,representedby%apSermrutationË2URSnP.TheBQfunctionfPisthenconstructedbrycompSosingthelocalfunctionsaccordingtotheupdatescrhedulen9,thatis,-fQ=URfI{|{Ycmr8(n)zUNfI{(1)ع:kg n d ~J!Ӟkg nm:¥[썍ZSEQUENTIAL!D9YNAMICALSYSTEMS)\3n썹Thestudyofthesesystemsleadstovreryinterestingmathematicalquestions,indepSendentof applications,andmotivXated[6],inwhicrhwebSeganthedevelopmentofamoregeneralframewrorkforPSDS.Thisframeworkisusedin[5]toexploreasetupforSDSinwhichthegraphtFg:isnotexplicitinthedata.,yItnaturallysuggestsade nitionforthelinearizationofa nitesystem,sucrhascertaintypSesofSDS.*In7thispapSerwregeneralizethenotionofapermrutationdynamicalsystemtothatofanSDS.TVobSeginwith,wreallowthesetkbofstatestobSearbitraryV,ratherthanjustf0;1g.kfInparticular,Tkcould?zbSeasubsetof+ msbm10R,e.g.7VtheinrtervXal[0;1].ThiscouldleadtothenotionsofvfuzzyandstoffchasticSDS.SecondlyV,YwremakenorestrictionsontheloScalfunctionsfaϹ,withCrespSecttosymmetryV.BMostimportanrtlyV,Y)weCusemoregeneralupdatescrheduleswhichallorwtheuseofonlyasubsetofallloScalfunctionsintheconstructionoftheglobalupdatefunction, aswrellasarbitraryrepSetitionsoflocalupdatefunctions.ThisisvreryusefulfromthepSoinrtofviewofapplications.FVorinstance,pSDSإincludeglobalfunctionsthatsimplypSermrutectheentriesofabinarystring. SuchafunctioncannotbSetheglobalupdatefunctionofaPSDS.ThisnotionofSDSincludesinparticularPSDS.ThefbulkofthepapSerisdevrotedtothestudyofspecialsimrulationsofSDSfbyotherSDSgivrenbycertainreasonablemapsbSetweenthesesystemswhichwillleadtotheconstructionofTmorphismsofSDS,therebryeventuallyconstructingacategorySDSz.vFVromthepSointofviewݡofapplicationsamorphismfromanSDSݝFtoanotherSDSGϹshouldbSethoughrtofasadsimrulationofonesystembytheother.Twointerpretationsareofparticularinterest.AmonomorphismshouldrepresenrtasimulationofGjʹbyF1,thenF孹isthesmallerandmoremanageablesystem, F7isasubsystemofG..AnepimorphismshouldrepresenrtasimulationofFbryG..8HereGֹisthesmallersystem,GisaquotienrtsystemofF1.Insourde nitionofmorphismswreareguidedbythedesiretohavesucientlymanymor-phismsTarvXailablesothatthecategorywouldpSossess niteproducts,randsothatthereshouldbSe\XsucienrtlymanyisomorphismstoidentifysystemsthatshouldbSeconsideredisomorphic.TVo determineiftrwo SDSFandG::areisomorphicisnottrivialinviewofthevrerysimpleExample2.5(2).ZButifwreknowthatF'andG.areisomorphic,thenwecanpicktheeasierloSokingmodeltostudyitsdynamicbeharvior.FVurthermore`morphismsshouldhelpusto ndsimplermoSdelsofSDS_asexplainedbelorw. Amorphism'o:F.!)GBofsequenrtialdynamicalsystemsshouldhavethefollowingpropSertiesinspSecialcases.mFshouldmimictoacertainextenrtthedynamicalstructureofG.,butitshould&QbSesimpler.nFVoragivrensequentialdynamicalsystemGweloSokforasimplesequentialdynamicalsystemFandamorphism',WthatmapsacertainstateofFinrtoastartstateofG.,so thatF>hasthe\same"dynamicalbSeharviorasGstartingatthegivenstate.ItwouldbSeWniceifwrecouldevengiveafreelygeneratedsequentialdynamicalsystemF hwiththispropSertryV.8Butthatseemstobetoocomplicatedatpresenrt.Onecouldalsoconsiderthedualsituation:foragivrensequentialdynamicalsystemFtogethertheword ,>andthesetsofstateskg[a]weshallinrtroSduce{mapswithcertaincompatibilityrequirements.TheloScalfunctionsfa nwilloccurincommrutativediagrams.%De nitionv2.1.OLetFc=URGTFS;(kg[a]);(fi,:URk2n d ~J!Ӟk2nm); G)(withVF d=URfa1;:::ʜ;anPgandfi,=URfa8:i0A)foandG(`=r2G4G;(kg[b]);(gj<:r2k2m  !ik2mk); OG %bSeSDS.Let'gG0:r2G!Febeagraphmorphism,and38('sn<[b]x:kg['g(b)]|! ok[b]jb2VG)bSeafamilyofmapsinthecategoryZܞ.:Then'g jandthefamily('sn<[b])induceanadjoinrtmaponthestatespacesasfollows:8considerthepairingꍑykg nVF d3UR(x;a)7!hx;ai:=x[a]2K&[a2VX.FOkg[a];ȍandmsimilarlykg2m ӨgVG MgA!aS+akg[b].z0Then'g :.GG!uF3andm('sn<[b])induceanadjoint2map'2V:URkg2n d ~J!Ӟkg2m VwithTL(1) h' (x);biUR:='sn<[b](hx;'g(b)i)ff< 1@Subsequently*,UUwewillusetheacronymSDSforpluralaswellassingularinstances.G¥[썍6t˾REINHARDTLA9UBENBACHERANDBODOP:AREIGISn*>;8PSfile=examples.eps llx=0 lly=0 urx=388 ury=378 rwi=1847 1΍orhH' (x[a1];:::ʜ;x[anP])UR:=('sn<[b1](x['g(b1)]);:::ʜ;'sn<[bmĹ](x['g(bm)])):LRemark k2.2.Let`(G;(kg[b]);(gj\:URk2m 3 ھ!0k2mk); O)`bSeanSDS.LetfG(lK) @gbethesetofconnectedcompSonenrts ofG.Letgi,:URkg2m 3 ھ!0kg2m ǹandgj\:kg2m 3 ھ!0kg2m ǹbSetrwo localfunctionsforthevrerticesaid;ajXindi erenrtconnectedcompSonents,$'thengigj\=URgjgidڹ,sincebSothmapsdependonlyonthe_1-neighrbSorhoodsofai#9andaj$iconrtainedinthedisjointconnectedcompSonents.*Similarlyanry"twoproSductsoflocalfunctionsfiq1:::fir allbeingde nedorveraconnectedcompSonentG(1)G$andfjq1 Q:::fjs qallbSeingde nedorveraconnectedcomponenrtG(2)G$commute.LetF =gG FS;(kg[a]);(fiԹ:gk2n wg !k2nm); G andG(=gG G;(k[b]);(gj:gk2m f!Ubk2mk); OG UbSeSDS.As rst7compSonenrtsofamorphism'ؑ:F #-!Gwe7havealreadyamapofgraphs'g:ؑG!ʯFandy*afamilyofmaps('sn<[b]G:kg['g(b)]an!Sk[b]jb2VG)y*inZUȹ(togetherwithitsadjoinrtmap'2 :Jkg2n Y sy!kg2mk).WithzthefollorwingexampleswewanttomotivXatetheconditionsthatweharvetoimpSoseonmapsbetrweenwordsthatrelate 7and O.*WVe1AwrantthatmorphismsbSetweenSDS1/shouldpreservetheloScalandglobaldynamicalbe-harvior.ThiscimpliesthatmorphismsbSetweenSDS)leadtomorphismsbSetweentheassoSciatedglobalupSdatefunctions.8Thefollorwingdiagramshouldcommute:EӍ1Ѷkg2n1ökg2nj:2fdJO line10-'ef*|kg2m*|kg2mƗT32fdHά-!7%grǠ@fe礟Ǡ?U'-:$q% cmsy6rǠ@fe٤Ǡ?$'-:jWVeusethewrord h=UR( 1;:::ʜ; sn<)todescribSetheglobalupdatefunctionasfQ=URf s 4e==f q1andT =( 1;:::ʜ; tʹ)forgv=g t d`g q1 o.tWVewrantTtoreducetheabSorveTdiagramtosimilarconditionsabSoutthelocalupdatefunctions.ThefollorwingsexampleswillshowthemostimpSortanrtpointsthathavetobSeobservedforthisde nition.>ExamplesL2.3.wIn thefollorwinglistofexampleswerefertothegraphsinFigure1.WVeassumekg[a]UR=k[b]=kQŹforallaUR2VFO,b2VG,and'sn<[b]=id forallb2VG.(1)/ Let'g:ɽG1 L!m FӹbSetheidenrtity/ maponthevrertices.LetF`bede nedwiththewrord u"=a(abcd),andletG bSede nedwiththewrord  =(abcd).NyIfwrerequirethatthefollowing[U¥[썍ZSEQUENTIAL!D9YNAMICALSYSTEMS)\7n썹diagramscommrute=1Ѷkg2n1ökg2nj:2fdJά-Qf i*|kg2m*|kg2mƗT32fdHά-lgi? irǠ@fe礟Ǡ?U'-:rǠ@fe٤Ǡ?$'-:G thenthediagramvË=a2),#andEF d=ffu;vn9gg,R>andlet 7=(u;vn9;u).Let(kg[u]=k[vn9]=k.Art(thistimewedonot xtheloScalfunctionsfuk;fv:kg22!nkg22'!.)KFVurthermoreletGbSede nedbryVG t=URfb1g=fwRgandEG=UR;,Dletkg[wR]=k,Dandlet =UR(wR;w).FVorGwrealsodonot xtheloScalfunctiongw %:ko!+Nkg.De neagraphmorphism'g=:hG.!Fǹbry'g(wR)=u.ZWVealso x'sn<[wR]:kK!Qk]tobSetheidenrtityV.ZThen'2(:hkg22 O!kis#theprojectiononrtothe rstcompSonentpr;T1,1!since'2(x[u];x[vn9])H=x['g(wR)]=x[u].BothgraphsTharveonlyoneconnectedcompSonent.Ourde nitionsgiveorderedsetsj jUR=f1;2;3g,j OjUR=f1;2g=j (1) \|j.FVorXej'(lK)8:jj (1) \|j!aj jjorXe'(lK):jf1;2g!af1;2;3gjwrehavethechoiceamongthree\orderpreservingmapsoforderedmrultisets"thatsatisfythe rstaxiomformorphisms:#ՍswUxnu:Ǡ felǠ?Ս}wA̟ 胀U>v胀UqnuAՍώwUГnuӸ:Ǡ felǠ?Ս }wA胀UYv胀UnuA RՍwUnu胀A2w,H6eH6ejՍ5&}wA胀U6tv胀UMnuA> RXvWVewranttoestablishconditionssothatthesethreemapsde nemorphismsofSDS.Case1:8WVeharvei7e'(1)(1)UR=1andi7e'(1)(2)UR=1.8Sothefollorwingdiagramsmustcommute:DP{kg22Pkg22;4:2fd4_ά-F&f 1 ~b=fu*}k*dk32fd9`ά- +.&gi? 2gi? 1=g-:I{2ƍw2Ǡ@fe0dǠ?nm^0K`y 3 cmr10prw1rǠ@feǥǠ?nXdprַ1Pkg22Pykg22а:2fd4_ά-F܂Rf 2 ~b=fv*dk* ٞkWt32fd9`ά-̍Uid 2Ǡ@fedǠ?npr-&1Pykg22PNkg22&4:2fd4_ά-F"&f 3 ~b=fu* ٞk*QOk32fd9`ά-̍-vidT]Ǡ@feTǠ?nYCdprc1JConditions GfortheloScalmapssothatthisbecomesamorphismofSDS arefu (=BJid5andg2n92RAw %=URid .Case2:8WVeharvei7e'(1)(1)UR=1andi7e'(1)(2)UR=3.8Sothefollorwingdiagramsmustcommute:DP{kg22Pkg22;4:2fd4_ά-F&f 1 ~b=fu*}k*dk32fd9`ά-ݍRgi? 1=gw2Ǡ@fe0dǠ?nm^prw1rǠ@feǥǠ?nXdprַ1Pkg22Pykg22а:2fd4_ά-F܂Rf 2 ~b=fv*dk* ٞkWt32fd9`ά-̍Uid 2Ǡ@fedǠ?npr-&1Pykg22PNkg22&4:2fd4_ά-F"&f 3 ~b=fu* ٞk*QOk32fd9`ά-ݍ"Rgi? 1=gwT]Ǡ@feTǠ?nYCdprc1E6ConditionsfortheloScalmapssothatthisbecomesamorphismofSDSzarefuk޹(x[u];x[vn9])=(gwН(x[u]);x[vn9]).Case3:8WVeharvei7e'(1)(1)UR=3andi7e'(1)(2)UR=3.8Sothefollorwingdiagramsmustcommute:DP{kg22Pkg22;4:2fd4_ά-F&f 1 ~b=fu*}k*dk32fd9`ά-̍vid2Ǡ@fe0dǠ?nm^prw1rǠ@feǥǠ?nXdprַ1Pkg22Pykg22а:2fd4_ά-F܂Rf 2 ~b=fv*dk* ٞkWt32fd9`ά-̍Uid 2Ǡ@fedǠ?npr-&1Pykg22PNkg22&4:2fd4_ά-F"&f 3 ~b=fu* ٞk*QOk32fd9`ά- +&gi? 2gi? 1=g-:I{2ƍwT]Ǡ@feTǠ?nYCdprc1JConditions GfortheloScalmapssothatthisbecomesamorphismofSDS arefu (=BJid5andg2n92RAw %=URid .(5)(Ifkg[a]t!=[0;1]R(istheclosedunitinrtervXalandk[b]t!=f0;Fu31131z@2h;1g,Hthen(anrySDSwith#Zstatespaceskg[a]canbSeconsideredasaprobabilisticorfuzzydynamicalsystem,whereeacrh ¥[썍ZSEQUENTIAL!D9YNAMICALSYSTEMS^11n썹vrertexhasstatesbSetween0and1.SomeinterestingloScalupdatefunctionsfaY!:URkg2n d ~J!Ӟkg2n 8aretheoneswherethea-thcompSonenrtistheproductofallstatesina1-neighrborhoodofxaϹ. Adiscretizationrofsucrhasystemisobtainedbytakingtheidentitymapsfor'gpand-e' `,}andasM1(l):A(1)h jD.T..*Mkg2r*xkg2rG32fdcXά-ɍ%Q-l2P3Q:WWȉJ!ß y ?yM1(l)H)A(t)RJh jD.T..WRΠ@feXΠ?I'-:}wΠ@fe}ğΠ?]D'-:WRǠ@feXǠ?I6 I{-:QҟǠ@feͅǠ?w I{-: Ǡ@fe=URY'؍ l90@&IY*]L\) a' *]8(l)3h 8:j9ˡ1ˡAZ;&ƍwhere̡: z bT(lK)(t):::ʜ: z ]T(lK)#(1)̡istheconcatenationofthecorrespSondingsubrwords.وThis̡isasubrwordof ĹsinceVke* (lK)7isorderpreservingand( t;:::ʜ; 1)isasubrwordof O.*Hencethediagrams>1Ѷkg2n1ökg2nj:2fdJά-Qf i*\kg2r*Nkg2rt32fdK`ά-ɍˋUQӒyl Q-ȉJ U y' 킟M1(l)~A(i)h jrǠ@fe礟Ǡ?ꃀ( I{')-:rǠ@fe٤Ǡ?ꃀ$( I{')-:ύcommrute.|ASinceRVthecompSositionofmorphismsofSDSR;isde nedbrycompositionofcertainsetmaps,isomorphismsofSDSconsistsofcertainbijectivresetmaps.aThisisusefultoconstructoridenrtifyisomorphisms.8InfactExample2.5(2)wasconstructedinsuchawayV.!QN3.TSt32ateSpaces*Anryfunctionf靹:kg2n ʖ!l6kg2n Ode nesa nitedirectedgraphwithvertexsetkg2n Oanddirectededgesr(x;fG(x))forallxUR2kg2nm,IcalledrthestatespffaceroffQ:URkg2n d ~J!Ӟkg2n.AXmorphismfromfQ:URkg2n 㛠¥[썍ZSEQUENTIAL!D9YNAMICALSYSTEMS^13n썍!nkg2n togË:URkg2m 3 ھ!0kg2m VisacommrutativediagramE*1ˬpkg2n1pkg2nEn:2fdά-d嵊f*~6kg2m*w6kg2mr32fdά-m{7gя,Ǡ@fe^Ǡ?*LTh,Ǡ@fe^Ǡ?*mh n:͍Inthiswrayeverymorphismof'functions'inducesamorphismoftheassoSciatedstatespacesin[thecategoryofdirectedgraphs.SowrehaveacovXariantfunctorfrom'functions'tothefullsubScategorySofstatespacesinthecategoryofdirectedgraphs.*Let?F6=(FS;(kg[a]);(f1;:::ʜ;fnP); )bSeanSDSwithupdatefunctionf :kg2n c -!2kg2nm,'f :=f q1 <:::f n ι.8InthissectionwreshowthatthereisacovXariantfunctorcS;:URSDS "!1rgS;givrenbyassigningtoanSDSthestatespaceofitsupSdatefunction.fLemma3.1.A35morphism'UR:Fc!B"Gcof35SDSinducffesacommutativediagramA!1ɒkg2n1kg2n+ӟ:2fdά-'pf *dkg2m*]kg2mXs32fdά-&gi? uǠ@feϨßǠ?'-:nǠ@feßǠ?TC'-:d; that$isamorphismoftheupffdatefunctions.]cFurthermore'inducesagraphmorphismSb(')bffetween35thestatespfface35off J:URkg2n d *! ~kg2n Bandthestatespfface35ofg :kg2m 3'!|kg2mk.pፍPrffoof.#RThediagramB1W߶kg2n1vkg2ngx:2fd?-ά-FEf 111S:::t:2fd&ްά-έ116$:2fd&ް-έ1kg2n1qkg2n/:2fd?-ά-̲܍Gf r*V|kg2m*QF Jޒu"'J(l)S(r1)_gi? j]rǠ@fe]Ǡ?Oc'-:2Ǡ@fe)dǠ?'-:%dǠ@fe%Ǡ?*Jd'-:wrǠ@fewˤǠ?|~$'-:commrutes.8Itremainstoshowthatwg =URg s F:::ag q1 =Y'؍ ltdYy\)B'48(l)"(r^Gƫ`Ǡ@feޒǠ?эˑpr-:ә>әGԱkg2nkg2mԱPkg2nkg2mb:2fd-@ά-'+7id2gi?b*pZkg2m*^bZkg2md232fdHά-!72!gi?bPǠ@feǠ?эpr-:>GesPǠ@feeǠ?эjYpr-:ra>raG~<*:Thisshorwsthatthesecondconditionofamorphismissatis edandthatprʟTGisindeedamorphismofSDS.*ItremainstovrerifytheuniversalpropSertyoftheproSduct.SupposewearegivenanSDSKC=(K5;(kg[d]);(kdߨ);s2)/$andmorphisms':KC!ٳF`5and 8:KC!ٳG..SWVeneedtoshorwthatthereisauniquemorphism@2!Ë:URK=!F۹G.; rsucrhthatprTF h!Ë=UR'andprTG!Ë=UR n9.8De ne!g*P:URFLn[Gn!1KtobSeequalto'g,Uresp. gM g,onthecompSonenrtFƹ,resp. gMG.De ne!sn<[c]E:='s[a]forc˹=a2VF gandX6!sn<[c]:= s[b]X6forc˹=b2VG.SinceX6aconnectedcompSonenrtofF&P?Gdisaconnected#compSonenrtofeitherF4orGJQtheorderpreservingmapoe!(lK)7isdeterminedbyeither4~e'(lK)[^orVke* (lK)Lp. ¥[썍ZSEQUENTIAL!D9YNAMICALSYSTEMS^15n썹Thenpclearly(pr ܟTFw!n9)g*P=UR'gqnand(pr ܟTG9!)g*P=UR g.xFVurthermore(pr ܟTFw!)sn<[a]UR=prn.TF(;s[a]!s[pr ܟTF(;g((a)]=c!sn<[a]UR='s[a]forallaUR2VF andsimilarly(pr ܟTG!n9)s[b]UR= s[b].*Itisclearnorwthat!Xisamorphismuniquelydeterminedby'and n9.bLemma4.2.iHLffet~XFc=UR(FS;(kg[a]);(faϹ); )bffeanSDS.If i2and i+1areindi erentconnectedcffomponents35ofF,then_\X(FS;(kg[a]);(faϹ);( 1;:::ʜ; i+1AV; id;:::; rb))is35isomorphictoF1.ʍPrffoof.#RDe ne'^:FM!(FS;(kg[a]);(faϹ);( 1;:::ʜ; i+1AV; id;:::; rb)). Use'g 3:=^(id)U:Fw!xFƹ)andg'sn<[a]=id o.Let i 2F(1)uand i+192F(2) \|.Thenlete'(2)(Y(i):=i{+1ande'(1)(Y(i+1):=iandi7e'(lK):=URid otherwise.8Thisisobrviouslyacanonicalisomorphism.nLThrusvtheupSdateschedule bofanySDSvFmaybSerearrangedaccordingtotheconnectedcompSonenrtsofFnandthisgivesacanonicallyisomorphicSDSS.Theorem4.3.(1)ybA2nSDSҰisindeffcomposable(w.r.t.FEproducts)ifandonlyiftheunder-%lying35grffaphisconnected.(2)%A2nySDSisuniquelyisomorphictotheprffoductofitscffonnectedcomponents,Fandthe%cffonnected35componentsareuniquelydetermined.Prffoof.#RIfKF}isapropSerproductthentheunderlyinggraphFisnotconnected.IfFhasmorethantFoneconnectedcompSonenrt,thenbytheprecedinglemmaitiscanonicallyisomorphictotheproSductofitsconnectedcomponenrtsasconstructedaborve.bTVoystudymorphismsofSDSxitsucestoknorwthemorphismsoftheform'UR:Fc!BG/BwhereGֹisindecompSosableorconnected.8ThisholdssinceNNzMorЦ(F1;G(1)$:::G(rG.,whereFǮandGL˹arearbitarySDS,canbSedescribedbryafamilyofmorphisms'j W:@MFi8:j !!Gjf ,9wheretheFi8:j 7aresuitable E¥[썍16t˾REINHARDTLA9UBENBACHERANDBODOP:AREIGISn썹indecompSosablepcomponenrtsofF1,QandtheGjrunthroughallrĉindecomposablecomponenrtsofG..8SowrecouldwritehG'UR=('1;:::ʜ;'rb):25ThereforeitissucienrtonlytostudymorphismsbSetweenindecompSosableSDS.!"W6.%Equalizers*Example6.1.+WVewranttogiveanexampleofanontrivialequalizerinthecategorySDS.This]willalsogivreussomeexamplesandshowthegreatvXarietyofmorphismsbSetweenfairlysmallSDS.*LetG]<:=G '(b);(kg);(gb=id qb); Q]=(b;b)G bSeanSDSontheonevrertexgraph.ThelocalandglobalhupSdatefunctionistheidenrtityhid^:URko!+Nkg.Finallyhtheupdatescrheduleisatwoletterwrord(b;b).]LetU6H:=oG >q(b);(kg);(hb K=oW); e=(b;b)G 8bSeU6anSDSTwithlocalfunction:ok%?!kg,the38transpSositionW(0)UR=1;(1)=0.WVeconstructtrwomorphisms';'20#:URG % !z_HPbry# y'g(b)UR=b;ԭe/'ᔹ(1)UR=1;#e'W{(2)UR=1; y'20RAg(b)UR=b;Fe'20H(1)UR=2;we='20(2)UR=2:Observre6thatthenumbSers1and2aretheindicesorpositionsofthelettersinthewrord(b;b).8FVurthermorewreuse'sn<[b]UR='20 TsD=[b]:=iduH:ko!+Nkg.*InordertocrheckthatthesearemorphismswreonlyhavetoshowthesecondpropSertyofmorphisms,namelythatthetrwodiagramsBX1k1k<:2fd!ά-'gi?b?=id*k*k<32fd!ά-Mh-:2Ob*=idzǠ@feǠ?w '-:UT=id¾zǠ@feǠ?Ǥ,'-:UT=id1k1>k,:2fd!ά-'gi?b?=id*k*>k,32fd!ά-l&nidjǠ@feϜǠ?'-:UT=idAjǠ@feAȜǠ?F{'-:UT=idcommrute. The`e rstdiagramarisesfromthecounterimageofthe rstletterof =UR(b;b)con-sistingzoftrwozinstancesoftheletterb,andtheseconddiagramarisesfromthecounrterimageofthesecondletterof =UR(b;b)thatisemptryV.8Similarlyweshowfor'20thatthediagramsCh1vk1vk̟:2fd!ά-'qgi?b?=id*vk*vk̞32fd!ά-l7id Ǡ@feE<Ǡ?VrO'-:0zP~=id Ǡ@fe><Ǡ?V'-:0,}Pс=id1AFk1A:Fk4:2fd!ά-'" I{-:iand1kg2n1Ckg2n$&:2fdά-nf,v+fLaG0*ak*FZk!U32fd!ά-l.\idpXǠ@feǠ? I{-:IiXǠ@feIǠ?NO I{-:foralla20#6=URainFƹ.*Norwde ne9 :wDFU!9&K*byg(b)wD:=a,sn<[b]= s[b],andDe (1):=i=jӹ.tThisisobrviouslytheonlyXqcrhoiceifwewanttoget=UR n9.#Thenwehaveǟ2=URsn<[b]pr ܟTaq:kg2n d ~J!ӞkandXqthediagramsC1r~kg2n1k~kg2n |:2fdά-'fa*Fk*?k932fd!ά-,la=idU:Ǡ@felǠ?R8-:N:Ǡ@feсlǠ?R83-:1)kg2n1-"kg2n :2fdά-nf}fLaG0*k*/k l32fd!ά-l1id Ǡ@fe?ܟǠ?R8v-:3Ǡ@fe38ܟǠ?R87\-:"commrute,henceistheuniquemorphismsuchthat=UR n9.8So(K,`;)isanequalizer.-FVorthenexttrworemarkswrewillassumeZ1=URfkg;id ʢk4g.?Remark6.2.zWVe wwranttoshowthat,-ingeneral,therearenoequalizersinthecategoryofSDS.LetG =UR(G;(kg[b]);(gb"ܹ); O)andHr=(HF:;(kg[c]);(hc.y); )bSethefollorwingSDS-%VG t:=URfa;b;c;dg,EG:=URffa;bg;fc;dgg,-%kg[b]UR:=ko=f0;1g꨹forallbUR2VG,-%gbx.:=URid forallbUR2VG,-% :=UR(a;b;c;d)=(b1;b2;b3;b4).-%VH n:=URfag,EF d:=;,-%kg[c]UR:=ko=f0;1g꨹forallcUR2VHD,-%hc˹:=URid forallcUR2VHD,-% n:=UR(a)=(c1).Let'; Ë:URG % !z_HPbSetrwomorphismsgivrenby-%'g(a)UR:=a, g(a):=c,-%'sn<[a]UR:=iduH=: s[a],U-'be%'-(1)UR:=1,Vke* i(1):=3.WVejWwrantto ndanequalizer.:EAkZ!G ofthesetrwomorphisms(i.e.'.= n9and(E;)univrersalw.r.t.8thispropSerty).E|¥[썍18t˾REINHARDTLA9UBENBACHERANDBODOP:AREIGISn썹AsatestobjectwreusetheSDSFc=UR(FS;(kg[a]);(faϹ); )de nedasfollows*-%VF d:=URfa;b;dg,EF:=URffa;bg;fa;dgg,-%kg[a]UR:=ko=f0;1g꨹forallaUR2VFO,-%faY!:=URid forallaUR2VFO,-% h:=UR(a;b;d)=(a1;a2;a3).TheUfollorwingtwomorphisms;o:URFc!BGshouldserveastestmorphisms.1Theyaregivenbry-%g(a)UR=g(c):=a,g(b):=b,g(d)=d,%g(a)UR=g(c):=a,g(b):=d,g(d)=b,-%sn<[a]UR:=iduH=:s[a]forallaUR2VG,-&e%,e(1)UR:=1,#Ee (2):=2,#Ee(3):=1,#Ee(4):=3,&me%,T(1)UR:=1,!e \(2):=3,!e(3):=1,!e(4):=2.Thenitiseasytoseethatn9'UR= XandW'= n9.*Assumethatwrehaveanequalizerҹ:E !9Gof'and n9.ThengܻmusthavethefollowingLȍimagesg(a)UR=g(c)=:za y(sinceg'g*P=g g),)g(b)=:W*bT<,)andg(d)=:Wh)*d iinVE-.FVurthermorelet`OeA µ(1)=:i1,veh ܹ(2)=:i2,veh ܹ(3)=:i3,hand`OeA µ(4)=:i4.ThenAwrehavei1 jȹ=We 8(1)=We 8e'l(1)=UeV7e*t !5(1)k=e {7(3)=i3.`mSincee "isorderpreservingontheconnectedcompSonenrts,#wegeti1+ki2andi1VURi4.!GSinceallofi1;i2;i4cmapinrtoaconnectedcompSonentofthegraphEW(theymapinrtoAa ҿ;Wu*b;Wչ*d ¾resp.)"wemusthavei2g¹andi4comparableintheorderofjs2j, theupSdatescrheduleofEù.The$morphisms$]and Aharve$uniquefactorizationsѤ=ck0 v(and=0 v(throughtheequalizer.'LNorwe0#(i2)UR=e q7(2)=2ande0(i4)UR=e q7(4)=3.'LSincee0نisorderpreservingwregeti2V<URi4.With,fthesameargumenrtforwegeti2=>9i4jacontradiction.Hencetherecannotexistanequalizerfor', n9.Remark6.3.InpthisconrtextandwithZ1=URfkg;id ʢk4gitmightappSearasifO=URGT(a);(kg);(id ʤ);(a)GisaninitialobjectinSDS.ThisisnotthecasesincethisSDSdoSesnotadmitamorphisminrtoanySDSwithupSdatefunctionsnottheidentityonthediagonalinkg2nm,thediagram?es1"^k1^k:2fd!ά-lUid*N6kg2n*G6kg2n432fdά- ,f 0Ǡ@fed$Ǡ?)Ǡ@fe]$Ǡ?VdoSesnotcommrute.>TVocompleteourstudyofproductswrehave,Chowever,theemptyproSduct.Lemma6.4.The35SDSG 7;;;UR=();;=();;=()G 7is35a nalobjeffctinSDS.čPrffoof.#RThereisauniquemorphismofgraphs;URn!1FnandthediagramA S1N6kg2n1G6kg2n4:2fdά-'?f8:id"fg]"fgĞ32fdά-lUid0Ǡ@fed$Ǡ?)Ǡ@fe]$Ǡ?mȍcommrutes.٘[ ¥[썍ZSEQUENTIAL!D9YNAMICALSYSTEMS^19n썍R7.a