文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

Thispaperstartswithtwopreliminarysections,oneontraditionaltracesemanticsforlabeledtransitionsystems,andoneonrelationliftingassociatedwithanendofunctor.Then,Section4describesthegeneraldistributivelawFP PFthatformsthebasisofourwork,andSection5introducesanap-propriatecategoryofcoalgebrasoveraKleislicategoryforourtracesemantics.Ourmainresultaboutaweakly nalcoalgebraoftracesisinSection6.2Traditionaltracesemantics

Thissectionsketchesthebasicsoftraditionaltracesemanticsforlabeledtran-sitionsystems(LTSs).Suchasystemisdescribedasacoalgebraα:X→P(A×X),where

XisthesetofstatesAisthesetoflabels(oractions)αdescribesthetransitionsx →x ,namelyas(a,x )∈α(x).a

ForsuchanLTSonecanformthesetUofin nitepathsas:

nU={( x0,a0 , x1,a1 ,...)∈(X×A)N| n∈N.xn →xn+1}a

Witheachstatex∈Xonecanthenassociateanin nitetrace (x)∈P(AN),namely

(1)N(u)|u∈Uwithπ1(u0)=x}. (x)={π2defn

NHerewewriteπ2fortheelement-wiseextensionofthesecondprojection

π2:X×A→Atoaffunction(X×A)N→AN.

Itisnothardtoseethatthisfunction :X→P(AN)satis es:

(2) (x)={a·σ| x ∈X.x →x andσ∈ (x )}.a

wherethedotina·σdescribespre xing.

Thefollowingsimpleexampleshowsthattheequation(2)doesnotuniquelydetermine (x).ConsidertheLTSgivenbythefollowingtransitions:

c

b

HencethisLTSiscapturedbyX={x},A={b,c}andα(x)={(b,x),(c,x)}.Theset (x)isthen{b,c}N,i.e.containsallin nitesequenceswithelementsbandc.However,thepropersubset

(3)k(x)={σ∈ (x)|boccursin nitelyofteninσ}

alsosatis es(2).Fortheinclusion( )assumeσ∈k(x),sothatσcontainsin nitelymanyb’s.Ifwewriteσ=a·σ ,wherea∈{b,c},thenclearlythetail

2

上一页第2页

你可能喜欢

热门文档

相关文档

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