Simplicial models for trace spaces

(1)

Simplicial models for trace spaces

Martin Raussen

Department of Mathematical Sciences Aalborg University

Denmark

ATMCS IV 21.6.2010

Martin Raussen Simplicial models for trace spaces

(2)

State space and model of trace space

Problem: How are they related?

Example:

State space = a cube~_I3\F

minus 4 box obstructions

Trace space contained in a torus(∂∆²)²–

homotopy equivalent to a wedge of two circles and a point: (S¹∨S¹)⊔ ∗

(3)

Motivation: Concurrency

A simple model for mutual exclusion

Mutual exclusionoccurs, when n processes P_i compete for m resources R_j.

P P

1 2

R1

P3

R2

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 P_i : . . .PR_j. . .VR_j. . . (E.W. Dijkstra) P: pakken;V: vrijlaten

(4)

A geometric model: 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 P₁:P_aP_bV_bV_a P₂:P_bPaVaV_b

Executions are directed paths – since time flow is irreversible – avoiding a forbidden region(shaded).

Dipaths that are dihomotopic (through a 1-parameter deforma- tion consisting of dipaths) correspond to equivalent executions.

Deadlocks, unsafe and unreachable regions may occur.

(5)

Simple Higher Dimensional Automata

Semaphore models

Alinear PV-program can be modelled as the complement of a forbidden region F consisting of a number ofholesin an n-cube Iⁿ:

Hole =isothetic hyperrectangleRⁱ,1≤i ≤l, in an n-cube.

State space

X =~_In\F, F =^S^l_i₌₁Rⁱ, Rⁱ =]aⁱ₁,b₁ⁱ[× · · · ×]aⁱ_n,b_nⁱ[^. with minimal vertex aⁱ and maximal vertex bⁱ.

X inherits a partial order from~_In. More general PV-programs:

Replace~_In by a productΓ₁× · · · ×^Γnofdigraphs.

Holes have then the form pⁱ₁((0,1))× · · · ×pⁱ_n((0,1))with p_jⁱ :~_I→^Γja directed injective (d-)path.

Pre-cubical complexes: like pre-simplicial complexes, with (partially ordered) hypercubes instead of simplices as building blocks.

(6)

Main interest: Spaces of d-paths/traces – up to dihomotopy

X ad-space, a,b∈ X.

p:~_I →X ad-pathin X (continuous and

“order-preserving”)

~_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)moduloincreasing reparametrizations.

In most cases: ~_P(X)(a,b)≃~_T(X)(a,b).

Adihomotopyon~_P(X)(a,b)is a map H :~_I×I →X such that H_t ∈~_P(X)(a,b)^, t∈ I; a path in~_P(X)(a,b).

Aim: Description of thehomotopy typeof~_P(X)(a,b);

in particular of itspath components, ie the dihomotopy classes of d-paths.

(7)

Covers of X and of ~ _P ( X )( 0 , 1 )

by contractible or empty subspaces

X =~_In\F,F =^S^l_i₌₁Rⁱ;Rⁱ = [aⁱ,bⁱ]^;0,1 the two corners in Iⁿ. Definition

X_j₁_,...,j_l ={x ∈ X| ∀i :x_j_i ≤aⁱ_j

i ∨ ∃k :x_k ≥b_kⁱ}

={x ∈X| ∀i :x ≤bⁱ ⇒x_j_i ≤aⁱ_j

i}^, 1≤j_i ≤n.

Examples:

