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

TraceSemanticsforCoalgebras

BartJacobs

DepartmentofComputerScience,UniversityofNijmegen

P.O.Box9010,6500GLNijmegen,TheNetherlands

Email:bart@cs.kun.nlURL:doc.guandang.net~bartAbstract

Traditionally,tracesarethesequencesoflabelsassociatedwithpathsintransitionsystemsX→P(A×X).Herewedescribetracesmoregenerally,forcoalgebrasoftheformX→P(F(X)),whereFisapolynomialfunctor.Themainresultstates~=thatF’s nalcoalgebraZ →F(Z)givesrisetoaweakly nalcoalgebrawithstatespaceP(Z),inasuitablecategoryofcoalgebras.Weak nalitymeansthatthereisacoalgebramapX→P(Z),butthereisnouniqueness.WeshowthatthereisacanonicalchoiceamongthesemapsX→P(Z),namelythelargestone,describingthetracesinasuitablyabstractformulation.AcrucialtechnicalingredientinourconstructionisageneraldistributivelawFP PF,obtainedviarelationlifting.1Introduction

~=A nalcoalgebraZ →F(Z)ofafunctorFisanabstractmodelconsistingof

behavioursofthekinddescribedbythefunctor(orinterface)F.TheelementsofZare“structured”inthesensethatthetransitionstructureisincorporated.Theassociatednotionofequivalenceis“strong”bisimulation.Itarisesasthenaturalnotionofequivalencewithinthetheoryofcoalgebras.

Tracesemanticsinvolvesonlylinearbehavioursconsistingofsequencesofconsecutiveactions,seeforinstance[2]foradiscussion.Itismuchmoreproblematicwithinthetheoryofcoalgebras.Partialresultsmaybefoundin[5],forcoalgebrasoftheformX→P(1+(A×X)).Herewegeneralisetheapproachfrom[5]tocoalgebrasoftheformX→P(F(X)).Thisisachievedbygeneralisingthedistributivelawthatisusedin[5]tooneoftheformFP PF.

Oncetheappropriateabstractionlevelisachieved,wearenotdone,sincethetechnicalelaborationappearsnon-trivial.MuchoftheworkfocussesongeneraltracesofcoalgebrasX→P(F(X))andontheirproperties.1ProceedingsofCoalgebraicMethodsinComputerScience(CMCS)2004.

Thisisapreliminaryversion.The nalversionwillbepublishedinElectronicNotesinTheoreticalComputerScienceURL:doc.guandang.net

第1页

你可能喜欢

热门文档

相关文档

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