Academic
Publications
Combinatorics of labelling in higher-dimensional automata

Combinatorics of labelling in higher-dimensional automata,10.1016/j.tcs.2009.11.013,Theoretical Computer Science,Philippe Gaucher

Combinatorics of labelling in higher-dimensional automata   (Citations: 3)
BibTex | RIS | RefWorks Download
The main idea for interpreting concurrent processes as labelled precubical sets is that a given set of n actions running concurrently must be assembled to a labelled n- cube, in exactly one way. The main ingredient is the non-functorial construction called labelled directed coskeleton. It is defined as a subobject of the labelled coskeleton, the latter coinciding in the unlabelled case with the right adjoint to the truncation functor. This non- functorial construction is necessary since the labelled coskeleton functor of the category of labelled precubical sets does not fulfil the above requirement. We prove in this paper that it is possible to force the labelled coskeleton functor to be well-behaved by working with labelled transverse symmetric precubical sets. Moreover, we prove that this solution is the only one. A transverse symmetric precubical set is a precubical set equipped with symmetry maps and with a new kind of degeneracy map called transverse degeneracy. Finally, we also prove that the two settings are equivalent from a directed algebraic topological viewpoint. To illustrate, a new semantics of CCS, equivalent to the old one, is given.
Journal: Theoretical Computer Science - TCS , vol. 411, no. 11-13, pp. 1452-1483, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...It was introduced a first time in [Gou02] [Wor04], after some ideas coming from [Dij68] [Pra91] [Gun94] [Gla04] (the last paper is a recent survey containing references to older papers), and improved in [Gau08b] [Gau08a] in relation with the study of process algebras...
    • ...The paper [Gau08b] treated the case of labelled precubical sets, and the paper [Gau08a] the more general cases of labelled symmetric precubical sets and labelled symmetric transverse precubical sets...
    • ...Theorem. (Theorem 9.2, Theorem 9.5, Theorem 12.7 and Corollary 13.7) The mapping defined in [Gau08b] and [Gau08a] taking each CCS process name to the geometric realization as flow |� SJP K|flow of the labelled symmetric precubical set � SJP K factors through Cattani-Sassone’s category of higher dimensional transition systems, i.e...
    • ...Let us recall for the reader that the semantics of process algebras used in this paper in Section 13 is the one of [Gau08a]...
    • ...On the contrary, as already explained in [Gau08b] and in [Gau08a], there exist labelled (symmetric) precubical sets containing n-tuples of actions running concurrently which assemble to several different n-cubes...
    • ...This section collects several information scattered between [Gau08b] and [Gau08a]...
    • ...CCS (Milner’s calculus of communicating systems [Mil89]) for mathematician is available in [Gau08b] and in [Gau08a]...
    • ...12.5. Definition. [Gau08b] [Gau08a] Let K be a labelled symmetric precubical set...
    • ...First we recall the semantics of process algebra given in [Gau08b] and [Gau08a]...
    • ...Let (� S)n ⊂ � S be the full subcategory of � S containing only the [p] for p 6 n. By [Gau08a, Proposition 5.4], the truncation functor � op Set↓! S � → (� S) op Set↓! S � has a right adjoint cosk �S,� n : (� S) op Set↓! S � → � op S Set↓! S �...
    • ...It would be also interesting to find the analogue of the notion of weak higher dimensional transition system for the labelled symmetric transverse precubical sets (the presheaves over b � ) introduced in [Gau08a]...

    Philippe Gaucher. Directed algebraic topology and higher dimensional transition system

Sort by: