Abstract. We present a presheaf model for the observation of infinite as well as finite computations. We apply it to give a denotational semantics of SCCS with finite delay, in which the meanings of recursion are given by final coalgebras and meanings of f
CategoricalModelsforFairnessandaFullyAbstractPresheafSemanticsofSCCSwithFiniteDelay
ThomasT.Hildebrandt
TheITUniversityofCopenhagen,Denmark,
hilde@it-c.dk
Abstract.Wepresentapresheafmodelfortheobservationofin niteaswellas nitecomputations.WeapplyittogiveadenotationalsemanticsofSCCSwith nitedelay,inwhichthemeaningsofrecursionaregivenby nalcoalgebrasandmeaningsof nitedelaybyinitialalgebrasoftheprocessequationsfordelay.Thiscanbeviewedasa rststepinrepresentingfairnessinpresheafsemantics.Wegiveaconcreterepresentationofthepresheafmodelasacategoryofgen-eralisedsynchronisationtreesandshowthatitiscore ectiveinacategoryofgeneralisedtransitionsystems,whichareaspecialcaseofthegeneraltransitionsystemsofHennessyandStirling.Theopenmapbisimulationisshowntoco-incidewithextendedbisimulationofHennessyandStirling,whichisessentiallyfairCTL-bisimulation.FinallyweformulateMilnersoperationalsemanticsofSCCSwith nitedelayintermsofgeneralisedtransitionsystemsandprovethatthepresheafsemanticsisfullyabstractwithrespecttoextendedbisimulation.Introduction
Whenreasoningaboutanddescribingthebehaviourofconcurrentagentsitisoftenthecasethatsomein nitecomputationsareconsideredunfairandconsequentlyruledoutasbeinginadmissible.AneconomicalwayofstudyingthissituationwasproposedbyMilnerin[25]showinghowtoexpressafairasynchronousparallelcompositioninhiscalculusSCCS(SynchronousCCS)byaddinga nite,butunboundeddelayoperator.Syntactically,the nitedelayofanagentiswritten.Theintendedsemanticsisthatcanperformanunboundednumberof-actions(delays)butmusteventuallyperformanaction,changingtoanagent,ifcanperformthisactionandchangeto,oritmusteventuallystop,ifcannotperformanyactions.Inotherwords,itsactionsarethesameasfor(thepossiblyin nitedelay),exceptthatin niteunfoldingoftherecursionisnotallowed.
Todealwithagentsinwhichonlysomein nitecomputationsareadmissible,onemustreaddresstheissueofhowtorepresentthebehaviourofagentsandsowhentwoagentsbehaveequally,i.e.theydenotethesameprocess.TheapproachusedforCCSandSCCS,takingtwoagentstobeequivalentiftheirderivationtreesarestrongbisimi-lar[23],willidentifyagentsthatonlydifferonwhethersomein nitecomputationsare
Towards categorical models for fairness fully abstract presheaf semantics of SCCS with fini Towards categorical models for fairness fully abstract presheaf semant...
Towards categorical models for fairness fully abstract presheaf semantics of SCCS with fini_专业资料。Towards categorical models for fairness fully abstract pres...
Towards categorical models for fairness fully abstract presheaf semantics of SCCS with fini_专业资料。Towards categorical models for fairness fully abstract pres...
热门文档