Intro: State space and trace space

Simplicial models for trace spaces

Martin Raussen

Department of Mathematical Sciences Aalborg University

Denmark

Workshop on Computational Topology Fields Institute, Toronto 8.11.2011

Table of Contents

Examples: State spacesand associatedpath spacesin Higher Dimensional Automata (HDA)

Motivation: Concurrency

Simplest case: State spaces and path spaces related tolinear PV-programs

Tool: Cutting up path spaces intocontractible subspaces

Homotopy type of path space described by amatrix poset categoryand realized by aprodsimplicial complex Algorithmics: Detectingdeadandalivesubcomplexes/matrices

Outlook: How to handlegeneral HDA

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³\F

minus 4 box obstructions

Path space modelcontained in torus(_∂∆²)²–

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

Analogy in standard algebraic topology

Relation between spaceX and loop spaceΩX.

Intro: State space and trace space

Pre-cubical set as state space

Example 2: State space and trace space for a non-looping pre-cubical complex

State space:Boundaries of two cubes glued together at common squareAB⁰C⁰•

Path spacemodel:

Prodsimplicial complex contained in(_∂∆²)²∪_∂∆²– homotopy equivalent to S¹∨S¹

Intro: State space and trace space

with loops

Example 3: Torus with a hole

• • • •

• •

X

• •

• N • •

• • • •

State space with holeX: 2D torus∂∆²×_∂∆²with a rectangle∆¹×_∆¹removed

Path spacemodel:

Discrete infinite space of dimension 0 corresponding to{r,u}^∗

Motivation: Concurrency

Semaphores: A simple model for mutual exclusion Mutual exclusion

occurs, whennprocessesP_i compete formresourcesR_j.

Onlyk 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: probeer;V: verhoog

Motivation: Concurrency

Semaphores: A simple model for mutual exclusion Mutual exclusion

occurs, whennprocessesP_i compete formresourcesR_j.

Onlyk 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: probeer;V: verhoog

A geometric model: Schedules in "progress graphs"

The Swiss flag example

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

000000000000000000 111111111111111111 00

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0

11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 1

Unsafe Un−

reachable

T1 T2

Pa Pb Vb Va

Pb Pa Va Vb

(0,0)

(1,1)

PV-diagram from P₁ :PaP_bV_bVa

P₂ :P_bP_aV_aV_b

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

Dipaths that aredihomotopic (through a 1-parameter deformation consisting of dipaths) correspond to equivalentexecutions.

Deadlocks, unsafeand unreachableregions may occur.

A geometric model: Schedules in "progress graphs"

The Swiss flag example

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

000000000000000000 111111111111111111 00

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0

11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 1

Unsafe Un−

reachable

T1 T2

Pa Pb Vb Va

Pb Pa Va Vb

(0,0)

(1,1)

PV-diagram from P₁ :PaP_bV_bVa

P₂ :P_bP_aV_aV_b

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

Dipaths that aredihomotopic (through a 1-parameter deformation consisting of dipaths) correspond to equivalentexecutions.

Deadlocks, unsafeand unreachableregions may occur.

A geometric model: Schedules in "progress graphs"

The Swiss flag example

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

000000000000000000 111111111111111111 00

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0

11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 1

Unsafe Un−

reachable

T1 T2

Pa Pb Vb Va

Pb Pa Va Vb

(0,0)

(1,1)

PV-diagram from P₁ :PaP_bV_bVa

P₂ :P_bP_aV_aV_b

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

Dipaths that aredihomotopic (through a 1-parameter deformation consisting of dipaths) correspond to equivalentexecutions.

Deadlocks, unsafeand unreachableregions may occur.

Simple Higher Dimensional Automata

Semaphore models The state space

Alinear PV-program is modeled as the complement of a forbidden regionFconsisting of a number ofholesin an n-cube:

Hole= isothetic hyperrectangle

