#
Combinatorics of branchings in higher dimensional automata

##
Philippe Gaucher

We explore the combinatorial properties of the branching areas of
execution paths in higher dimensional automata. Mathematically, this
means that we investigate the combinatorics of the negative corner
(or branching) homology of a globular $\omega$-category and the
combinatorics of a new homology theory called the reduced branching
homology. The latter is the homology of the quotient of the
branching complex by the sub-complex generated by its thin elements.
Conjecturally it coincides with the non reduced theory for higher
dimensional automata, that is $\omega$-categories freely generated
by precubical sets. As application, we calculate the branching
homology of some $\omega$-categories and we give some invariance
results for the reduced branching homology. We only treat the
branching side. The merging side, that is the case of merging areas
of execution paths is similar and can be easily deduced from the
branching side.

Keywords: cubical set, thin element, globular higher dimensional category, branching,
higher dimensional automata, concurrency, homology theory.

2000 MSC: 55U.

*Theory and Applications of Categories*, Vol. 8, 2001, No. 12, pp 324-376.

http://www.tac.mta.ca/tac/volumes/8/n12/n12.dvi

http://www.tac.mta.ca/tac/volumes/8/n12/n12.ps

http://www.tac.mta.ca/tac/volumes/8/n12/n12.pdf

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/8/n12/n12.dvi

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/8/n12/n12.ps

TAC Home