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
Abstract Trace Semantics... 暂无评价 16页 免费 Escape Constructs in Dat.....On coalgebras and nal semantics progress report This report summarises research...
Technical Report Complete Abstract Operational Semantics for the Web Service Business Proce_专业资料。In this technical report we present an abstract operational...
ISSN 1361 - 6161 Computer Science University of Manchester A Fibration Semantics for Pi-Calculus Modules via Abstract MONSTR Rule Systems R. Banach Department...
The abstract mathematical structures known as coalgebras are of increas-ing interest...nite data structures and providing semantics for object-oriented programming...
Thesis — Ctlin Hritcu Semantics of Imperative Objects Context. The object ...A typed, compositional logic for a stack-based abstract machine. In Zoltan...
4页 免费 Abstract Web Semantics 暂无评价 15页 免费 Robust photo retrieval u... 暂无评价 6页 免费 Robust Semantics for Arg... 暂无评价 51页 免费搜...
Categorical Models for Fairness and a Fully Abstract Presheaf Semantics of SCCS...nal coalgebras and meanings of ?nite delay by initial algebras of the ...
Process semantics and Pr... 暂无评价 13页 免费 Trace-Based Abstract Int....of coalgebras does not extend easily to other known equivalences on processes...
Operational Semantics for Declarative Multi-Paradigm Languages_专业资料。Abstract. In this paper we define an operational semantics for functional logic languages...
Abstract We present a static and dynamic semantics for an abstract machine that evaluates expressions of a polymorphic programming language. Unlike traditional ...
热门文档