Trace spaces:
Organization, Calculations, Applications
Martin Raussen
Department of Mathematical Sciences Aalborg University
Denmark
ATMCS III, Paris, July 2008
Martin Raussen Trace spaces: Organization, Calculations, Applications
Outline
Outline
1. Motivations, mainly from Concurrency Theory 2. Directed topology: algebraic topology with a twist 3. Trace spaces: definitions, calculations via classical
algebraic topology
4. Categorical organization of invariants Main Collaborators:
◮ Lisbeth Fajstrup (Aalborg), ´Eric Goubault, Emmanuel Haucourt (CEA and X, France)
Motivation: Concurrency
Mutual exclusion
Mutual exclusion occurs, when n processes Pi compete for m resources Rj.
P P
1 2
R 1
P3
R2
Only k processes can be served at any given time.
Semaphores!
Semantics: A processor has to lock a resource and relinquish the lock later on!
Description/abstraction Pi : . . .PRj. . .VRj. . . (Dijkstra)
Martin Raussen Trace spaces: Organization, Calculations, Applications
Schedules in ”progress graphs”
The Swiss flag example
Unsafe
Un- reachable
(0,0)
Pa Pb Vb Va Pb
Pa Va Vb T2
T1 (1,1)
- 6
PV-diagram from P1:PaPbVbVa
P2:PbPaVaVb
Executions aredirected paths – since time flow is irreversible – avoiding a forbidden region(shaded).
Dipaths that are dihomotopic (through a 1-parameter defor- mation consisting of dipaths) correspond to equivalentexecutions.
Deadlocks, unsafeand unreachable regions may occur.
Higher dimensional automata
seen as (geometric realizations of) cubical sets
Vaughan Pratt, Rob van Glabbeek, Eric Goubault...
a b
a b 2 processes, 1 processor
cubical complex bicomplex
2 processes, 3 processors 3 processes, 3 processors
Squares/cubes/hypercubes are filled in iff actions on boundary areindependent.
Higher dimensional automata are (pre)-cubical sets:
◮ like simplicial sets, but modelled on (hyper)cubes instead of simplices; glueing byface maps
◮ additionally:preferred directions– not all paths allowable.
Martin Raussen Trace spaces: Organization, Calculations, Applications
Discrete versus continuous models
How to handle the state-space explosion problem?
Thestate space explosion problemfor discrete models for concurrency (transition graph models): The number of states (and the number of possible schedules) growsexponentiallyin the number of processors and/or the length of programs.
Need clever ways to find out which of the schedules yield equivalentresults for general reasons – e.g., to check for correctness.
Alternative:Infinite continuousmodels allowing for well-known equivalence relations on paths (homotopy= 1-parameter deformations) – but with an important twist!
Analogy: Continuous physics as an approximation to (discrete) quantum physics.
A general framework for directed topology
The twist: d-spaces, M. Grandis (03)
X a topological space.~P(X)⊆XI ={p :I = [0,1]→X cont.} a space ofd-paths (CO-topology; ”directed” paths↔
executions) satisfying
◮ {constant paths} ⊆~P(X)
◮ ϕ∈~P(X)(x,y),ψ∈~P(X)(y,z)⇒ ϕ∗ψ∈~P(X)(x,z)
◮ ϕ∈~P(X),α∈II anondecreasingreparametrization
⇒ ϕ◦α∈~P(X)
The pair(X,~P(X))is called ad-space.
Observe:~P(X)is in generalnotclosed underreversal:
α(t) =1−t, ϕ∈~P(X)6⇒ ϕ◦α∈~P(X)!
Examples:
◮ An HDA withdirectedexecution paths.
◮ A space-time(relativity) withtime-likeorcausalcurves.
Martin Raussen Trace spaces: Organization, Calculations, Applications
D-maps, Dihomotopy, d-homotopy
Ad-map f :X →Y is a continuous map satisfying
◮ f(~P(X))⊆~P(Y).
special case:~P(I) ={σ∈ II|σnondecreasing reparametrization},~I= (I,~P(I)).
Then~P(X) =space of d-maps from~I to X .
◮ DihomotopyH:X ×I →Y , every Ht a d-map
◮ elementary d-homotopy= d-map H:X ×~I →Y – H0=f−→H g =H1
◮ d-homotopy: symmetric and transitive closure (”zig-zag”) L. Fajstrup, 05: In cubical models (for concurrency, e.g., HDAs), the two notions agree for d-paths (X =~I). In general, they do not.
Dihomotopy is finer than homotopy with fixed endpoints
Example: Two wedges in the forbidden region
All dipaths from minimum to maximum are homotopic.
A dipath through the “hole” isnot dihomotopic to a dipath on the boundary.
Martin Raussen Trace spaces: Organization, Calculations, Applications
The twist has a price
Neither homogeneity nor cancellation nor group structure
Ordinary topology: Path space = loop space (within each path component).
A loop space is an H-space with concatenation, inversion, cancellation.
“Birth and death” of d-homotopy classes
Directed topology:
Loops do not tell much;
concatenation ok, can- cellationnot!
Replace group struc- ture by category structures!
D-paths, traces and trace categories
Getting rid of reparametrizations
X a (saturated)d-space.
ϕ,ψ∈~P(X)(x,y)are calledreparametrization equivalentif there areα,β∈~P(I)such that ϕ◦α=ψ◦β(“same oriented trace”).
(Fahrenberg-R., 07): Reparametrization equivalence is an equivalence relation (transitivity).
~T(X)(x,y) =~P(X)(x,y)/≃makes~T(X)into the (topologically enriched)trace category– compositionassociative.
A d-map f :X →Y induces afunctor~T(f):~T(X)→~T(Y).
Martin Raussen Trace spaces: Organization, Calculations, Applications
The two main objectives
◮ Investigation/calculation of thehomotopy typeof trace spaces~T(X)(x,y)for relevant d-spaces X
◮ Investigation oftopology changeunder
~T(X)(x′,y)σ
∗ x′x
← ~T(X)(x,y)−→σyy′ ∗~T(X)(x,y′) Categorical organization
Categorical organization
First tool: The fundamental category
~π1(X)of a d-space X [Grandis:03, FGHR:04]:
◮ Objects: points in X
◮ Morphisms: d- or dihomotopy classes of d-paths in X
◮ Composition:from concatenation of d-paths
A B
C D
Property: van Kampen theorem (M. Grandis) Drawbacks: Infinitely many objects. Calculations?
Question: How much does~π1(X)(x,y)depend on(x,y)? Remedy: Localization, component category. [FGHR:04, GH:06]
Problem: This “compression” works only forloopfreecategories (d-spaces)
Martin Raussen Trace spaces: Organization, Calculations, Applications
Preorder categories
Getting organised with indexing categories
A d-space structure on X induces the preorder:
x y ⇔~T(X)(x,y)6=∅
and an indexingpreorder category~D(X)with
◮ Objects: (end point)pairs(x,y),x y
◮ Morphisms:
~D(X)((x,y),(x′,y′)):=~T(X)(x′,x)×~T(X)(y,y′):
x′ ((66x //y ))55y′
◮ Composition: by pairwise contra-, resp. covariant concatenation.
A d-map f :X →Y induces a functor~D(f):~D(X)→~D(Y).
The trace space functor
Preorder categories organise the trace spaces
The preorder category organises X via the trace space functor~TX :~D(X)→Top
◮ ~TX(x,y):=~T(X)(x,y)
◮ ~TX(σx,σy): ~T(X)(x,y) //~T(X)(x′,y′)
[σ] /[σx ∗σ∗σy] Homotopical variant~D
π(X)with morphisms
~Dπ(X)((x,y),(x′,y′)):=~π1(X)(x′,x)×~π1(X)(y,y′) and trace space functor~TX
π :~D
π(X)→Ho−Top(with homotopyclassesas morphisms).
Martin Raussen Trace spaces: Organization, Calculations, Applications
D-homology ~ H
∗
For every d-space X , there are homologyfunctors
~H∗+1(X) =H∗◦~TX π :~D
π(X)→Ab, (x,y)7→H∗(~T(X)(x,y)) capturing homology of all relevant d-path spaces in X
and the effects of the concatenation structure maps.
A d-map f :X →Y induces anatural transformation~H
∗+1(f) from~H
∗+1(X)to~H
∗+1(Y).
Similarly for other algebraic topological functors; a bit more complicated for homotopy groups: base points!
Sensitivity with respect to variations of end points
Questions from a persistence point of view
◮ How much does (the homotopy type of)~TX(x,y)depend on (small) changes of x,y ?
◮ Which concatenation maps
~TX(σx,σy):~TX(x,y)→~TX(x′,y′), [σ]7→[σx ∗σ∗σy] are homotopy equivalences, induce isos on homotopy, homology groups etc.?
◮ Thepersistencepoint of view: Homology classes etc. are born (at certain branchings/mergings) and may die (analogous to the framework of G. Carlsson etal.)
◮ Are there “components” with (homotopically/homologically) stable dipath spaces (between them)? Are there borders (“walls”) at which changes occur?
Martin Raussen Trace spaces: Organization, Calculations, Applications
Topology of trace spaces for a cubical complex X
l1“arc length” parametrization: on each cube, arc length is the l1-distance of end-points. Additive continuation
subspace of arc-length parametrized d-paths~P
n(X)⊂~P(X). D-homotopic paths in~P
n(X)(x,y)have thesame arc length!
The spaces~P
n(X)and~T(X)arehomeomorphic,~P(X)is homotopy equivalentto both.
Theorem
X a pre-cubical set; x,y ∈X . Then~T(X)(x,y)
◮ ismetrizable,locally contractibleandlocally compact1.
◮ has the homotopy type of a CW-complex.2
First examples
Inthe unit cube,∂Inits boundary.
◮ ~T(In;x,y)is contractible for all x y ∈In;
◮ ~T(∂In;0,1)is homotopy equivalent to Sn−2.
1MR, Trace spaces in pre-cubical complexes, Draft
Aim: Decomposition of trace spaces
Method: Investigation of concatenation maps
Let L ⊂X denote a (properly chosen) subspace. Investigate the concatenation map
cL:~T(x0,L)×L~T(L,x1)→~T(x0,x1), (p0,p1)7→p0∗p1 onto? fibres? Topology of the pieces? Generalization:
L1,· · · ,Lk a sequence of (properly chosen) subspaces.
Investigate the concatenation map
~T(X)(x0,L1)×L1· · · ×Lj~T(X)(Lj,Lj+1)×Lj+1· · · ×Lk~T(X)(Ln,x1).
onto? fibres? Topology of the pieces?
Martin Raussen Trace spaces: Organization, Calculations, Applications
Tool : The Vietoris-Begle mapping theorem
Stephen Smale’s version for homotopy groups
What does a surjective map p :X →Y with highly connected fibres p−1(y),y ∈Y,tell about invariants of X,Y ?
TheVietoris-Begle mapping theoremcompares the Alexander-Spanier cohomology groups of X,Y .
Stephen Smale, A Vietoris Mapping Theorem for Homotopy, Proc. Amer. Math. Soc. 8 (1957), no. 3, 604 – 610:
Theorem
Let f :X →Y denote a proper surjective map between connected locally compact separable metric spaces. Let moreover X be locally n-connected, and for each y ∈Y , let f−1(y)be locally(n−1)-connected and(n−1)-connected.
Then
1. Y is locally n-connected, and
2. f#:πr(X)→πr(Y)isan isomorphism for all 0≤r ≤n−1 and onto for r =n.
An important special case
All fibres contractible and locally contractible
Corollary
Let f :X →Y denote a proper surjective map between locally compact separable metric spaces. Let moreover X be locally contractible, and for each y ∈Y , let f−1(y)be contractible and locally contractible. Then
1. Y is locally contractible, and 2. f is aweak homotopy equivalence.
Martin Raussen Trace spaces: Organization, Calculations, Applications
Applications to trace spaces I
A simple case as illustration
Definition
A subset A⊆X of a d-space X is called
d-convex if[x0,x1] ={p(t)|p∈~P(X)(x0,x1),t ∈I} ⊆A;
in particular, p−1(A)is either an interval or empty for all p∈~P(X);
unavoidable from B ⊂X to C ⊂X if~P(X\A)(B,C) =∅.
Theorem
Let X be a nice d-space, e.g., the geometric realization of a pre-cubical complex. Let x0,x1∈X,L⊂X d-convex and unavoidable from x0to x1.
If~T(X)(x0,L)and~T(X)(L,x1)are locally contractible, then the concatenation map
cL:~T(X)(x0,L)×L~T(X)(L,x1)→~T(X)(x0,x1), (p0,p1)7→p0∗p1 is a weak(?) homotopy equivalence.
An important special case
Corollary
If~T(X)(x0,l)and~T(X)(l,x1)are contractible and locally contractible for every l ∈L, then
~T(X)(x0,x1)is weakly(?)homotopy equivalent to L.
Proof.
The fibre over l ∈L of the “mid point” map m:~T(X)(x0,L)×L~T(X)(L,x1)→L is m−1(l) =~T(X)(x0,l)×~T(X)(l,x1). Example
X =∂In= {x∈In| ∃i:xi =0∨xi =1} ≃Sn−1 L= ∂±In= {x∈In| ∃i,j :xi =0,xj =1} ≃Sn−2
Then~T(∂In)(0,1)is weakly homotopy equivalent3to Sn−2.
3in fact homotopy equivalent
Martin Raussen Trace spaces: Organization, Calculations, Applications
Key points in the proof of Theorem
◮ Check the topological conditions (separable metric space, locally compact, locally contractible, properness) for trace spaces in nice d-spaces4.
◮ Surjectivity corresponds to unavoidability.
◮ D-convexity ensures that every fibre is an interval, hence contractible.
◮ Under which conditions to L can Milnor’s proof be adapted to get an actual homotopy equivalence?
4MR, Trace spaces in pre-cubical complexes, manuscript
Applications to trace spaces II: A generalisation
The setting: Definitions
Given a collectionLof m+1 (finitely many) disjoint subsets Li ⊂X with L0={x0},Lm ={x1}.
A d-path in X is calledprime with respect toLif there are Li,Lj ∈ Land a,b∈I such that
p−1(Li) = [0,a],p−1(Lj) = [b,1]and p−1(Lk) =∅for k 6=i,j.
Let~PL(X)⊂~P(X)denote the subspace of all d-paths that are prime with respect toL.
The collectionLis calledunavoidable from x0to x1if
◮ every d-path p ∈~P(X)(x0,x1)can be decomposed into pieces that are prime with respect toL;
◮ every d-path q ∈~PL(X)(Li,Lj)that is d-homotopic (rel Li,Lj) to a prime d-path is prime itself.
A sequence(0,i1,. . .,in,m)isL-admissible if
~PL(X)(Lij,Lij+1)6=∅,0≤j ≤n.
Martin Raussen Trace spaces: Organization, Calculations, Applications
Decomposition of d-path spaces
F1 F3
F2 F4
T1 y T1
x T3
x
2 T2
x T4 x
T3
y T4
y
T y
Theorem
LetLdenote a collection of finitely many disjoint subsets in X that is unavoidable from x0to x1. Then~T(X)(x0,x1)isweakly homotopy equivalentto the disjoint union over all L-admissible sequences (0,i1,. . .,in,1)of spaces
~TL(X)(x0,Li1)×L
i1· · · ×L
ij
~TL(X)(Lij,Li
j+1)×L
ij+1· · · ×Lin~TL(X)(Lin,x1).
Proof.
Apply Smale’s Vietoris theorem to the concatenation map into
~T(X)(x0,x1).
◮ Unavoidability ensures surjectivity.
◮ Since the pieces are prime, every fibre is a product of intervals, hence contractible.
An important special case
Reachability. For a given collectionLof finitely many disjoint subsets in X that is unavoidable from x0 to x1, let
RL(Li,Lj) ={(xi,xj)∈Li×Lj |~PL(xi,xj)6=∅} ⊂X ×X. Corollary
If, moreover, for all i,j,(xi,xj)∈RL(Li,Lj)the path spaces
~TL(X)(xi,xj)are contractible and locally contractible, then
~T(X)(x0,x1)isweakly homotopy equivalentto the disjoint union over allL-admissible sequences(0,i1,. . .,in,1)of spaces
RL(x0,Li1)×L
i1· · · ×L
ij RL(Lij,Lij+1)×L
ij+1· · · ×LinRL(Lin,x1)⊂Xn+1.
The latter space consists of sequences ofmutually reachable points in the given layers.
Martin Raussen Trace spaces: Organization, Calculations, Applications
Examples
1.
A wedge of two directed circles X =~S1∨x0
~S1:
~T(X)(x0,x0)≃ {1,2}∗.
(Choose Li = {xi},i = 1,2 with xi 6=
x0on the two branches).
2.
Y =cube with two wedges deleted:
~T(Y)(0,1)≃ ∗ ⊔(S1∨S1).
(Li two vertical cuts through the wedges; product is homotopy equiva- lent to torus; reachability
two components, one of which is con- tractible, the other a thickening of S1∨S1⊂S1×S1.)
Application to trace spaces III
Piecewise linear traces
Let X denote the geometric realization of a finite pre-cubical complex (-set) M, i.e., X =∐(Mn×~In)/≃.
X consists of “cells” eα homeomorphic to Inα. A cell is called maximalif it is not in the image of a boundary map∂±. The d-path structure~P(X)is inherited from the~P(~In)by
“pasting”.
Definition
p ∈~P(X)is calledPLif: p(t)∈ eαfor t ∈ J ⊆I⇒p|J linear5.
~PPL(X),~T
PL(X): subspaces of linear d-paths and traces.
Theorem
For all x0,x1∈X , the inclusion~T
PL(X)(x0,x1)֒→~T(X)(x0,x1) is a weak homotopy equivalence.
5and close-up on boundaries
Martin Raussen Trace spaces: Organization, Calculations, Applications
Outline of proof
A sequence of cells(eα0,. . .,eαn)in X is called achainfrom x0 to x1if every of the cells is maximal, if x0∈eα0,x1 ∈eαn
and if∂+eαi ∩∂−eαi+1 6=∅for 0≤i <n.
Let C(X)(x0,x1)denote the set of chains in X from x0to x1. Apply Smale’s Vietoris theorem to the concatenation map:
S
c∈C(X)(x0,x1)~T(X)(x0,∂+eα0)×∂+eα0∩∂−eα1 · · · ×∂+eαi−1∩∂−eαi
~T(X)(∂−eαi,∂+eαi)×∂+eαi∩∂−eαi+1 · · · ×∂+eαn−1∩∂−eαn
~T(X)(∂−eαn,x1)→~T(X)(x0,x1).
This map is aweak homotopy equivalence: It is surjective; the fibres are products of intervals, hence contractible.
Pastehomotopy equivalenceson factors
~TPL(X)(∂−eαi,∂+eαi)֒→~T(X)(∂−eαi,∂+eαi).
A prodsimplicial structure on ~ T
PL
( X )
Cube paths and the PL-paths in each of them
Definition
Amaximal cube pathin a pre-cubical set is a sequence (eα1,. . .,eαk)of maximal cells such that∂+eαi∩∂−eαi+1 6=∅.
The PL-traces within a given maximal cube path(eα1,. . .,eαk) correspond to sequences in{(y1,. . .,yk−1)∈
∏ki=−11(∂+eαi∩∂−eαi+1)⊂ Xk |~P(eαi)(yi−1,yi)6=∅,1<i<k}. This set carries a natural structure as a
product of simplices∏ ∆jk.
Subsimplices and their products: Some coordinates of d-paths are minimal, maximal or fixed within one or several cells.
The space~T
PL(X)carries thus the structure of a prodsimplicial complex possibilities for inductive calculations.
Martin Raussen Trace spaces: Organization, Calculations, Applications
Simple examples
1.
1 2 3
4 5
Two maximal cube paths from 0 to 1, each of them contributing∆2×∆2. Empty intersection.
~TPL(X)(0,1)≃(∆2×∆2)⊔(∆2×∆2).
2. X =∂~In. Maximal cube paths from 0 to 1 have length 2.
Every PL-d-path is determined by an element of
∂±~In≃Sn−2.
Future work
on the algebraic topology of trace spaces
◮ Is there an automatic way to place consecutive “diagonal cut” layers in complexes corresponding to PV-programs that allow to compare path spaces tosubspaces of the products of these layers?
◮ PL-d-paths come in“rounds”corresponding to the sums of dimensions of the cells they enter. This gives hope for inductive calculations(as in the work of Herlihy, Rajsbaum and others) in distributed computing.
◮ Explore the combinatorial algebraic topology of the trace spaces
◮ withfixed end pointsand
◮ what happens undervariations of end points.
◮ Make this analysis useful for the determination of components(extend the work of Fajstrup, Goubault, Haucourt, MR)
Martin Raussen Trace spaces: Organization, Calculations, Applications
Examples of component categories
Example 1: No nontrivial d-loops
00000000 00000000 0000 11111111 11111111 1111 00000 11111
00000 11111
A B
C D
Figure: Deleted square with component category
AA
((Q
QQ QQ QQ QQ QQ QQ QQ
2
22 22 22 22 22 22
22 BB
vvmmmmmmmmmmmmmmm
AB
#
AC //ADoo BD
# CD
OO
CC
66m
mm mm mm mm mm mm mm
FF
DD
XX11
1111 1111
11111
hhQQQQ
QQQQQQQQQQQ
Components A,B,C,D – or rather
AA,AB,AC,AD,BB,BD,CC,CD,DD⊆X×X .
#: diagram commutes.
Examples of component categories
Example 2: Oriented circle
X = ~S1
6
oriented circle
~T(~S1)(x,y)≃N0.
C:∆
a ))∆¯
ll b
∆the diagonal,∆¯ its complement.
C is the free category generated by a,b.
◮ Remark that the components areno longer products!
◮ In order to get a discrete component category, it is essential to use an indexing category taking care ofpairs (source, target).
Martin Raussen Trace spaces: Organization, Calculations, Applications
Tool: Homotopy flows
in particular: Automorphic homotopy flows
A d-map H :X×~I →X is called a (f/p)homotopy flowif future H0=idX−→H f =H1
past H0=g−→H idX =H1
Ht isnota homeomorphism, in general; the flow isirreversible.
H and f are called
automorphic if~T(Ht):~T(X)(x,y)→~T(X)(Htx,Hty)is a homotopy equivalence for all x y,t ∈I.
Automorphisms are closed under composition – concatenation of homotopy flows!
Aut+(X),Aut−(X)monoidsof automorphisms.
Variations:~T(Ht)induces isomorphisms on homology groups, homotopy groups....
Compression: Generalized congruences and quotient categories
Bednarczyk, Borzyszkowski, Pawlowski, TAC 1999
How to identify morphisms in a categorybetween different objectsin an organised manner?
Start with an equivalence relation ≃on the objects.
Ageneralized congruenceis an equivalence relation on non-emptysequences ϕ= (f1. . .fn)of morphisms with cod(fi)≃dom(fi+1)(≃-paths) satisfying
1. ϕ≃ψ⇒dom(ϕ)≃dom(ψ),codom(ϕ)≃codom(ψ) 2. a≃b⇒ida≃idb
3. ϕ1≃ψ1, ϕ2≃ψ2, cod(ϕ1)≃dom(ϕ2)⇒ ϕ2ϕ1≃ψ2ψ1
4. cod(f) =dom(g)⇒f ◦g≃ (fg)
Quotient categoryC/≃: Equivalence classes of objects and of
≃-paths; composition:[ϕ]◦[ψ] = [ϕψ].
Martin Raussen Trace spaces: Organization, Calculations, Applications
Automorphic homotopy flows give rise to generalized congruences
Let X be a d -space and Aut±(X)themonoidof all (future/past) automorphisms.
“Flow lines” are used to identify objects (pairsof points) and morphisms (classes of d-paths) in an organized manner.
Aut±(X)gives rise to ageneralized congruenceon the (homotopy) preorder category~D
π(X)as the symmetric and transitive congruence closure of:
Congruences and component categories
◮ f+:(x,y)↔≃ (x′,y′):f−, f±∈Aut±(X)
◮
(x,y)(σ−→1,σ2)(u,v)≃(x′,y′)(−→τ1,τ2)(u′,v′),
f+:(x,y,u,v)↔(x′,y′,u′,v′):f−, f± ∈Aut±(X), and
~T(X)(x′,y′)(τ1,τ2)//
~T(f−)
~T(X)(u′,v′)
~T(f−)
~
T(X)(x,y) (σ1,σ2)//
~T(f+)
JJ
~T(X)(u,v)
~T(f+)
JJ commutes (up to ...).
◮ (x,y)(c−→x,Hy)(x,fy)≃(fx,fy)(H−→x,cfy)(x,fy), H :idX →f . Likewise for H :g→idX.
The component category~D
π(X)/≃identifies pairs of points on the same “homotopy flow line” and (chains of) morphisms.
Martin Raussen Trace spaces: Organization, Calculations, Applications
Examples of component categories 1
Example 3: The component category of a wedge of two oriented circles
X =~S1∨~S1
~T(X)(x,y) ≃ N0∗N0
Examples of component categories
Example 4: The component category of an oriented cylinder with a deleted rectangle
L M U
Martin Raussen Trace spaces: Organization, Calculations, Applications
Dihomotopy equivalence – a naive definition
Definition
A d-map f :X →Y is a dihomotopy equivalence if there exists a d-map g :Y →X such thatg◦f ≃idX and f ◦g ≃idY. But this doesnotimply an obvious property wanted for:
A dihomotopy equivalence f :X →Y should induce (ordinary) homotopy equivalences
~T(f):~T(X)(x,y)→~T(Y)(fx,fy)!
00000000 00000000 0000 11111111 11111111 1111 00000 11111
00000 11111
A B
C D
A map d-homotopic to the identity does not preserve homotopy types of trace spaces? Need to be more restrictive!
Dihomotopy equivalences
using automorphic homotopy flows
Definition
A d-map f :X →Y is called afuture dihomotopy equivalenceif there are maps f+:X →Y,g+ :Y →X with f →f+and automorphichomotopy flowsidX →g+◦f+,idY →f+◦g+. Property of dihomotopy class!
likewise: past dihomotopy equivalencef−→f,g−→g dihomotopy equivalence= both future and past dhe (g−,g+are then d-homotopic).
Theorem
A (future/past) d-homotopy equivalence f :X →Y induces homotopy equivalences
~T(f)(x,y):~T(X)(x,y)→~T(Y)(fx,fy)for all x y.
Moreover: (All sorts of) Dihomotopy equivalences are closed under composition.
Martin Raussen Trace spaces: Organization, Calculations, Applications
Concluding remarks
◮ Component categoriescontain the essential information given by (algebraic topological invariants of) path spaces
◮ Compression via component categories is anantidote to the state space explosion problem
◮ Some of the ideas (for the fundamental category) are implementedand have been tested for huge industrial software from EDF ( ´Eric Goubault & Co., CEA)
◮ Dihomotopy equivalence: Definition uses automorphic homotopy flows to ensure homotopy equivalences
~T(f)(x,y):~T(X)(x,y)→~T(Y)(fx,fy)for all x y.
◮ Much more theoretical and practical work remains to be done!
