The context of the talk is the geometric semantics of concurrent programs; in
that context, properties of interest of concurrent programs are described as
certain directed homotopy invariants, among which the fundamental category, i.e.
the category of directed paths (or traces) modulo directed homotopy. Trace
spaces have been introduced recently by Martin Raussen, as a means to represent
the structure of directed paths in directed topological spaces, and as a means
to represent some information about the fundamental category, in particular. In
this talk, I am going to present some of the algorithmics that allows for
finitely presenting these structures, in some interesting cases. Although based
on an algebraic topological approach, the computations involve boolean matrices
and combinatorial problems, such as minimal hypergraph transversals. If time
permits, I will sketch some applications of this to static analysis, and
fault-tolerant protocols for distributed systems. This is joint work with Samuel
Mimram, Emmanuel Haucourt, Martin Raussen, Lisbeth Fajstrup and Christine
Tasson, and part of it will be presented at ESOP 2012.