~_P(X)(0,1) = ^[

1≤j1,...,jl≤n

~_P(X_j₁_,...,j_l)(0,1)^.

(8)

More intricate subspaces as intersections

either empty or contractible

Definition

∅6=J₁,. . .,J_l ⊆[1:n]:

X_J₁_,...,J_l = ^\

ji∈Ji

X_j₁_,...,j_l

= {x ∈ X| ∀i,j_i ∈J_i :x ≤bⁱ ⇒x_j_i ≤aⁱ_j

i}

Theorem

~P(X_J₁_,...,J_l)(0,1)is eitheremptyorcontractible.

Proof.

relies on: Subspaces X_J₁_,...,J_l areclosed under∨= l.u.b.

Question: For which J₁,. . .,J_l ⊆[1:n]is

~_P(X_J₁_,...,J_l)(0,1)6=^∅?

(9)

Combinatorics: Bookkeeping with binary matrices

M_l,n poset(≤) ofbinaryl×n-matrices M_l,n^R no rowvector is thezerovector M_l,n^C every columnvector is aunitvector Restriction toIndex sets ↔ Matrix sets

(P([1:n]))^l ↔ M_l,n

J = (J₁,. . .,J_l) 7→ M^J = (m_ij)^, m_ij =1⇔j ∈J_i J^M ← M J_i^M ={j|m_ij =1} l-tuples of subsets6=^∅ ↔ M_l,n^R

{(K₁,. . .,K_l)|[1:n] =^GK_i} ↔ M_l,n^C

X_M :=X_J_M, ~_P(X_M)(0,1) =~_P(X_J_M)(0,1)6=^∅?

(10)

A combinatorial model and its geometric realization

First examples

Poset category – Combinatorics Prodsimplicial complex – Topology

C(X)(0,1)⊆M_l,n^R ⊆M_l,n T(X)(0,1)⊆ (^∆ⁿ⁻¹)^l J ↔M ∈ C(X)(0,1) ∆_J^|^J¹^|−¹

1 × · · · ×∆_J^|^J^l^|−¹

l ⊆

T(X)(0,1)

⇔~_P(X_M)(0,1)6=^∅.

Examples:

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 1

T(X₁)(0,1) = (∂∆¹)²

=4∗

T(X₂)(0,1) =3∗

⊂ C(X)(0,1)

(11)

Further examples

(1) X =~_In\~_Jn

C(X)(0,1) = M_1,n^R \ {[1,. . .1]}.

T(X)(0,1) =∂∆ⁿ⁻¹≃Sⁿ⁻².

(2)

Cmax(X)(0,1) = {

0 1 1 0 1 1

,

1 0 1 1 0 1

,

1 1 0 1 1 0

}. T(X)(0,1) =3 diagonal

squares⊂(∂∆²)²=T²

≃S¹.

(12)

Homotopy equivalence between trace space

~ _T ( X )( 0 , 1 ) and the prodsimplicial complex T ( X )( 0 , 1 )

Theorem

~P(X)(0,1)≃T(X)(0,1)≃^∆C(X)(0,1).

Proof.

FunctorsD^,E^,T ^:C(X)(0,1)⁽^op⁾→Top:

D(J₁,. . .,J_l) =~_P(X_J₁_,...,J_l)(0,1)^, E(J₁,. . .,J_l) =^∆^|_J^J¹^|−¹

1 × · · · ×^∆^|_J^J^l^|−¹

l ,

T(J₁,. . .,J_l) =∗

colimD =~_P(X)(0,1)^, colimE =T(X)(0,1)^, hocolimT =^∆C(X)(0,1).

The trivial natural transformationsD ⇒ T^,E ⇒ T yield:

hocolimD ∼=^hocolimT^∗ ∼=^hocolimT ∼=^hocolimE. Projection lemma:

hocolimD ≃colimD, hocolimE ≃colimE.

(13)

From C ( X )( 0 , 1 ) to properties of path space

Questions answered by homology calculations using T(X)(0,1)

Is~_P(X)(0,1)path-connected, i.e., are all (execution) d-paths dihomotopic (lead to the same result)?

Determination ofpath-components?

Are componentssimply connected?

Other topological properties?

The prodsimplicial structure onC(X)(0,1)↔T(X)(0,1)leads to an associatedchain complexof vector spaces.

There are fast algorithms to calculate thehomologygroups of these chain complexes even for very big complexes.

Number of path-components: rkH₀(T(X)(0,1))^.

For path-components, there might be faster “discrete” methods.

Even if “exponential explosion” prevents precise calculations, inductive determination (round by round) of general properties ((simple) connectivity) may be possible.

Implementationin ALCOOL: progress at CEA/LIX-lab.

(14)

Deadlocks and unsafe regions determine C ( X )( 0 , 1 )

A dual view: extendedhyperrectanglesR_jⁱ

:= [0,bⁱ₁[× · · · ×[0,b_j−1ⁱ [×]aⁱ_j,bⁱ_j[×[0,b_j+1ⁱ [× · · · ×[0,b_nⁱ[⊃Rⁱ.

X_M =X\ ^[

mij=1

R_jⁱ.

Theorem

The following are equivalent:

1 ~_P(X_M)(0,1) =^∅⇔M6∈C(X)(0,1).

2 There is a map i :[1:n]→[1:l]such that m_i(j),j=1 and such that^T_1≤j≤nR_j^i(j)6=^∅– giving rise to adeadlock unavoidable from 0.

3 Mere combinatorics: Checking a bunch ofinequalities:

There is a map i :[1:n]→[1:l]such that a^i(j)_j <_b^i(k)

j for all 1≤j,k ≤n.

OBS:χ(^graph(ⁱ)) =^M(ⁱ)∈^M_l,n^C ^!

(15)

Which of the l

ⁿ

matrices in M

_l^C_,n

belong to D ( X )( 0 , 1 ) ?

A matrix M ∈M_l,n^C is described by a (choice) map i :[1:n]→[1 :l]^,m_i₍_j₎_,j =1. Deadlocks inequalities:

M ∈D(X)(0,1)⊆M_l,n^C ⇔aⁱ_j⁽^j⁾<_bⁱ⁽^k⁾

j for all 1≤j,k ≤n.

Algorithmic organisation: Choice maps with thesame image give rise to the sameupperbounds b^∗_j.

(16)

Partial orders and order ideals on matrix spaces

and an order preserving mapΨ

ConsiderΨ:M_l,n→Z/2, Ψ(M) =1⇔~_P(X_M)(0,1) =^∅.

Ψ isorder preserving, in particular:

Ψ⁻¹(0)^,^Ψ⁻¹(1)are closed in opposite senses:

M ≤N :Ψ(N) =0⇒^Ψ(M) =0;Ψ(M) =1⇒^Ψ(N) =1 (thus T(X)(0,1)prodsimplicial).

Ψ(M) =1⇔∃N ∈M_l,n^C such that N≤M,Ψ(N) =1 D(X)(0,1) ={N ∈ M_l,n^C|^Ψ(N) =1}–dead

C(X)(0,1) ={M ∈M_l,n^R|^Ψ(M) =0}–alive Cmax(X)(0,1) maximal such matrices characterized by: m_ij =1 apart from:

∀N ∈D(X)(0,1)∃^!(i,j)^:0=m_ij <_n_ij =1

Matrices in Cmax(X)(0,1)correspond tomaximal simplex productsin T(X)(0,1).

Example: X =~_In⊂~_Jn

,D(X)(0,1) =

{[1,. . .,1]}^,Cmax(X)(0,1) =M_l,n^R \ {[1,. . .,1]}.

(17)

From D ( X ) to C

_max

( X )

Minimal transversals in hypergraphs (simplicial complexes)

Algorithmics: ConstructCmax(X)(0,1)incrementally (checking for one matrix N ∈ D(X)(0,1)at a time), starting with matrix 1:

1 N_i₊₁6≤M ∈ Cⁱ(X)⇒M ∈ Cⁱ⁺¹(X)^;

2 N_i₊₁≤M⇒M is replaced by n matrices M^j with one additional 0. Example: X =~_In\~_Jn.

A matrix in D(X)(0,1)describes ahyperedgeon the vertex set [1:l]×[1:n]; D(X)(0,1)describes ahypergraph.

Atransversalin a hypergraph is a vertex set that has non-empty intersection with each hyperedge

↔a matrix L such that∀N ∈D(X)(0,1)∃(i,j)^:l_ij =n_ij =1.

M =1−L: ∀N∈D(X)(0,1)∃(i,j)^:0=m_ij <_n_ij =1.

Conclusion: Search for matrices in A_max(0,1)corresponds to search forminmal transversalsin D(X)(0,1).

In our case: All hyperedges have same cardinality n, include one element per column.

(18)

Extensions

1. Obstructions intersecting the boundary of Iⁿ - Components

More general semaphores (intersection with the boundary of Iⁿallowed)

Different end points:~_P(X)(c,d)and iterative calculations Endcomplexesrather than end points (allowing processes not to respond..., Herlihy & Cie)

Same technique, modification of definition and calculation of C(X)(−^,−), D(X)(−^,−)etc.

New light on definition and determination ofcomponentsof model space X .

(19)

Extensions

2a. Semaphores corresponding tonon-linearprograms:

Products of digraphs instead of~_In: Γ=∏ⁿ_j₌₁Γ_j, state space X =^Γ\F ,

F a product of generalized hyperrectangles Rⁱ.

~_P(^Γ)(x,y) =∏~_P(^Γj)(x_j,y_j)– homotopy discrete!

Represent apath component C ∈~_P(^Γ)(x,y)by (regular) d-paths p_j ∈~_P(^Γj)(x_j,y_j)– an interleaving.

The map c :~_In→^Γ,c(t₁,. . .,t_n) = (c₁(t₁)^,^{. . .}^,c_n(t_n))induces ahomeomorphism◦c :~_P(~_In)(0,1)→C⊂~_P(^Γ)(x,y).

(20)

Extensions

2b. Semaphores: Topology of components of interleavings

Pull back F via c:

X¯ =~_In\F^¯,F¯ =^SR^¯ⁱ,R¯ⁱ =c⁻¹(Rⁱ)– honest hyperrectangles!

0

1

i_X :~_P(X)֒→~_P(^Γ).

Given a component C ⊂~_P(^Γ)(x,y).

The d-map c : ¯X →X induces a homeomorphism c◦^:~_P(X^¯)(0,1)→i_X⁻¹(C)⊂~_P(X)(x,y).

C “lifts to X ”⇔~_P(X^¯)(0,1)6=^{∅; if so:}

Analyse i_X⁻¹(C)via~_P(X^¯)(0,1).

Exploit relations between various components.

(21)

Extensions

3. D-paths in pre-cubical complexes

Higher Dimensional Automaton:Pre-cubical complexwith preferred diretions. Geometric realization X with d-space structure.

P(X)(x,y)isELCX(equi locally convex). D-paths within a specified “cube path” form acontractiblesubspace.

P(X)(x,y)has the homotopy type of a simplicial complex:

the nerve of an explicitcategory of cube paths(with inclusions as morphisms).

(22)

Want to know more?

Thank you!

Rick Jardine, Path categories and resolutions

forthcoming AGT-paper Simplicial models of trace spaces Thank you for your attention!

Simplicial models for trace spaces