Rⁱ =]aⁱ₁,b₁ⁱ[× · · · ×]aⁱ_n,b_nⁱ[⊂Iⁿ,1≤i≤l:

with minimal vertexaⁱ and maximal vertexbⁱ. State spaceX=~Iⁿ\F, F =^Sl_i=1Rⁱ

Xinherits a partial order from~Iⁿ.

More general (PV)-programs:

Replace~Iⁿby a productΓ1× · · · ×Γnofdigraphs.

Holes have then the formp₁ⁱ((0,1))× · · · ×p_nⁱ((0,1))with pⁱ_j :~I→Γj a directed injective (d-)path.

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

Simple Higher Dimensional Automata

Semaphore models The state space

Alinear PV-program is modeled as the complement of a forbidden regionFconsisting of a number ofholesin an n-cube:

Hole= isothetic hyperrectangle

Rⁱ =]aⁱ₁,b₁ⁱ[× · · · ×]aⁱ_n,b_nⁱ[⊂Iⁿ,1≤i≤l:

with minimal vertexaⁱ and maximal vertexbⁱ. State spaceX=~Iⁿ\F, F =^Sl_i=1Rⁱ

Xinherits a partial order from~Iⁿ.

More general (PV)-programs:

Replace~Iⁿby a productΓ1× · · · ×Γnofdigraphs.

Holes have then the formp₁ⁱ((0,1))× · · · ×p_nⁱ((0,1))with pⁱ_j :~I→Γj a directed injective (d-)path.

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

Simple Higher Dimensional Automata

Semaphore models The state space

Alinear PV-program is modeled as the complement of a forbidden regionFconsisting of a number ofholesin an n-cube:

Hole= isothetic hyperrectangle

Rⁱ =]aⁱ₁,b₁ⁱ[× · · · ×]aⁱ_n,b_nⁱ[⊂Iⁿ,1≤i≤l:

with minimal vertexaⁱ and maximal vertexbⁱ. State spaceX=~Iⁿ\F, F =^Sl_i=1Rⁱ

Xinherits a partial order from~Iⁿ.

More general (PV)-programs:

Replace~Iⁿby a productΓ1× · · · ×Γnofdigraphs.

Holes have then the formp₁ⁱ((0,1))× · · · ×p_nⁱ((0,1))with pⁱ_j :~I→Γj a directed injective (d-)path.

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

Spaces of d-paths/traces – up to dihomotopy

the interesting spaces Definition

X ad-space,a,b ∈X.

p:~I →X ad-pathinX (continuous and

“order-preserving”) fromatob.

~P(X)(a,b)={p:~I →X|p(0) =a,p(b) =1,pa 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).

Adihomotopyon~P(X)(a,b)is a mapH:~I×I →X such thatHt ∈~P(X)(a,b), t ∈I; ie a path in~P(X)(a,b).

Aim:

Description of thehomotopy typeof~P(X)(a,b)asexplicit finite dimensional prodsimplicial complex.

In particular: itspath components, ie the dihomotopy classes of d-paths (executions).

Spaces of d-paths/traces – up to dihomotopy

the interesting spaces Definition

X ad-space,a,b ∈X.

p:~I →X ad-pathinX (continuous and

“order-preserving”) fromatob.

~P(X)(a,b)={p:~I →X|p(0) =a,p(b) =1,pa 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).

Adihomotopyon~P(X)(a,b)is a mapH:~I×I →X such thatHt ∈~P(X)(a,b), t ∈I; ie a path in~P(X)(a,b).

Aim:

Description of thehomotopy typeof~P(X)(a,b)asexplicit finite dimensional prodsimplicial complex.

In particular: itspath components, ie the dihomotopy classes of d-paths (executions).

Spaces of d-paths/traces – up to dihomotopy

the interesting spaces Definition

X ad-space,a,b ∈X.

p:~I →X ad-pathinX (continuous and

“order-preserving”) fromatob.

~P(X)(a,b)={p:~I →X|p(0) =a,p(b) =1,pa 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).

Adihomotopyon~P(X)(a,b)is a mapH:~I×I →X such thatHt ∈~P(X)(a,b), t ∈I; ie a path in~P(X)(a,b).

Aim:

Description of thehomotopy typeof~P(X)(a,b)asexplicit finite dimensional prodsimplicial complex.

In particular: itspath components, ie the dihomotopy classes of d-paths (executions).

Spaces of d-paths/traces – up to dihomotopy

the interesting spaces Definition

X ad-space,a,b ∈X.

p:~I →X ad-pathinX (continuous and

“order-preserving”) fromatob.

~P(X)(a,b)={p:~I →X|p(0) =a,p(b) =1,pa 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).

Adihomotopyon~P(X)(a,b)is a mapH:~I×I →X such thatHt ∈~P(X)(a,b), t ∈I; ie a path in~P(X)(a,b).

Aim:

Description of thehomotopy typeof~P(X)(a,b)asexplicit finite dimensional prodsimplicial complex.

In particular: itspath components, ie the dihomotopy classes of d-paths (executions).

Tool: Subspaces of X and of ~ _P ( X )( 0, 1 )

X =~_Iⁿ\F,F =^Sl_i=1Rⁱ;Rⁱ = [aⁱ,bⁱ];0,1the two corners inIⁿ.

Definition

1 X_ij ={x ∈X|x ≤bⁱ ⇒x_j ≤aⁱ_j}– directionjrestricted at holei

2 M a binaryl×n-matrix:X_M =^T_mij=1X_ij

First Examples:

M = 1 0

1 0

1 0 0 1

0 1 1 0

0 1 0 1

M =

[100] [010] [001]

Tool: Subspaces of X and of ~ _P ( X )( 0, 1 )

X =~_Iⁿ\F,F =^Sl_i=1Rⁱ;Rⁱ = [aⁱ,bⁱ];0,1the two corners inIⁿ.

Definition

1 X_ij ={x ∈X|x ≤bⁱ ⇒x_j ≤aⁱ_j}– directionjrestricted at holei

2 M a binaryl×n-matrix:X_M =^T_mij=1X_ij

First Examples:

M = 1 0

1 0

1 0 0 1

0 1 1 0

0 1 0 1

M =

[100] [010] [001]

Covers by contractible (or empty) subspaces

Bookkeeping with binary matrices Binary matrices

M_l,n poset(≤) ofbinaryl×n-matrices M_l,n^R,∗ no rowvector is thezerovector M_l,n^R,u every rowvector is aunitvector M_l,n^C,u every columnvector is aunitvector

A cover:

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

M∈M_l,n^R,u

~P(X_M)(0,1).

Theorem

Every path space~P(X_M)(0,1),M∈M_l,n^R,∗, isemptyor

contractible. Which is which?

Proof.

SubspacesX_M,M∈M_l,n^R,∗areclosed under∨= l.u.b.

Covers by contractible (or empty) subspaces

Bookkeeping with binary matrices Binary matrices

M_l,n poset(≤) ofbinaryl×n-matrices M_l,n^R,∗ no rowvector is thezerovector M_l,n^R,u every rowvector is aunitvector M_l,n^C,u every columnvector is aunitvector

A cover:

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

M∈M_l,n^R,u

~P(X_M)(0,1).

Theorem

Every path space~P(X_M)(0,1),M∈M_l,n^R,∗, isemptyor

contractible. Which is which?

Proof.

SubspacesX_M,M∈M_l,n^R,∗areclosed under∨= l.u.b.

Covers by contractible (or empty) subspaces

Bookkeeping with binary matrices Binary matrices

M_l,n poset(≤) ofbinaryl×n-matrices M_l,n^R,∗ no rowvector is thezerovector M_l,n^R,u every rowvector is aunitvector M_l,n^C,u every columnvector is aunitvector

A cover:

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

M∈M_l,n^R,u

~P(X_M)(0,1).

Theorem

Every path space~P(X_M)(0,1),M∈M_l,n^R,∗, isemptyor

contractible. Which is which?

Proof.

SubspacesX_M,M∈M_l,n^R,∗areclosed under∨= l.u.b.

A combinatorial model and its geometric realization

First examples Combinatorics poset category

C(X)(0,1)⊆M_l^R,∗_,n ⊆Ml,n

M∈ C(X)(0,1)“alive”

Topology:

prodsimplicial complex T(X)(0,1)⊆(∆ⁿ⁻¹)^l

∆M =∆m₁× · · · ×∆m_l ⊆ T(X)(0,1)

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

Examples of path spaces

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 1

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

=4∗

T(X2)(0,1) =3∗

⊃ C(X)(0,1)

A combinatorial model and its geometric realization

First examples Combinatorics poset category

C(X)(0,1)⊆M_l^R,∗_,n ⊆Ml,n

M∈ C(X)(0,1)“alive”

Topology:

prodsimplicial complex T(X)(0,1)⊆(∆ⁿ⁻¹)^l

∆M =∆m₁× · · · ×∆m_l ⊆ T(X)(0,1)

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

Examples of path spaces

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 1

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

=4∗

T(X2)(0,1) =3∗

⊃ C(X)(0,1)

A combinatorial model and its geometric realization

First examples Combinatorics poset category

C(X)(0,1)⊆M_l^R,∗_,n ⊆Ml,n

M∈ C(X)(0,1)“alive”

Topology:

prodsimplicial complex T(X)(0,1)⊆(∆ⁿ⁻¹)^l

∆M =∆m₁× · · · ×∆m_l ⊆ T(X)(0,1)

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

Examples of path spaces

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 1

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

=4∗

T(X2)(0,1) =3∗

⊃ C(X)(0,1)

Further examples

State spaces, “alive” matrices and path spaces

1 X =~_Iⁿ\~_Jⁿ

2

1 C(X)(0,1) =M_1,n^R,∗\ {[1,. . .1]}. T(X)(0,1) =_∂∆ⁿ⁻¹ 'Sⁿ⁻².

2 C_max(X)(0,1) = {

0 1 1

0 1 1

,

1 0 1

1 0 1

,

1 1 0

1 1 0

}. C(X)(0,1) ={M ∈M_l,n^R,∗| ∃N ∈ C_max(X)(0,1):M ≤N} T(X)(0,1) =3 diagonal squares⊂(∂∆²)²=T²

'S¹. More examples in Mimram’s talk!

Further examples

State spaces, “alive” matrices and path spaces

1 X =~_Iⁿ\~_Jⁿ

2

1 C(X)(0,1) =M_1,n^R,∗\ {[1,. . .1]}. T(X)(0,1) =_∂∆ⁿ⁻¹ 'Sⁿ⁻².

2 C_max(X)(0,1) =

{

0 1 1

0 1 1

,

1 0 1

1 0 1

,

1 1 0

1 1 0

}. C(X)(0,1) ={M ∈M_l,n^R,∗| ∃N ∈ C_max(X)(0,1):M ≤N} T(X)(0,1) =3 diagonal squares⊂(∂∆²)²=T²

'S¹. More examples in Mimram’s talk!

Further examples

State spaces, “alive” matrices and path spaces

1 X =~_Iⁿ\~_Jⁿ

2

1 C(X)(0,1) =M_1,n^R,∗\ {[1,. . .1]}. T(X)(0,1) =_∂∆ⁿ⁻¹ 'Sⁿ⁻².

2 C_max(X)(0,1) =

{

0 1 1

0 1 1

,

1 0 1

1 0 1

,

1 1 0

1 1 0

}. C(X)(0,1) ={M ∈M_l,n^R,∗| ∃N ∈ C_max(X)(0,1):M ≤N} T(X)(0,1) =3 diagonal squares⊂(∂∆²)²=T²

'S¹. More examples in Mimram’s talk!

Homotopy equivalence between trace space

~ _T ( X )( 0, 1 ) and the 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.

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

D(M) =~P(X_M)(0,1), E(M) =∆M,

T(M) =∗

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.

Homotopy equivalence between trace space

~ _T ( X )( 0, 1 ) and the 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.

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

D(M) =~P(X_M)(0,1), E(M) =∆M,

T(M) =∗

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.

Homotopy equivalence between trace space

~ _T ( X )( 0, 1 ) and the 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.

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

D(M) =~P(X_M)(0,1), E(M) =∆M,

T(M) =∗

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.

Why prodsimplicial?

rather than simplicial

We distinguish, for every obstruction,setsJ_i ⊂[1:n]of restrictions. A joint restriction is of product type

J₁× · · · ×J_l ⊂[1:n]^l, andnot an arbitrary subset of [1:n]^l.

Simplicial model: a subcomplex of∆^nl –2^(nl) subsimplices.

Prodsimplicial model: a subcomplex of(_∆ⁿ)^l –2^(nl) subsimplices.

Why prodsimplicial?

rather than simplicial

We distinguish, for every obstruction,setsJ_i ⊂[1:n]of restrictions. A joint restriction is of product type

J₁× · · · ×J_l ⊂[1:n]^l, andnot an arbitrary subset of [1:n]^l.

Simplicial model: a subcomplex of∆^nl –2^(nl) subsimplices.

Prodsimplicial model: a subcomplex of(_∆ⁿ)^l –2^(nl) subsimplices.

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

Questions answered by homology calculations usingT(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 ofpath-components?

Are componentssimply connected?

Other topological properties?

Strategies – Attempts

ImplementationofT(X)(0,1)in ALCOOL:

Progress at CEA/LIX-lab.: Goubault, Haucourt, Mimram The prodsimplicial structure onC(X)(0,1)↔T(X)(0,1) leads to an associatedchain complexof vector spaces over a field.

Use fast algorithms (eg Mrozek CrHom etc) to calculate thehomologygroups of these chain complexes even for very big complexes: M. Juda (Krakow).

Number of path-components:rkH0(T(X)(0,1)).

For path-components alone, there are faster “discrete”

methods, that also yield representatives in each path component: Mimram’s talk!

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

Questions answered by homology calculations usingT(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 ofpath-components?

Are componentssimply connected?

Other topological properties?

Strategies – Attempts

ImplementationofT(X)(0,1)in ALCOOL:

Progress at CEA/LIX-lab.: Goubault, Haucourt, Mimram The prodsimplicial structure onC(X)(0,1)↔T(X)(0,1) leads to an associatedchain complexof vector spaces over a field.

Use fast algorithms (eg Mrozek CrHom etc) to calculate thehomologygroups of these chain complexes even for very big complexes: M. Juda (Krakow).

Number of path-components:rkH0(T(X)(0,1)).

For path-components alone, there are faster “discrete”

methods, that also yield representatives in each path component: Mimram’s talk!

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

Questions answered by homology calculations usingT(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 ofpath-components?

Are componentssimply connected?

Other topological properties?

Strategies – Attempts

ImplementationofT(X)(0,1)in ALCOOL:

Progress at CEA/LIX-lab.: Goubault, Haucourt, Mimram The prodsimplicial structure onC(X)(0,1)↔T(X)(0,1) leads to an associatedchain complexof vector spaces over a field.

Use fast algorithms (eg Mrozek CrHom etc) to calculate thehomologygroups of these chain complexes even for very big complexes: M. Juda (Krakow).

Number of path-components:rkH0(T(X)(0,1)).

For path-components alone, there are faster “discrete”

methods, that also yield representatives in each path component: Mimram’s talk!

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

Questions answered by homology calculations usingT(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 ofpath-components?

Are componentssimply connected?

Other topological properties?

Strategies – Attempts

ImplementationofT(X)(0,1)in ALCOOL:

Progress at CEA/LIX-lab.: Goubault, Haucourt, Mimram The prodsimplicial structure onC(X)(0,1)↔T(X)(0,1) leads to an associatedchain complexof vector spaces over a field.

Use fast algorithms (eg Mrozek CrHom etc) to calculate thehomologygroups of these chain complexes even for very big complexes: M. Juda (Krakow).

Number of path-components:rkH0(T(X)(0,1)).

For path-components alone, there are faster “discrete”

methods, that also yield representatives in each path component: Mimram’s talk!

Detection of dead and alive subcomplexes

An algorithm starts with deadlocks and unsafe regions!

Allow less = forbid more!

RemoveextendedhyperrectanglesR_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 “dead” matrix N ≤M,N ∈M_l,n^C,usuch that T

nij=1R_jⁱ 6= _∅– giving rise to adeadlockunavoidable from 0, i.e., T(X_N)(0,1) =_∅.

Detection of dead and alive subcomplexes

An algorithm starts with deadlocks and unsafe regions!

Allow less = forbid more!

RemoveextendedhyperrectanglesR_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 “dead” matrix N ≤M,N ∈M_l,n^C,usuch that T

nij=1R_jⁱ 6= _∅– giving rise to adeadlockunavoidable from 0, i.e., T(X_N)(0,1) =_∅.

Dead matrices in D ( X )( 0, 1 )

Inequalities decide Decisions: Inequalities

Deadlock algorithm (Fajstrup, Goubault, Raussen) : Theorem

N∈M_l,n^C,udead⇔

For all1≤j≤n, for all1≤k≤n such that∃j⁰:n_kj0=1:

n_ij =1⇒aⁱ_j<b^k_j.

M∈M_l,n^R,∗dead⇔ ∃N∈M_l,n^C,udead, N ≤M.

Definition

D(X)(0,1):={P∈M_l,n|∃N∈M_l,n^C,u,Ndead:N≤P}.

A cube with a cube hole X=~_Iⁿ\~_Jⁿ

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

Dead matrices in D ( X )( 0, 1 )

Inequalities decide Decisions: Inequalities

Deadlock algorithm (Fajstrup, Goubault, Raussen) : Theorem

N∈M_l,n^C,udead⇔

For all1≤j≤n, for all1≤k≤n such that∃j⁰:n_kj0=1:

n_ij =1⇒aⁱ_j<b^k_j.

M∈M_l,n^R,∗dead⇔ ∃N∈M_l,n^C,udead, N ≤M.

Definition

D(X)(0,1):={P∈M_l,n|∃N∈M_l,n^C,u,Ndead:N≤P}.

A cube with a cube hole X=~_Iⁿ\~_Jⁿ

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

Maximal alive ↔ minimal dead

Still alive – not yet dead

Cmax(X)(0,1)⊂ C(X)(0,1)maximalalive matrices.

Matrices inC_max(X)(0,1)correspond tomaximal simplex productsinT(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 removed from a cube

X =~_Iⁿ\~_Jⁿ_,D(X)(0,1) ={[1,. . .,1]}; Cmax(X)(0,1): vectors with a single 0;

C(X)(0,1) =M_l,n^R \ {[1,. . .,1]}; T(X)(0,1) =_∂∆ⁿ⁻¹.

Maximal alive ↔ minimal dead

Still alive – not yet dead

Cmax(X)(0,1)⊂ C(X)(0,1)maximalalive matrices.

Matrices inC_max(X)(0,1)correspond tomaximal simplex productsinT(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 removed from a cube

X =~_Iⁿ\~_Jⁿ_,D(X)(0,1) ={[1,. . .,1]}; Cmax(X)(0,1): vectors with a single 0;

C(X)(0,1) =M_l,n^R \ {[1,. . .,1]}; T(X)(0,1) =_∂∆ⁿ⁻¹.

Extensions

1. Obstruction hyperrectangles intersecting the boundary ofIⁿ - Components

More general linear semaphore state spaces

More general semaphores (intersection with the boundary

∂Iⁿ ⊂Iⁿallowed)

ndining philosophers: Trace space has2ⁿ−2 contractible components!

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

State space components

New light on definition and determination ofcomponentsof model spaceX.

Extensions

1. Obstruction hyperrectangles intersecting the boundary ofIⁿ - Components

More general linear semaphore state spaces

More general semaphores (intersection with the boundary

∂Iⁿ ⊂Iⁿallowed)

ndining philosophers: Trace space has2ⁿ−2 contractible components!

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

State space components

New light on definition and determination ofcomponentsof model spaceX.

Extensions

2a. Semaphores corresponding tonon-linearprograms:

Path spaces in product of digraphs Products ofdigraphsinstead of~_Iⁿ_: Γ=_∏ⁿ_j=1Γj, state spaceX = _Γ\F,

F a product of generalized hyperrectanglesRⁱ.

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

Pullback to linear situation

Represent apath componentC ∈~_P(_Γ)(x,y)by (regular) d-pathsp_j ∈~_P(_Γj)(x_j,y_j)– an interleaving.

The mapc:~_Iⁿ→_Γ,c(t₁,. . .,t_n) = (c₁(t₁),. . .,c_n(t_n))induces ahomeomorphism◦c :~_P(~_Iⁿ)(0,1)→C⊂~_P(_Γ)(x,y).

Extensions

2a. Semaphores corresponding tonon-linearprograms:

Path spaces in product of digraphs Products ofdigraphsinstead of~_Iⁿ_: Γ=_∏ⁿ_j=1Γj, state spaceX = _Γ\F,

F a product of generalized hyperrectanglesRⁱ.

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

Pullback to linear situation

Represent apath componentC ∈~_P(_Γ)(x,y)by (regular) d-pathsp_j ∈~_P(_Γj)(x_j,y_j)– an interleaving.

The mapc:~_Iⁿ→_Γ,c(t₁,. . .,t_n) = (c₁(t₁),. . .,c_n(t_n))induces ahomeomorphism◦c :~_P(~_Iⁿ)(0,1)→C⊂~_P(_Γ)(x,y).

Extensions

2b. Semaphores: Topology of components of interleavings Homotopy types of interleaving components Pull backF viac:

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

iX :~_P(X),→~_P(Γ).

Given a componentC⊂~_P(_Γ)(x,y).

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

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

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

Exploit relations between various components.

Special case:Γ= (S¹)ⁿ– a torus

State space: A torus with rectangular holes inF: Investigated by Fajstrup, Goubault, Mimram etal.:

Analyse bylanguageon the alphabetC(X)(0,1)ofalive matrices for a one-fold delooping ofΓ\F.

Extensions

2b. Semaphores: Topology of components of interleavings Homotopy types of interleaving components Pull backF viac:

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

iX :~_P(X),→~_P(Γ).

Given a componentC⊂~_P(_Γ)(x,y).

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

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

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

Exploit relations between various components.

Special case:Γ= (S¹)ⁿ– a torus

State space: A torus with rectangular holes inF: Investigated by Fajstrup, Goubault, Mimram etal.:

Analyse bylanguageon the alphabetC(X)(0,1)ofalive matrices for a one-fold delooping ofΓ\F.