Trace Semantics for Coalgebras Export

@article{citeulike:3735230, abstract = {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's final coalgebra gives rise to a weakly final coalgebra with state space P(Z), in a suitable category of coalgebras. Weak finality means that there is a coalgebra map X→P(Z), but there is no uniqueness. We show that there is a canonical choice among these maps X→P(Z), namely the largest one, describing the traces in a suitably abstract formulation. A crucial technical ingredient in our construction is a general distributive law FPimpliesPF, obtained via relation lifting.}, author = {Jacobs, B.}, citeulike-article-id = {3735230}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.entcs.2004.02.031}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S1571066104051746}, day = {11}, doi = {10.1016/j.entcs.2004.02.031}, issn = {15710661}, journal = {Electronic Notes in Theoretical Computer Science}, keywords = {category-theory, coalgebra, computation}, month = {December}, pages = {167--184}, posted-at = {2008-12-12 01:57:34}, priority = {2}, title = {Trace Semantics for Coalgebras}, url = {http://dx.doi.org/10.1016/j.entcs.2004.02.031}, volume = {106}, year = {2004} }

TY - JOUR ID - citeulike:3735230 L3 - citeulike-article-id:3735230 N2 - 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's final coalgebra gives rise to a weakly final coalgebra with state space P(Z), in a suitable category of coalgebras. Weak finality means that there is a coalgebra map X→P(Z), but there is no uniqueness. We show that there is a canonical choice among these maps X→P(Z), namely the largest one, describing the traces in a suitably abstract formulation. A crucial technical ingredient in our construction is a general distributive law FPimpliesPF, obtained via relation lifting. JF - Electronic Notes in Theoretical Computer Science SN - 15710661 EP - 184 TI - Trace Semantics for Coalgebras VL - 106 SP - 167 KW - category-theory KW - coalgebra KW - computation AU - Jacobs, B PY - 2004/12/11/ UR - http://dx.doi.org/10.1016/j.entcs.2004.02.031 ER -