Scheduling spaces in concurrency via directed topology

Wednesday, December 4, 2013 - 1:30pm - 2:30pm
Lind 305
Martin Raussen (Aalborg University)
Concurrency theory in Computer Science studies the effects that arise when
several processors run simultaneously sharing common resources. It
attempts to advise methods to deal with the state space explosion
problem, sometimes using models with a combinatorial/topological flavor.
It is a common feature of these models that a schedule corresponds to a
directed path (d-path), and that d-homotopies (preserving the directions)
result in computations with the same result.

I shall discuss particular classical examples of directed spaces, a class
of Higher Dimensional Automata (HDA). For such a state space, I shall
describe a (nerve lemma) method that determines the homotopy type of the
space of traces (schedules) as a prodsimplicial complex - with products of
simplices as building blocks. A description of that complex opens up for
(machine) calculations of homology groups and other topological invariants
of the trace space. The determination of the path components of trace
space is particularly important for applications.

Unfortunately, the resulting prodsimplicial complexes grow still quickly
in both dimension and the number of cells. I shall sketch ongoing work
with K. Ziemiański (Warsaw) that tries to find smaller homotopy equivalent
simplicial complexes via suitable homotopy decompositions of trace spaces.