(Prod-)Simplicial models for trace spaces

(1)

(Prod-)Simplicial models for trace spaces

Martin Raussen

Department of Mathematical Sciences Aalborg University

Denmark

GETCO Aalborg 12.1.2010

Martin Raussen (Prod-)Simplicial models for trace spaces

(2)

State space and model of trace space

How are they related?

State space =

a cube minus 4 obstructions

Trace space within in a torus homotopy equivalent to a wedge of two circles and a point

(3)

Motivation: Concurrency

Mutual exclusion

Mutual exclusion occurs, 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)

(4)

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 P V V

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

(5)

Simple Higher Dimensional Automata

Semaphore models

Alinear PV-program can be modelled as the complement of a number of holes in an n-cube:

isothetic hyperrectanglesRⁱ,1≤i ≤l, in an n-cube:

X =~_In\F, F =

[l

i=1

Rⁱ, Rⁱ =]aⁱ₁,b₁ⁱ[× · · · ×]aⁱ_n,bⁱ_n[^.

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 (d-)path.

(6)

Spaces of d-paths/traces, 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 Ht ∈~_P(X)(a,b)^, t ∈I.

Aim: Describe thehomotopy typeof~_P(X)(a,b); in particular its path components, i.e., 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ⁱ;0,1 the two corners.

Definition

For 1≤j_i ≤n let

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}

Examples:

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

1≤j₁,...,j_l≤n

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

(8)

More intricate subspaces

as intersections

Definition

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

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}

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

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

(9)

Bookkeeping with binary matrices

M_l,n (vector space/Boolean algebra of)binary l×n-matrices

M_l,n^R no row vector is the zero vector M_l,n^C every column vector is a unit vector

Index 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 susbsets6=^∅ ↔ 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)^.

(10)

A combinatorial model and its geometric realization

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!!!

(11)

Properties of the decomposition of path space

Theorem

1 ~_P(X)(0,1) =^S₁_≤_i_≤_l,1_≤_j_i_≤_n~_P(X_j₁_,...,j_l)(0,1).

2 For every M ∈ C(X)(0,1):

~_P(X_M)(0,1)iscontractible.

Proof.

All X_M,M ∈M_l,n^R areclosed under∨=max.

D-homotopyH(p,q)connecting p,q ∈~_P(X_M)(0,1): G(p,q)^:p→p∨q,G(q,p)^:q →p∨q,

H(p,q) =G(q,p)∗G⁻(p,q) G(p,q;t)(s) =p(s)∨q(ts)

Contraction: Choose p∈~_P(X_M)(0,1). q 7→H(p,q)

(12)

Homotopy equivalence between path space and a prodsimplicial complex

Theorem

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

Proof.

FunctorsD^,E^,T ^:C(X)(0,1)→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:

(13)

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

Questions answered by homology calculations

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?

The prodsimplicial structure onC(X)(0,1)↔T(X)(0,1)leads to an associated chain complex of vector spaces.

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

For example: The number of path-components is the rank of the homology group in degree 0.

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.

(14)

Deadlocks and unsafe regions determine C ( X )

A dual view: extendedhyperrectangles:

R_jⁱ := [0,b₁ⁱ[× · · · ×[0,bⁱ_j₋₁[×]aⁱ_j,bⁱ_j[×[0,b_jⁱ₊₁[× · · · ×[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₁_≤_j_≤_nR_jⁱ⁽^j⁾6=^∅– giving rise to adeadlock unavoidable from 0.

3 Checking a bunch ofinequalities:

(15)

Partial orders and order ideals on matrix spaces

and an order preserving mapΨ

The partial order on 0,1: 0≤0,0≤1,1≤1 extends to M_l,n. ConsiderΨ:M_l,n→Z/2, Ψ(M) =1⇔~_P(X_JM)(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 Examples!.

Matrices in Cmax(X)(0,1)correspond to maximal simplex products in T(X)(0,1).

(16)

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.

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

j for all 1≤j,k ≤n.

Requires to check a bunch of inequalities or ratherorder relations.

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

(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. Examples!

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

~_P(X)(c,d)and iterative calculations

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

New light on definition and determination ofcomponents.

(19)

Extensions

2a. Semaphores corresponding tonon-linearprograms:

Γ=∏ⁿ_j₌₁Γ_j, state space X =^Γ\F,F 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).

Pull back F via c:

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

(20)

Extensions

2b. Semaphores: Topology of components of interleavings

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).

(Prod-)Simplicial models for trace spaces