Ziemiański) Martin Raussen

Hele teksten

(1)Spaces of directed paths as simplicial complexes Martin Raussen Department of Mathematical Sciences Aalborg University, Denmark. Seminar Algebraic Topology Faculty of Mathematics, Informatics and Mechanics University of Warsaw January 22, 2013 Martin Raussen. Spaces of directed paths as simplicial complexes.

(2) Table of Contents Agenda Examples: State spaces and associated path spaces in Higher Dimensional Automata (HDA) Motivation: from Concurrency Theory Simplest case: State spaces and path spaces related to linear PV-programs – mutual exclusion Tool: Cutting up path spaces into contractible subspaces Homotopy type of path space described by a matrix poset category and realized by a prodsimplicial complex Algorithmics: Detecting dead and alive subcomplexes/matrices Outlook: How to handle general HDA – with directed loops Case: Directed loops on a punctured torus (joint with K. Ziemiański) Martin Raussen. Spaces of directed paths as simplicial complexes.

(3) Intro: State space, directed paths and trace space Problem: How are they related?. Example 1: State space and trace space for a semaphore HDA. State space: a 3D cube ~I 3 \ F minus 4 box obstructions pairwise connected. Path space model contained in torus (∂∆2 )2 – homotopy equivalent to a wedge of two circles and a point: (S 1 ∨ S 1 ) t ∗. Analogy in standard algebraic topology Relation between space X and loop space ΩX . Martin Raussen. Spaces of directed paths as simplicial complexes.

(4) Intro: State space and trace space with loops. Example 2: Punctured torus. • •. •. •. •. •. •. •. •. •. X. • •. N •. •. •. State space: Punctured torus X and branch point N: 2D torus ∂∆2 × ∂∆2 with a rectangle ∆1 × ∆1 removed Martin Raussen. Path space model: Discrete infinite space of dimension 0 corresponding to {r , u }∗ . Question: Path space for a punctured torus in higher dimensions? Joint work with K. Ziemiański.. Spaces of directed paths as simplicial complexes.

(5) Why bother? Concurrency Definition from Wikipedia. Concurrency In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. The computations may be executing on multiple cores in the same chip, preemptively time-shared threads on the same processor, or executed on physically separated processors. A number of mathematical models have been developed for general concurrent computation including Petri nets, process calculi, the Parallel Random Access Machine model, the Actor model and the Reo Coordination Language. Specific applications to static program analysis – design of automated tools to test correctness etc. of a concurrent program regardless of specific timed execution. Martin Raussen. Spaces of directed paths as simplicial complexes.

(6) Mutual exclusion Semaphores. Mutual exclusion occurs, when n processes Pi compete for m resources Rj .. Only k processes can be served at any given time. Semaphores Semantics: A processor has to lock a resource and to relinquish the lock later on! Description/abstraction: Pi : . . . PRj . . . VRj . . . (E.W. Dijkstra) P: prolaag; V : verhogen Martin Raussen. Spaces of directed paths as simplicial complexes.

(7) A geometric model: Schedules in "progress graphs" Semaphores: The Swiss flag example T2 1 0. Vb Va Pa Pb. (0,0). 1 0 0 1 (1,1) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00000000 11111111 0 1 Un− 00000000 11111111 0 1 00000000 11111111 0 1 reachable 00000000 11111111 0 1 00000000 11111111 0 1 00000000 11111111 0 1 00000000 11111111 0 1 00000000 11111111 0 1 00000000 11111111 0 1 00000000 11111111 0 1 00000000 11111111 0 1 00000000 11111111 0 1 00000000 11111111 Unsafe 0 1 00000000 11111111 0 1 00000000 11111111 0 1 00000000 11111111 0 1 0 1 0 1 0 1 0 1 0 1 0 1 111111111111111111 000000000000000000 Pa. Pb. Vb. Va. T1. PV-diagram from P1 : Pa Pb Vb Va P2 : Pb Pa Va Vb. Martin Raussen. Executions are directed paths – since time flow is irreversible – avoiding a forbidden region (shaded). Dipaths that are dihomotopic (through a 1-parameter deformation consisting of dipaths) correspond to equivalent executions. Deadlocks, unsafe and unreachable regions may occur.. Spaces of directed paths as simplicial complexes.

