文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Abstract Trace Semantics for Coalgebras
侵权投诉

Abstract Trace Semantics for Coalgebras

Traditionally, traces are the sequences of labels associated with paths in transition systems X → P(A × X). Here we describe traces more generally, for coalgebras of the form X → P(F (X)), where F is a polynomial functor. The main result states that F

σ mustalsocontainin nitelymanyb’s.Thereverseinclusion( )isobtainedsimilarly.

Wehavetworemarks.

Thislastexampleshowsthatuniquenessisnotpartoftracesemantics(inthismanner),andthusthatatracefunction willnotariseasmaptoa nalcoalgebra.However,asourmainresult(Theorem6.5)shows,itdoesariseascanonicalmaptoaweakly nalcoalgebra.This“weakness”meansexistence,butnotuniqueexistence.

Despitethislackofuniqueness,tracesemanticsisusefulforthecompar-isonofstates,namelyviatraceinclusionortraceequalitybetweenstates.Thispaperhowever,focusesexclusivelyontheabstracttheory,andnotonapplications.

Onemaywishtoinclude nitetraces—andnotonlyin niteones.Atypicalwayofdoingthisisviaauxiliarytransitionsthatarerepeatedoverandoveragainoncea nalstateisreached.ThenonemayalsorestrictoneselftocoalgebrasoftheformX→P (A×X)forthepowersetP ofnon-emptysets.Weshallnotdoso.

TracesemanticsforLTSs,moreabstractly 2.1

Beforeweproceedtoacoalgebraicapproachtotracesemantics,weliketoidentifythecrucialstepsofthismoreabstractapproachforanLTSα:X→P(A×X)asconsideredabove.We rstnoticethatitsfunctorP(A× )canbewrittenasPF,thereF=A× .The nalcoalgebraofFisofcoursethe~=→setANofin nitesequences,givenbytheheadandtailoperation h,t :AN

NA×A.Interestingly,thesetUofin nitetracescarriesanF-coalgebrastruc-tureU→A×U,givenby( x0,a0 , x1,a1 ,...) → a0,( x1,a1 ,...) .The

Ninducedmaptothe nalcoalgebraisπ2:U→AN,asusedinthede nition(1).

InthemoreabstractapproachintheremainderofthispaperweshallallowmoregeneralfunctorsFforcoalgebraX→P(FX).Acrucialstepistogiveanappropriatede nitionofthesetUofin nitepaths,withanF-coalgebrastructure.ThisyieldsamapU→Ztothe nalF-coalgebraZ,andhenceatracemapX→P(Z).

3Coalgebraicpreliminaries

WeshallrestrictourselvestocoalgebrasX→F(X)ofendofunctorsF:Sets→Sets.Later,inSection6weshallfurtherrestricttheseF’stoso-calledpoly-nomialfunctors,builtupfromtheidentity,constantfunctors,product,co-productsandexponents( )Awithaconstantset,seeforinstace[3].

AssociatedwithafunctorF:Sets→Setswecande newhatisusuallycalledrelationlifting.ItisanextensionRel(F)ofFfromsetstorelations,inthesensethatR X×YismappedtoRel(F)(R) F(X)×F(Y).Itmaybede nedingeneraltermsviaepi-monofactorisation:ifwehave

3

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email