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

r1,r2 :R →X×Y,then:

F(R)Rel(F)(R)SSSSSSSSS F(r1),F(r2) SSSSF(X)×F(Y)

Forpolynomialfunctorsonecandescribethisrelationliftingconvenientlyviaaninductivede nition,see[3].Thefollowinglistsumsupthebasicresultsthatweneedaboutrelationlifting.

(i)Equalityispreserved:Rel(F)(=X)==F(X).

(ii)Compositionispreserved:forR X×YandS Y×Z,therelational

compositionS R={(x,z)| y.R(x,y)∧S(y,z)}satis es:

Rel(F)(S R)=Rel(F)(S) Rel(F)(R).

(iii)Inclusionsarepreserved:ifR SthenRel(F)(R) Rel(F)(S).

(iv)Inverseimages(orsubstitution,orreindexing)anddirectimagespre-

served:forfunctionsf1:X1→Y1,f2:X2→Y2andrelationsS Y1×Y2andR X1×X2wehave:

Rel(F)(f1×f2) 1(S)=(F(f1)×F(f2)) 1Rel(F)(S) Rel(F)f1×f2(R)=F(f1)×F(f2)Rel(F)(R),

where,ingeneral h(P)={x| y.x=h(y)∧y∈P}={h(y)|y∈P}.AllthesepropertiesholdforfunctorsFthatpreserveweakpullbacks,see[6],andhenceinparticularforpolynomialfunctors.

Weshallneedthefollowingnon-standardresultaboutrelationlifting.Lemma3.1Assumearelation r1,r2 :R X×Y,withassociatedrelationlifting p1,p2 :Rel(F)(R) F(X)×F(Y).Assumewehaveadiagram

TW

1RZSYZ2XZ

Thenwehaveaninclusion,asindicatedbythedashedarrow,in:

Rel(F)(TO)_____OOOOOOOOOO

1Rel(F)(R)×FZ

4Rel(F)(S)FYFZ2FXFZ

上一页第4页

你可能喜欢

热门文档

相关文档

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