(8) Simple Higher Dimensional Automata Semaphore models The state space A linear PV-program is modeled as the complement of a forbidden region F consisting of a number of holes in an n-cube: Hole = isothetic hyperrectangle R i =]a1i , b1i [× · · · ×]ani , bni [⊂ I n , 1 ≤ i ≤ l: with minimal vertex ai and maximal vertex bi . S State space X = ~I n \ F , F = li =1 R i X inherits a partial order from ~I n . d-paths are order preserving. More general concurrent programs. HDA. Higher Dimensional Automata (HDA, V. Pratt; 1990): Cubical complexes: like simplicial complexes, with (partially ordered) hypercubes instead of simplices as building blocksa d-paths are order preserving. a We. tacitly suppress labels Martin Raussen. Spaces of directed paths as simplicial complexes.

(9) Spaces of d-paths/traces – up to dihomotopy A general framework. Aims.. Definition X a d-space, a, b ∈ X . p : ~I → X a d-path in X (continuous and “order-preserving”) from a to b. ~P (X )(a, b ) = {p : ~I → X | p (0) = a, p (b ) = 1, p a d-path}. Trace space ~T (X )(a, b ) = ~P (X )(a, b ) modulo increasing reparametrizations. In most cases: ~P (X )(a, b ) ' ~T (X )(a, b ). A dihomotopy in ~P (X )(a, b ) is a map H : ~I × I → X such that Ht ∈ ~P (X )(a, b ), t ∈ I; ie a path in ~P (X )(a, b ). Aim: Description of the homotopy type of ~P (X )(a, b ) as explicit finite dimensional (prod-)simplicial complex. In particular: its path components, ie the dihomotopy classes of d-paths (executions). Martin Raussen. Spaces of directed paths as simplicial complexes.

(10) Tool: Subspaces of X and of ~P (X )(0, 1) X = ~I n \ F , F =. Sl. i =1 R. i ; Ri. =]ai , bi [; 0, 1 the two corners in I n .. Definition 1. Xij = {x ∈ X | x ≤ bi ⇒ xj ≤ aji } – direction j restricted at hole i. 2. M a binary l × n-matrix: XM =. T. mij =1 Xij. –. Which directions are restricted at which hole?. Examples: Two holes in 2D. –. M = 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1. Martin Raussen. One hole in 3D (dark) M= [100]. [010]. [001]. Spaces of directed paths as simplicial complexes.

(11) Covers by contractible (or empty) subspaces Bookkeeping with binary matrices. Binary matrices Ml,n poset (≤) of binary l × n-matrices R,∗ Ml,n no row vector is the zero vector – every hole obstructed in at least one direction. A cover by contractible subspaces Theorem 1. ~P (X )(0, 1) =. [. ~P (XM )(0, 1).. R,∗ M ∈Ml,n. 2. R,∗ , is Every path space ~P (XM )(0, 1), M ∈ Ml,n empty or contractible. Which is which?. Proof. R,∗ Subspaces XM , M ∈ Ml,n are closed under ∨ = l.u.b.. Martin Raussen. Spaces of directed paths as simplicial complexes.

(12) A combinatorial model and its geometric realization First examples. Topology: prodsimplicial complex T(X )(0, 1) ⊆ (∆n−1 )l ∆M = ∆m1 × · · · × ∆ml ⊆ T(X )(0, 1) – one simplex ∆mi for every hole. Combinatorics: poset category R,∗ C(X )(0, 1) ⊆ Ml,n ⊆ Ml,n M ∈ C(X )(0, 1) “alive”. ⇔ ~P (XM )(0, 1) 6= ∅. Examples of path spaces. T(X1 )(0, 1) = (∂∆1 )2 = 4∗ T(X2 )(0, 1) = 3∗ . 1 0 1 0. . 1 0 0 1. . 0 1 1 0. . 0 1 0 1. . Martin Raussen. ⊃ C(X )(0, 1). Spaces of directed paths as simplicial complexes.

(13) Further examples State spaces, “alive” matrices and path spaces 1. 2. X = ~I n \ ~J n C(X )(0, 1) = M1R,n,∗ \ {[1, . . . , 1]}. T(X )(0, 1) = ∂∆n−1 ' S n−2 . X = ~I n \ (~J0n ∪ ~J1n ) C(X )(0, 1) = M2R,n,∗ \ matrices with a [1, . . . , 1]-row. T(X )(0, 1) ' S n −2 × S n −2 .. t1. 1 t2. t2. 0 t0. t0. t1 t2. t1 t2. . Martin Raussen. t1. t0 1 0 0 0 0 1 alive. . 0 0 0 1 1 1 dead. t0. Spaces of directed paths as simplicial complexes.

(14) Why prodsimplicial? rather than simplicial. We distinguish, for every obstruction, sets Ji ⊂ [1 : n] of restrictions. A joint restriction is of product type J1 × · · · × Jl ⊂ [1 : n]l , and not an arbitrary subset of [1 : n ]l . l. l. Simplicial model: a subcomplex of ∆n – 2(n ) subsimplices. Prodsimplicial model: a subcomplex of (∆n )l – 2(nl ) subsimplices.. Martin Raussen. Spaces of directed paths as simplicial complexes.

(15) Homotopy equivalence between path space ~P (X )(0, 1) and prodsimplicial complex T(X )(0, 1) Theorem (A variant of the nerve lemma). ~P (X )(0, 1) ' T(X )(0, 1) ' ∆C(X )(0, 1). Proof. Functors D , E , T : C(X )(0, 1)(op) → Top: D(M ) = ~P (XM )(0, 1), E (M ) = ∆M , T (M ) = ∗ colim D = ~P (X )(0, 1), colim E = T(X )(0, 1), hocolim T = ∆C(X )(0, 1). The trivial natural transformations D ⇒ T , E ⇒ T yield: hocolim D ' hocolim T ∗ ' hocolim T ' hocolim E . Projection lemma: hocolim D ' colim D , hocolim E ' colim E .. Martin Raussen. Spaces of directed paths as simplicial complexes.

(16) Detection of dead and alive matrices & subcomplexes An algorithm starts with deadlocks and unsafe regions!. Allow less = forbid more! Remove extended hyperrectangles Rji := [0, b1i [× · · · × [0, bji −1 [×]aji , 1] × [0, bji +1 [× · · · × [0, bni [⊃ R i . XM = X \. S. i mij =1 Rj .. Theorem The following are equivalent: ~P (XM )(0, 1) = ∅ ⇔ M 6∈C(X )(0, 1). 1 C,u 2 There is a “dead” matrix N ≤ M, N ∈ Ml,n such that T i nij =1 Rj 6 = ∅ – giving rise to a deadlock unavoidable from 0, i.e., T (XN )(0, 1) = ∅. C,u Ml,n : every column a unit vector – every direction obstructed once. Martin Raussen. Spaces of directed paths as simplicial complexes.

(17) Dead matrices in D (X )(0, 1) Inequalities decide Decisions: Inequalities Deadlock algorithm (Fajstrup, Goubault, Raussen). :. Theorem C,u N ∈ Ml,n dead ⇔ For all 1 ≤ j ≤ n, for all 1 ≤ k ≤ n such that ∃j 0 : nkj 0 = 1:. nij = 1 ⇒ aji < bjk . R,∗ C,u M ∈ Ml,n dead ⇔ ∃N ∈ Ml,n dead, N ≤ M.. Definition C,u D (X )(0, 1) := {P ∈ Ml,n |∃N ∈ Ml,n , N dead : N ≤ P }.. A cube with a cubical hole X = ~I n \ ~J n C,u D (X )(0, 1) = {[1, . . . , 1]} = M1,n . Martin Raussen. Spaces of directed paths as simplicial complexes.

(18) Maximal alive ↔ minimal dead Still alive – not yet dead. Cmax (X )(0, 1) ⊂ C(X )(0, 1) maximal alive matrices. Matrices in Cmax (X )(0, 1) correspond to maximal simplex products in T(X )(0, 1). Connection: M ∈ Cmax (X )(0, 1), M ≤ N a succesor (a single 0 replaced by a 1) ⇒ N ∈ D (X )(0, 1). A cube with a cubical hole X = ~I n \ ~J n , D (X )(0, 1) = {[1, . . . , 1]};. Cmax (X )(0, 1): vectors with a single 0; R \ {[1, . . . , 1]}; C(X )(0, 1) = Ml,n T(X )(0, 1) = ∂∆n−1 .. Martin Raussen. Spaces of directed paths as simplicial complexes.

(19) From C(X )(0, 1) to properties of path space Questions answered by homology calculations using T(X )(0, 1) Questions Is ~P (X )(0, 1) path-connected, i.e., are all (execution) d-paths dihomotopic (lead to the same result)? Determination of path-components? Are components simply connected? Other topological properties? Strategies – Attempts Implementation of T(X )(0, 1) in ALCOOL at CEA/LIX-lab.: Goubault, Haucourt, Mimram The prodsimplicial structure on C(X )(0, 1) ↔ T(X )(0, 1) leads to an associated chain complex of vector spaces over a field. Use fast algorithms (eg Mrozek’s CrHom etc) to calculate the homology groups of these chain complexes even for quite big complexes: M. Juda (Krakow). Number of path-components: rkH0 (T(X )(0, 1)). For path-components alone, there are fast “discrete” methods, that also yield representatives in each path component (ALCOOL). Martin Raussen. Spaces of directed paths as simplicial complexes.

(20) Open problem: Huge complexes – complexity. Huge prodsimplicial complexes l obstructions, n processors: T(X )(0, 1) is a subcomplex of (∂∆n−1 )l : potentially a huge high-dimensional complex. Possible antidotes Smaller models? Make use of partial order among the obstructions R i , and in particular the inherited partial order among their extensions Rji with respect to ⊆. Work in progress: yields often simplicial complex of far smaller dimension!. Martin Raussen. Spaces of directed paths as simplicial complexes.

(21) Open problems: Variation of end points Conncection to MD persistence?. Components?! So far: ~T (X )(0, 1) - fixed end points. Now: Variation of ~T (X )(a, b) of start and end point, giving rise to filtrations. At which thresholds do homotopy types change? How to cut up X × X into components so that the homotopy type of trace spaces with end point pair in a component is invariant? Birth and death of homology classes? Compare with multidimensional persistence (Carlsson, Zomorodian).. Martin Raussen. Spaces of directed paths as simplicial complexes.

(22) Extensions. 1. Obstruction hyperrectangles intersecting the boundary of I n – why?. More general linear semaphore state spaces More general semaphores (intersection with the boundary ∂I n ⊂ I n allowed) n dining philosophers: Trace space has 2n − 2 contractible components! Different end points: ~P (X )(c, d) and iterative calculations End complexes rather than end points (allowing processes not to respond..., Herlihy & Cie) Dining philosophers. Martin Raussen. Spaces of directed paths as simplicial complexes.

(23) Extensions 2a. Semaphores corresponding to non-linear programs:. Path spaces in product of digraphs Products of digraphs instead of ~I n : Γ = ∏nj=1 Γj , state space X = Γ \ F , F a product of generalized hyperrectangles R i . ~P (Γ)(x, y) = ∏ ~P (Γj )(xj , yj ) – homotopy discrete! Pullback to linear situation Represent a path component C ∈ ~P (Γ)(x, y) by (regular) d-paths pj ∈ ~P (Γj )(xj , yj ) – an interleaving. The map c : ~I n → Γ, c (t1 , . . . , tn ) = (c1 (t1 ), . . . , cn (tn )) induces a homeomorphism ◦c : ~P (~I n )(0, 1) → C ⊂ ~P (Γ)(x, y).. Martin Raussen. Spaces of directed paths as simplicial complexes.

(24) Extensions 2b. Semaphores: Topology of components of interleavings. Homotopy types of interleaving components Pull back F via c: S X̄ = ~I n \ F̄ , F̄ = R̄ i , R̄ i = c −1 (R i ) – honest hyperrectangles! iX : ~P (X ) ,→ ~P (Γ). Given a component C ⊂ ~P (Γ)(x, y). The d-map c : X̄ → X induces a homeomorphism c ◦ : ~P (X̄ )(0, 1) → iX−1 (C ) ⊂ ~P (Γ)(x, y). C “lifts to X ” ⇔ ~P (X̄ )(0, 1) 6= ∅; if so: Analyse iX−1 (C ) via ~P (X̄ )(0, 1). Exploit relations between various components. Special case: Γ = (S 1 )n – a torus State space: A torus with rectangular holes in F : Investigated by Fajstrup, Goubault, Mimram etal.: Analyse by language on the alphabet C(X )(0, 1) of alive matrices for a one-fold delooping of Γ \ F . Martin Raussen. Spaces of directed paths as simplicial complexes.

(25) Extensions 3a. D-paths in pre-cubical complexes. HDA: Directed pre-cubical complex Higher Dimensional Automaton: Pre-cubical complex – like simplicial complex but with cubes as building blocks – with preferred diretions. Geometric realization X with d-space structure. Branch points and branch cubes These complexes have branch points and branch cells – more than one maximal cell with same lower corner vertex. At branch points, one can cut up a cubical complex into simpler pieces. Trouble: Simpler pieces may have higher order branch points.. AO. /• O. /• O. /1 O. /• O. /• O. /• O. /C O. /• O. /• O. c11. •O c12. b12. BO 1. b11. b22. 0 Martin Raussen. a2. / B2. c21 b21. c22. /•. a1. /A. Spaces of directed paths as simplicial complexes.

(26) Extensions 3b. Path spaces for HDAs without d-loops Non-branching complexes Start with complex without directed loops: After finally many iterations: Subcomplex Y without branch points. Theorem ~P (Y )(x0 , x1 ) is empty or contractible. Proof. Such a subcomplex has a preferred diagonal flow and a contraction from path space to the flow line from start to end. Branch category Results in a (complicated) finite branch category M(X )(x0 , x1 ) on subsets of set of (iterated) branch cells. Theorem ~P (X )(x0 , x1 ) is homotopy equivalent to the nerve N (M(X )(x0 , x1 )) of that category. Martin Raussen. Spaces of directed paths as simplicial complexes.

(27) Extensions 3c. Path spaces for HDAs with d-loops. Delooping HDAs A pre-cubical complex comes with an L1 -length 1-form ω reducing to ω = dx1 + · · · + dxn on every n-cube. Integration: L1 -length on rectifiable paths, homotopy invariant. Defines l : P (X )(x0 , x1 ) → R and l] : π1 (X ) → R with kernel K . The (usual) covering X̃ ↓ X with π1 (X̃ ) = K is a directed pre-cubical complex without d- loops. Theorem (Decomposition theorem) For every pair of points x0 , x1 ∈ X , path space ~P (X )(x0 , x1 ) is F homeomorphic to the disjoint union n∈Z ~P (X̃ )(x00 , xn1 )a . a in. the fibres over x0 , x1. Martin Raussen. Spaces of directed paths as simplicial complexes.

(28) Case: d-paths on a punctured torus Punctured torus and n-space n-torus T n = Rn /Zn . forbidden region F n = ([ 14 , 43 ]n + Zn )/Zn ⊂ T n . punctured torus Q n = T n \ F n ' T(nn−1) punctured n-space Q̃ n = Rn \ ([ 41 , 43 ]n + Zn ) ' Rn(n−1) with d-paths from quotient map Rn ↓ T n . Aim: Describe the homotopy type of ~P (Q ) = ~P (Q )(0, 0) F ~P (Q ) ,→ ΩQ (0, 0) disjoint union ~P (Q ) = k≥0 ~P (k)(Q ) with multiindex = multidegree k = (k1 , . . . , kn ) ∈ Zn+ , ki ≥ 0. ~P (k)(Q ) ∼ = ~P (Q̃ n )(0, k) =: Z (k).. Martin Raussen. Spaces of directed paths as simplicial complexes.

(29) Path spaces as colimits Category J (n) Poset category of proper non-empty subsets of [1 : n] with inclusions as morphisms. Via characteristic functions isomorphic to the category of non-identical bit sequences of length n: ε = (ε 1 , . . . ε n ) ∈ J (n). B J (n ) ∼ = ∂∆n−1 ∼ = S n −2 . Definition Uε (k) := {x ∈ Rn | ε j = 1 ⇒ xj ≤ kj − 1 or ∃i : xi ≥ ki } Zε (k) := ~P (Uε (k))(0, k). Lemma Zε (k ) ' Z (k − ε ). Theorem Z (k) = colimε∈J (n) Zε (k) ' hocolimε∈J (n) Zε (k) ' hocolimε∈J (n) Z (k − ε). Martin Raussen. Spaces of directed paths as simplicial complexes.

(30) An equivalent homotopy colimit construction Inductive homotopy colimites Using the category J (n) construct for k ∈ Zn , k ≥ 0: X (k) = ∗ if ∏n1 ki = 0; X (k) = hocolimε∈J (n) X (k − ε). By construction k ≤ l ⇒ X (k) ⊆ X (l); X (1) ∼ = ∂∆n−1 . Inductive homotopy equivalences q (k) : Z (k) → X (k): ∏n1 ki = 0 ⇒ Z (k) contractible, X (k) = ∗ q (k) = hocolimε∈J (n) q (k − ε) : Z (k) ' hocolimε∈J (n) Z (k − ε) → hocolimε∈J (n) X (k − ε) = X (k).. Martin Raussen. Spaces of directed paths as simplicial complexes.

(31) Homology and cohomology of space Z (k) of d-paths Definition l m ∈ Zn+ ⇔ lj < mj , 1 ≤ j ≤ n.. O n = {(l, m)| l m or m l} ⊂ Zn+ × Zn+ . B(k) := Zn+ (≤ k) × Zn+ (≤ k) \ O n – unordered pairs I(k) :=< lm| (l, m) ∈ B(k) >≤ Z < Zn+ (≤ k) >. Theorem For n > 2, H ∗ (Z (k)) = Z < Zn+ (≤ k) > /I(k) . All generators have degree n − 2. H∗ (Z (k)) ∼ = H ∗ (Z (k)) as abelian groups. Proof Spectral sequence argument, using projectivity of the functor H∗ : J (n) → Ab∗ , k 7→ H∗ (Z (k)). Martin Raussen. Spaces of directed paths as simplicial complexes.

(32) Interpretation via cube sequences Betti numbers Cube sequences. [a∗ ] := [0 a1 a2 · · · ar = l] ∈ Anr(n−2) (l) of size l ∈ Zn+ , length r and degree r (n − 2). An∗ (∗) the free abelian group generated by all cube sequences. L An∗ (≤ k) := l≤k An∗ (l). Hr (n−2) (Z (k)) ∼ = Anr(n−2) (≤ k) generated by cube sequences of length r and size ≤ k. Betti numbers of Z (k) Theorem n = 2: β 0 = (k1k+1k2 ); β j = 0, j > 0;. n > 2: β 0 = 1, β i (n−2) = ∏n1 (kij ), β j = 0 else.. Corollary 1 2. Small homological dimension of Z (k): (minj kj )(n − 2). For k = (k , . . . , k ), β i (Z (k)) = β k (n−2)−i (Z (k)). Martin Raussen. Spaces of directed paths as simplicial complexes.

(33) Generalization. “Explanation” The result can be stated and generalized for a complex T(nn−1) ⊂ K ⊂ T n – with universal cover Rn(n−1) ⊂ K̃ ⊂ Rn . Homology is generated by cube sequences [a∗ ] := [0 a1 a2 · · · ar = l] such that the cells [ai − 1, ai ] 6⊂ K̃ . A cube sequence a∗ is maximal if it is not properly contained in another cube sequence with same endpoints. A maximal cube sequence a∗ gives rise to a subspace ~P (a∗ )(0, k) ⊂ ~P (K̃ )(0, k) – concatenation of paths on boundary of cubes [ai − 1, ai ] and contractible path spaces. S Y (k) = a∗ ~P (a∗ )(0, k), a∗ maximal. Then also Y (k) ' hocolimε∈J (n) Y (k − ε) and Y (k) contractible if ∏i ki = 0. Hence Y (k) ' X (k) ' Z (k). ~P (a∗ )(0, k) ⊂ ~P (K̃ )(0, k) induces an injection H ∗ (~P (a∗ )(0, k)) ∼ = H ∗ ((S n−2 )r ) → H ∗ (~P (K̃ )(0, k)). Martin Raussen. Spaces of directed paths as simplicial complexes.

(34) To conclude Conclusions and challenges From a (rather compact) state space model (shape of data) to a finite dimensional trace space model (represent shape). Calculations of invariants (Betti numbers) of path space possible for state spaces of a moderate size (measuring shape). Dimension of trace space model reflects not the size but the complexity of state space (number of obstructions, number of processors); still: curse of dimensionality. Challenge: General properties of path spaces for algorithms solving types of problems in a distributed manner? Connections to the work of Herlihy and Rajsbaum – protocol complex etc Challenge: Morphisms between HDA d-maps between cubical state spaces functorial maps between trace spaces. Properties? Equivalences? Martin Raussen. Spaces of directed paths as simplicial complexes.

(35) Want to know more? Books Kozlov, Combinatorial Algebraic Topology, Springer, 2008. Grandis, Directed Algebraic Topology, Cambridge UP, 2009. Articles MR, Simplicial models for trace spaces, AGT 10 (2010), 1683 – 1714. MR, Execution spaces for simple HDA, Appl. Alg. Eng. Comm. Comp. 23 (2012), 59 – 84. MR, Simplicial models for trace spaces II: General Higher Dimensional Automata, AGT 12 (2012), 1741 – 1761. Fajstrup, Trace spaces of directed tori with rectangular holes, Aalborg University Research Report R-2011-08. Fajstrup et al., Trace Spaces: an efficient new technique for State-Space Reduction, Proceedings ESOP, Lect. Notes Comput. Sci. 7211 (2012), 274 – 294. Rick Jardine, Path categories and resolutions, Homology, Homotopy Appl. 12 (2010), 231 – 244. Martin Raussen. Spaces of directed paths as simplicial complexes.

(36) Advertisement for ACAT Thank you!. ESF network ACAT. Applied and Computational Algebraic Topology http: http://acat.lix. //www.esf.org/acat polytechnique.fr/ Thank you for your attention! Martin Raussen. Spaces of directed paths as simplicial complexes.

(37)