数理解析研究所講究録996 巻 1997 年 207-221

207

Towards Cycle Filling as Parallelization$\mathrm{Y}_{11}\mathrm{k}\mathrm{i}1_{1}\mathrm{i}\mathrm{C}1(^{\mathrm{Y}}\mathrm{T}\cdot \mathrm{a}1_{\vee}^{-}1*\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{n}\mathrm{a}$Science, Rit,stlm(
Depart,ment, ofUniversity
1916 Noji-ch , Kusat,su-shi, Shiga 525.
email:.ac.jp$\backslash ,\mathrm{i}\mathrm{k}_{t\backslash }\mathrm{n}$$\mathrm{c}_{\mathrm{t})\mathrm{I}\mathrm{n}}\mathrm{P}^{11}\mathrm{t}\mathrm{e}1$$\mathit{0}$$\mathrm{J}_{C\backslash _{\mathrm{P}}}e\mathrm{t}\prime \mathrm{n}$$\mathrm{t}\mathrm{a}\mathrm{k}_{i}\iota \mathrm{y}\subset\gamma \mathrm{I}\mathrm{n}\mathrm{a}\mathrm{C}\mathrm{c}\underline{\mathrm{i})}\mathrm{t},\mathrm{h}_{\mathrm{C}\mathrm{o}}1\mathrm{y}.\mathrm{C}\mathrm{s}.\mathrm{r}\mathrm{i}\mathrm{t},\mathrm{S}11\mathrm{m}\mathrm{e}\mathrm{i}$$\mathrm{S}(^{\backslash }\mathrm{I}^{)}\mathrm{t}\mathrm{t}^{\mathrm{Y}}\mathrm{n}1|)(\mathrm{Y}\mathrm{r}24$, 1996

Abstract
We give a new formulation of(HDA) called cubic $al$ Barnotation. It gives an intrinsicof hypercubes which are building )of HDA.
The gain is ananddefinition of cycle filling.
we have anentation of Hoare traces and Mazurkiewicz traces. The cycle filling map canto realize the idea of cycle filling as parallelization $[2, 8]$ . Combined with the extraction)
algorithnl ofsions fronl HDA [9], the cycle filling
will realize aoftran:ifornlation in concurrent )languages as geometricof higher dilnellsional spaces.
$\mathrm{H}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{e}\mathrm{r}- \mathrm{D}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{l}\mathrm{l}\iota \mathrm{s}\mathrm{i}0\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{A}_{1}1\mathrm{f}\mathrm{o}111\mathrm{R}\mathrm{t}\mathrm{a}$$\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}_{0}11$$\mathrm{e}\mathrm{x}_{1^{)}}1\mathrm{i}\mathrm{C}\mathrm{i}\mathrm{t}$$1$$\mathrm{l}\mathrm{o}\mathrm{C}\mathrm{k}.\mathrm{b}$$\mathrm{A}\mathrm{k}o$$\mathrm{s}_{\mathrm{L}}\mathrm{i}\mathrm{m}_{1^{)}}1\mathrm{e}$$\mathrm{e}\mathrm{x}_{1^{)}}1\mathrm{i}_{\mathrm{C}}\mathrm{i}\mathrm{t}$$\mathrm{n}\mathrm{l}\mathrm{a}_{1^{)}}$$[)\mathrm{e}\iota \mathrm{l}\mathrm{s}\mathrm{e}\mathrm{d}$$\mathrm{r}\mathrm{e}_{1^{)}}\mathrm{r}\mathrm{p}_{\mathrm{L}}\mathrm{S}$$\mathrm{r}\mathrm{e}\iota \mathrm{q}$$\mathrm{n}\mathrm{l}\mathrm{e}\mathrm{t}1_{1}\mathrm{o}\mathrm{d}$$1^{)\mathrm{r}o}\mathrm{c}\mathrm{p}\mathrm{s}\mathrm{S}\mathrm{e}\mathrm{X}\mathrm{l}$$\mathrm{m}\mathrm{a}_{1^{)}}$$1)\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}$1$1$$\uparrow \mathrm{r}\mathrm{a}11^{\epsilon \mathrm{f}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{t}}.,0\mathrm{i}_{0\mathrm{n}}$$\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{n}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g}$Introduction)In. we will consid ain. which is stat,ed asfollows: Given a process
P. how can we mechanically find a )expression
$P$
and
are )
and ( is more parallel t,han
example. $Q=(a||l)||c$ )
, of
is a
: $(l)||c)+l)$ : $(a_{\backslash }^{\vee}c+c;a)+c$ ; $(a_{!}. l)+l)$ : ) wherc $(-|| -)$ andareparallelcomposit,ion and sequent,ial composit,ion.
$(-! -)$
may bet,o t,his. One candidate is the. By decomposit,ion we can, an cxplicit, algorithm t,o find
check
is a
of $P,$
is not,given.
candidate ist,hestyle t,race. Let, [int,of P. $H_{P}=\{al)c.acb, l)aC, l)ca. Cal).Cl)a\}$ is t,he set of maximal
for$P$ and $Ip=\{<|).
C>_{a}\}$ is t,he set, of prefixed independence relat,ion)
means$ol)c=acl)$ . Then we find new set of relations $I=\{<a.l)>,$ $<l).c>,$ $<ti.a>$ . $<c.a>_{b}$wit,h some suit,ablet,he merged.
. and merge andto$J=\{<\mathit{0},. l).c>\}$ . which means
obt,ained. ) and are pairwise commut,ative. Thenint, )$P$t,he.
semant,ics
equal to [
we
So
a
of at
level. However. fordegree ofbetween $P$ andext,ract,ing t,he
t,he semant,ical palal1(. $J>$ . we wollld need a richer
in t,he semant,ics dolnain.
$\mathrm{t},\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{l}$$\mathrm{e}\mathrm{l}$$\mathrm{p}\mathrm{a}\mathrm{l}_{l}\lambda 11(^{\backslash },1\mathrm{i}_{\mathrm{Z}}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{P}^{\mathrm{r}}\mathrm{o}1)1\mathrm{e}\mathrm{m}$$(^{\backslash },1$$\mathrm{P}\mathrm{l}\cdot \mathrm{o}\mathrm{c}(),\mathrm{s}\mathrm{S}\mathrm{a}(^{\backslash },\mathrm{b}_{1}\cdot \mathrm{a}$$Q$$\exp_{\mathrm{l}\mathrm{C}\mathrm{S}\mathrm{S}}\mathrm{i}_{0}\mathrm{n}$

$1$

$Q$

$\mathrm{s}\iota\iota \mathrm{C}\mathrm{h}\mathrm{t},\mathrm{h}_{C\backslash }\mathrm{t},$$\mathrm{f}$$\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{l}\mathrm{n}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{r}$$?$$P=\mathit{0}$$p_{C\iota\Gamma\prime ll}C,l?\nearrow,\prime t?,O7|$$1^{\cdot}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{S}$$P?\mathrm{F}\mathrm{o}1^{\cdot}$$a$$\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{l}\cdot \mathrm{C}$$\ln^{r}‘ \mathrm{t}\mathrm{n}\mathrm{y}‘\backslash \mathrm{p}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{a}\mathrm{c}\mathrm{h}\mathrm{C}\mathrm{s}$$\mathrm{p}_{\mathrm{l}\mathrm{O}}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$$\mathrm{d}_{\mathrm{C}\mathrm{C}\mathrm{O}1}\mathrm{n}\mathrm{p}_{\mathrm{o}\mathrm{s}}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{t}_{}\mathrm{h}\mathrm{o}\mathrm{d}[4]$$\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{t},\mathrm{h}\mathrm{e}\mathrm{l}Q$$\mathrm{b}_{11}\mathrm{t}$$\mathrm{p}_{C\backslash 1_{C}}\cdot’\iota 11\mathrm{C}\mathrm{l}\mathrm{i}_{7},\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{A}\mathrm{n}\mathrm{o}\mathrm{t},\mathrm{h}\mathrm{e}\Gamma$$Q\mathrm{f}\mathrm{i}\cdot \mathrm{o}\mathrm{m}P$$\mathrm{M}\mathrm{a}7_{\mathrm{J}}1\mathrm{u}\cdot \mathrm{k}\mathrm{i}\mathrm{e}\mathrm{w}\mathrm{i}_{\mathrm{C}}\mathrm{z}$$P\mathrm{J}=<H_{P}..\cdot.I_{P}>\mathrm{f})\mathrm{e}$$\mathrm{t}_{r}\mathrm{h}\mathrm{e}\mathrm{o}1^{\cdot}\mathrm{y}[0]\ulcorner$$\mathrm{e}\mathrm{r}_{\mathrm{P}^{1\mathrm{e}\mathrm{t}\mathrm{t}}}\cdot \mathrm{a},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{H}\mathrm{o}_{C}\lambda 1^{\cdot}\mathrm{C}\mathrm{t}_{1_{C}^{r}},\cdot\iota \mathrm{C}\mathrm{e}\mathrm{s}$$\mathrm{w}\mathrm{h}\mathrm{c}\mathrm{l}\cdot \mathrm{C}<l$$<\mathit{0},.l)>_{c}\}$$a$$\mathrm{C}11$$I$$\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{l}\cdot \mathrm{i}\mathrm{t},\mathrm{h}\mathrm{m}$$1^{\cdot}\mathrm{e}\mathrm{t}\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{t}\mathrm{n}<H_{P}$$l$$J>\mathrm{i}\mathrm{s}$$o\mathrm{b}\mathrm{t},\mathrm{a}\mathrm{i}\mathrm{n}$$\mathrm{t}_{}\mathrm{h}\mathrm{e}$$\mathrm{o}\mathrm{t}_{)}\mathrm{t},\mathrm{a}\mathrm{i}\mathrm{n}$$\iota)_{C}’\iota 1^{\cdot}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{C}\tau 1\mathrm{i}_{\mathrm{Z}}\mathrm{a}\mathrm{t}_{r}\mathrm{i}0\mathrm{n}$)$\mathrm{p}\mathrm{a}\mathrm{l}\subset\backslash \mathrm{u}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{S}\mathrm{m}$$\mathrm{e}\mathrm{x}_{1^{)1\mathrm{C}\mathrm{s}}Q\mathrm{i}\mathrm{o}}\mathrm{S}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{f}\cdot \mathrm{m}$$1^{\cdot}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t},\mathrm{i}0\mathrm{n}$$c$$Q\mathrm{I}\cdot$$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\subset\lambda \mathrm{l}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t}_{}\mathrm{h}\mathrm{e}$$I_{T}\supset$$.c>_{\mathrm{f}l}$$Q_{\subset\backslash 1}1\mathrm{d}\mathrm{f}\mathfrak{c}$$1^{\cdot}$$\mathrm{Y},1\mathrm{i}_{\mathrm{Z}\mathrm{a}}\mathrm{t},\mathrm{i}_{0}\mathrm{n}<H_{P}$$\mathrm{s}\mathrm{t}_{111},\cdot \mathrm{c}\cdot \mathrm{t}_{11},1^{\cdot}\mathrm{e}$)Theach we will
in t,his
is based on Higher-Dimensional Ant,omat,a (HDA) [6. 10]
model of
. HDA model is a gcom(
formalizcd
t,he parallel. In
model. we int, )of atomic act, ns by t,he
t,he at,omic act,ions.
(77,-cllbe) spanned by the alcs
t,he
act,ions is)hand. nondet,of ?7,
by (spanned ),$\mathrm{t}_{5\subset}^{\Gamma}\mathrm{t}\mathrm{k}_{1}\urcorner$$\subset\backslash _{1^{)}\mathrm{p}\mathrm{r}}\mathit{0}$$\mathrm{p}\mathrm{a}_{1}$$\mathrm{C}1$$\mathrm{t},\mathrm{r}\iota 1\mathrm{t}^{\tau},$$\backslash ,\mathrm{t}_{\mathit{0}}1\mathrm{i}_{\mathrm{C}}1\mathrm{y}$$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{c}\mathrm{l}\mathrm{u}\cdot 1^{\cdot}\mathrm{C}\mathrm{n}\mathrm{c}\mathrm{y}$$\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{t},\mathrm{e}1^{\cdot}1_{\mathrm{C}}\mathrm{a}\mathrm{V}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t},1^{\cdot}t\backslash \mathrm{n}\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{i}_{0}\mathrm{n}$$\mathrm{t}_{0}\mathrm{h}\mathrm{c}$$1^{\cdot}\mathrm{e}\mathrm{t}$$\mathrm{s}\mathrm{y}_{\mathrm{S}\mathrm{t}_{\mathrm{C}}\mathrm{l}},\mathrm{n},\backslash ’$$\mathrm{C}\mathrm{l}\mathrm{l}$$\Gamma 1\ln$$\mathrm{i}o$$\mathit{7}\mathrm{t}- \mathrm{d}\mathrm{i}\mathrm{n}\mathrm{l}\mathrm{C}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}_{\dot{c}}\iota 1$$\mathit{7}7_{\text{ノ}}$$\mathrm{h}\mathrm{y}\iota)\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{l}\mathrm{l}\mathrm{b}\mathrm{t}\mathrm{Y}$$\mathrm{O}11$$\mathrm{c}\mathrm{o}\mathrm{l}\cdot 1^{\cdot}(\tau \mathrm{s}\iota)0\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t},\mathit{0}$$\mathrm{e}1^{\cdot}1\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{i}_{\mathrm{S}\mathrm{t}\mathrm{i}}9\mathrm{c}\mathrm{r}\mathrm{U}11$$\mathrm{a}\mathrm{t}_{\mathrm{o}\mathrm{n}1},\mathrm{i}_{\mathrm{C}}$$\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}1^{\cdot}\mathrm{p}\mathrm{r}\mathrm{C}\mathrm{t}_{e}\mathrm{e}\mathrm{d}\mathrm{s}\mathrm{i}\mathrm{m}_{1}$$1\mathrm{y}$$\mathrm{t},\mathrm{h}$$\mathrm{t}_{1},\cdot \mathrm{c}\mathrm{e}$$,$$o\mathrm{t},\mathrm{h}\mathrm{e}\mathrm{r}$$\mathrm{f}$$\mathrm{y}$208
is simply the dimension of the semantics space. For
the arcs. Hence t,hc degree of paral1)
above is t,he 3-cube spanned by arcs . ) and while t,heofexample,in the following figllre. We can see t,hat, t,he degree ofof $P$ above is the$(^{\backslash },1\mathrm{i}_{\mathrm{S}\ln}$$Q$$\mathrm{r}\mathrm{t}^{\backslash },\mathrm{t},\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{t}_{i}\mathrm{h}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{t}_{\mathrm{C}\mathrm{r}}1$

$l$

$a$

$c$

$\mathrm{s}_{1^{)\mathrm{a}\mathrm{C}\mathrm{C}}}(\mathrm{a})$$\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{c}\mathrm{r}_{\mathrm{P}^{1\mathbb{C}}}\cdot \mathrm{t},\mathrm{a}\mathrm{t},\mathrm{i}_{0}\mathrm{n}$(b)vert,ices alld edgesin (a). Also, by identifyingof is 2 since t,here is a,ain the space (b). We find five 2-dimensional cycles ill t,he space. Nalnely.
in this space. wet,he)and one closed pat,hs $c.l$) c. ). If we fillclosed pat,hs.
closedt,he,aint,hese cycles with five 2-cllbes. wespace (c). This space has a high -dimensional
cllbe. Finally. weby the 2-faces ofcycle, nalnely t,he 3-dimensional empty )
t,he
t,he
,ain
wit,
idea of cycle filliof . This is
a -cllbe and we
fill t.he cycle
int,rodllccd ) E. Gollba\iota llt, [2] in a
set,t,ing andwhich has )
as
t,o
,
t,he
Also,
an
gave
language.
in abyt,he process expression
fiom the obt,ained space [9].
,$2- \mathrm{C}\mathrm{l}\iota \mathrm{b}\mathrm{e}$$\Gamma$$1)\mathrm{a}1_{C}’.\iota 11\mathrm{Q}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{I}\mathrm{n}$$\mathrm{S}\mathrm{O}\mathrm{l}\mathrm{n}\mathrm{C}^{\backslash }$$\mathrm{o}\mathrm{b}\mathrm{t}$$\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{s}a.b.a.b$$\mathrm{t},\mathrm{w}\mathrm{o}$$a,$ $c,$ $a,$$\mathrm{t},\mathrm{w}o$

$1$

$l$

$c$

$.$

$\mathrm{o}\mathrm{b}\mathrm{t}$$(^{\backslash },1^{\backslash }$$\mathrm{t},\mathrm{h}\mathrm{e}$$\mathrm{a}\mathrm{c}\mathrm{C}\mathrm{S}\mathrm{l}\mathrm{u}\cdot \mathrm{r}\mathrm{o}\mathrm{t}\mathrm{m}\mathrm{d}\mathrm{e}\mathrm{d}$$\mathrm{s}_{1}$$3$$\mathrm{h}$$Q$$\mathrm{o}\mathrm{b}\mathrm{t}$$\mathrm{i}\mathrm{n}\mathrm{t}_{c}\mathrm{e}\mathrm{r}\mathrm{p}\mathrm{r}\mathrm{C}\mathrm{t},\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\iota$$p\mathrm{r}rallC^{\lrcorner}liZ\mathrm{f}t’,\mathit{0}7l$$7|,g$$\mathrm{m}\mathrm{o}\mathrm{l}\cdot \mathrm{e}\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{l}\cdot\subset \mathrm{t}\prime \mathrm{l}$$\iota_{\mathrm{y}}$$\mathrm{C}\mathrm{e}\mathrm{n}$$\mathrm{t}.\mathrm{h}\mathrm{e}_{\subset}\backslash 11\mathrm{f},\mathrm{h}\mathrm{o}1$$\mathrm{e}\mathrm{x}\mathrm{t},1^{\cdot}t\gamma \mathrm{c}\mathrm{t}$$\mathrm{a}_{01}\cdot \mathrm{i}\mathrm{t},\mathrm{h}_{\mathrm{l}}\mathrm{n}$$\mathrm{s}_{1^{)\mathrm{e}\mathrm{C}}}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{c}\mathrm{p}_{1}\cdot \mathrm{o}\mathrm{c}\mathrm{C}\mathrm{s}\mathrm{s}$$\subset\backslash \iota \mathrm{l}\mathrm{t}\downarrow \mathrm{h}\mathrm{o}\mathrm{r}[8]$$Q$. we will refine the idea of cycle filling as parallelizat,ion. We give a new
In thist,o t,he. As
of HDA by int,roducing new syst,em of notation called cubieal
int,rinsic
formalizat,ionofdefinition
gives aformalization of HDA as seen in [10. 3. 1]. oura collect,ion of. which isand a HDA is defined as a well-labeled cubical
we will int,roduce reachable
dimensions. Also. for applicat,ion t,o
of
t,he
, of
. we can.
. The advant,ages ofcomplexes
well-labeledstyle
explicitly contains
define t,he cycle filling map. and secondly.
t,races. Hence olll model is an extension of.

$\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{l}\mathrm{n}111_{\mathrm{t}}t\mathrm{t}’,\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{p}\mathrm{a}\mathrm{p}\mathrm{e}\backslash ,1$$Bar- 7l,\mathit{0}\dagger af,?.\mathrm{O}7|,$$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{n}\mathrm{p}\mathrm{a}1^{\cdot}\mathrm{t}^{\tau}\mathrm{d}$$n- \mathrm{c}11\mathrm{b}_{\mathrm{C}}\mathrm{S}$$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{n}\mathrm{p}1_{\mathrm{C}\mathrm{X}}(\mathcal{W}CC)$$\mathrm{C}1\iota 1)(\backslash \mathrm{s}$$\mathrm{v}\mathrm{a}\mathrm{r}\mathrm{i}_{0}1\iota \mathrm{s}$$1^{\cdot}\mathrm{O}\mathrm{l}\mathrm{l}\mathrm{g}\mathrm{h}\mathrm{l}\mathrm{y}$$\mathrm{p}_{1^{\backslash }\mathrm{O}\mathrm{C}(^{\mathrm{Y}}\mathrm{s}\mathrm{S}\mathrm{a}}.1\mathrm{g}\mathrm{e}\mathrm{b}1^{\cdot}\mathrm{a}$$\mathrm{c}\iota\iota \mathrm{b}\mathrm{i}_{\mathrm{C}_{C}\backslash 1}$$\mathcal{R}\mathcal{W}CC\mathrm{a}1^{\cdot}\mathrm{C}$$(\mathcal{R}\mathcal{W}CC)$$\mathcal{R}\mathcal{W}CC$$\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{m}c\gamma 1\mathrm{l}\mathrm{y}$$\backslash \mathrm{u}$$\mathrm{f}\mathrm{i}_{1}\cdot \mathrm{s}\mathrm{t}$($\mathrm{M}\mathrm{a}7_{\mathrm{Y}}111^{\cdot}\mathrm{k}\mathrm{i}\mathrm{C}\mathrm{W}\mathrm{i}\mathrm{C}\mathrm{Z}$$\mathrm{M}\mathrm{a}\mathrm{z}\iota 11^{\cdot}\mathrm{k}\mathrm{i}\mathrm{e}\mathrm{w}\mathrm{i}\mathrm{c}\mathrm{z}\mathrm{t},1t\backslash \mathrm{C}\mathrm{e}\mathrm{s}$$\cdot$. We will develop the formalizat,ion ofof t,his
We will now sket,ch t,he
next, section. We do not,and it,processa part,in)Rat,her.
viewedasdilncnsional
where
a
.
we work inbyt,hoset,oconst,
t,ransif,ion syst,
in CCS-likeprocess
we define. So in
)
)
in
lizcs
in t,he domain of RVVCC. Section 4
processt,he. The
of RWCC and defines the parallclizat,ion cdgorithIn with cycle filling
will be given in t,he final sect,ion.
$\mathcal{R}\mathcal{W}CC$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{g}\iota \mathrm{U}\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{p}\mathrm{a}_{\mathrm{P}^{\mathrm{t}^{\mathrm{Y}}1}}\cdot$$\mathrm{t}_{}\mathrm{h}\mathrm{e}$$\mathrm{i}_{\mathrm{C}11}1\mathrm{a}1^{\cdot}$$\mathrm{e}\mathrm{I}\mathrm{n}_{1^{)}}1_{0}\mathrm{y}$$\mathcal{R}\mathcal{W}CC$$\mathrm{s}\mathrm{c}\mathrm{t},\mathrm{t},\mathrm{i}\mathrm{n}\mathrm{g}$$1$$1\mathrm{a}\mathrm{n}\mathrm{g}_{11\mathrm{a}}\mathrm{g}\mathrm{e}$$\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}_{\mathrm{C}1}$$\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{C}\mathrm{s}\mathrm{S}\mathrm{c}\mathrm{s}\mathrm{a}\mathrm{l}\mathrm{e}$$\mathrm{s}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{l}C\backslash 1$$\mathrm{s}\mathrm{e}\mathrm{c}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}3$$\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{t}_{1^{\backslash },1},1^{)1(}\mathrm{Y}\mathrm{t},\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{r}\iota \mathrm{l}\mathrm{C}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{S}$$(^{\mathrm{Y}},\mathrm{m}\mathrm{s}$$\mathrm{i}\mathrm{o}\iota$$\mathrm{f}o1^{\cdot}\mathrm{m}\subset\backslash$$\mathrm{l}\mathrm{e}\mathrm{I}\mathrm{n}$$\mathrm{t},1\mathrm{l}\mathrm{c}\mathrm{p}_{c}’\iota 1\mathrm{a}11\mathrm{e}\mathrm{l}\mathrm{i}_{\mathrm{Z}}t\backslash \mathrm{t}_{1}\mathrm{i}_{01}1\iota$$1\mathrm{a}\mathrm{n}\mathrm{g}_{11}\mathrm{a}\mathrm{g}\mathrm{e}\mathrm{S}$$\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{g}\iota \mathrm{l}\mathrm{a}\mathrm{g}\mathrm{e}$$111^{\prime\iota}\subset 1^{)}$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{c}\mathrm{l}\iota \mathrm{l}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{r}(\backslash ,\mathrm{m}_{\mathrm{e}\backslash }1\mathrm{k}$2Reachable Well-labeled Cubical Complexes:, a HDA is a higher-dimensional space which is aat, t,heir )The cubes are gllled to each$\mathrm{c}o11_{\mathrm{C}\mathrm{C}}\mathrm{t},\mathrm{i}_{0}11$$\mathrm{I}\mathrm{n}\mathrm{t}_{1}1\mathrm{i}\mathrm{t},\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{l}\mathrm{y}$sions.

$\mathrm{f}\mathfrak{c})\mathrm{m}1_{t}\backslash 11\mathrm{y}$$\mathrm{o}\mathrm{t},\mathrm{h}\mathrm{e}\dot{\mathrm{l}}$desclil)ed by t,he bolmdary$\mathrm{f}$$0\mathrm{P}\mathrm{C}\mathrm{r}\mathrm{a}\mathrm{t}_{01\mathrm{S}},\cdot$.

$0\mathrm{l}\mathrm{m}\mathrm{d}\mathrm{a}\Gamma \mathrm{i}\mathrm{e}\mathrm{S}$$\mathcal{R}\mathcal{W}CC$of cubes of. so t,hat$\mathrm{v}_{t}\gamma 1^{\cdot}\mathrm{i}\mathrm{o}11\mathrm{s}\mathrm{d}\mathrm{i}\ln\{\backslash ,\mathrm{n}-$$\mathrm{t},\mathrm{h}\mathrm{c}\mathrm{s}\mathrm{h}_{t\backslash }\mathrm{p}\mathrm{t}$}of a HDA is

Tradit,ionally. t,he cubes are defined$(^{\backslash },\mathrm{x}\mathrm{f},\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{y}$.

. We will give here an
Namely, a cube is an element of a set satisfying someas a wcll-labeled cubianda
HDA
Bar-notatio
isof ctlbes with))
(VVCC). For applicat,ion
algebra. we will also define reachable
calcomplexes (RVVCC).
$\mathrm{i}11\mathrm{t}\mathrm{t}i1^{\cdot}\mathrm{n}_{C}\prime \mathrm{d}$$\mathrm{p}\mathrm{r}\mathrm{o}_{1)}\mathrm{C}1^{\cdot}\mathrm{t},\mathrm{i}\mathrm{e}\mathrm{s}$$\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t},\mathrm{i}\mathrm{o}_{1}1$$\mathrm{l}\mathrm{e}\mathrm{X}$$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{n}\mathrm{l}$$cub?,C\mathrm{r}\iota l$$\mathrm{f}\mathrm{o}\mathrm{l}\cdot \mathrm{l}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{i}7\mathrm{J}\mathrm{e}\mathrm{d}$$7|_{\text{ノ}}$$\mathrm{c}\iota \mathrm{l}\mathrm{b}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{l}$$\mathrm{t},o1$$\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{S}$

209
2.1

$n$

-cubes in cubical Bar-notation

Let $A$ be a denllmcrable set of symbols called labels. and let
be a monoid wit,
generated over $A$ . We will view the elements ofas words over $A$ and view 1 as the empty
word. We first, define pre -cubes in cubical Bar-notation over.
$\mathrm{A}1$$\mathrm{h}\iota \mathrm{m}\mathrm{i}\mathrm{t},$$1$$\mathcal{M}$$n$$\mathcal{M}$Definition 1: A pre ’-cube is adist,inct, elements. , $a_{n},\in A$ .
$a_{1}\ldots$

Bar-expression [a 1will be called t,he base $po?,nt$ .

$\mathrm{c}\iota \mathrm{l}\mathrm{b}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{l}$] wit,h$|a_{2}|\cdots|a_{\downarrow},$$?\mathit{1}^{f}$$\tau n$$\tau n\in \mathcal{M}$and71-cllbc\tau , $uf[a,]|a_{\mathit{2}}|\cdots|a_{n},]$ is a
. aspanned by 71
whose. the )
common ,art,ing point is . Next we willof pre -cubes. For
example. the boundary of the pre, which areis the collect,ioll of four line
also pre l-cllbes.
Bar-notation this collection is
as $\{?l’[a].ln[l$).
Also. the base point,of the-cllbe $wa[l)]$ . for example. is one ofend )of t,he-cube. Anot,her end point, is). This sit,llat,ion isby t,he wordint,he, will be
Figllre 1. whelc
.
Int,

,

$11\mathrm{i}\mathrm{t}_{J}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{l}\mathrm{y}$$\mathrm{c}\iota 1\mathrm{b}(^{\mathrm{Y}}$$\mathrm{p}_{1}\cdot \mathrm{c}$$\mathrm{s}\mathrm{t}$$1$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{l}$$\tau n$$‘ T1^{\backslash }\mathrm{C}\mathrm{S}a_{1}\ldots..a_{?\downarrow}$$2- \mathrm{c}11\mathrm{b}_{\mathrm{C}}m[a|l)]$$\mathrm{s}\mathrm{e}\mathrm{g}_{\mathrm{I}\mathrm{n}\mathrm{C}}\mathrm{n}\mathrm{t}_{\mathrm{S}}$$\mathrm{h}\mathrm{l}\mathrm{c}\iota \mathrm{l}\mathrm{b}\mathrm{i}\mathrm{C}\mathrm{a}\mathrm{l}$$\mathrm{d}(^{\backslash },\mathrm{S}\mathrm{C}1^{\cdot}\mathrm{i}\mathrm{b}$$?l$ ) $a$)$1$$1)1\mathrm{C}1$$\mathrm{F}\mathrm{i}\mathrm{g}_{11\mathrm{r}\mathrm{e}}1$,t,he bolmdary$\mathrm{o}\mathrm{P}^{\mathrm{c}\mathrm{r}\mathrm{a}}\mathrm{t},\mathrm{o}\mathrm{r}\mathrm{s}$for pre$\mathrm{t}l^{)}[](\tau r’\in \mathcal{M})$$d_{tl}^{0}’(.

$C_{0}$$d_{r\downarrow}$$d,,$\tau lf[a_{1}|\cdots|a_{n},])=j1\bigcup_{=}^{\prime 1}\{\mathrm{t}lf[\mathit{0}_{\mathrm{I}}.|\cdots \mathrm{v}^{j}\ldots|a,,]\}$

when

$77,$

$\geq 2$.

$‘\ldots\dot{}\ldots’\tau\sim$means omit, ,ing$\mathrm{e}\mathrm{x}_{1^{)}1}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{d}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{C}\mathrm{l}\cdot$$\mathrm{t}$$a_{i}$.

$n- \mathrm{C}11\mathrm{b}_{\mathrm{C}\mathrm{S}}$.

t,he elements of. Not,ice
is in t,he form
with A4 by the bijection. Then. t.he set, :)$?l- \mathrm{C}111$$C_{l\iota}$$\mathrm{i}\mathrm{l}1_{11\mathrm{S}}\mathrm{t}_{1\mathrm{a}},\cdot \mathrm{t},\mathrm{e}\mathrm{d}$: (pre) 2-cube $w[a|1)]$

Definition 2: Let,be t,he set, of preof. Hence we will identify
theorboundary operator
is t,he map$(^{\mathit{2}},tic$$\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}_{\iota},‘ \mathrm{i}$$1$$?l^{f}al$$\mathrm{t},\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{C}\mathrm{O}\mathrm{l}\mathrm{n}\mathrm{m}\mathrm{t}\mathrm{l}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{V}}\mathrm{i}\mathrm{t}\mathrm{y}_{\mathrm{C}\mathrm{o}\mathrm{n}}\mathrm{S}\mathrm{t},\Gamma \mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}$$\mathrm{d}_{\mathrm{t}^{\backslash }},\mathrm{f}\mathrm{i}\mathrm{n}..(\backslash$$].\eta l’ \mathit{0},[b].?(fl)[a]\}$$\mathrm{t}_{}\mathrm{h}\mathrm{c}$$\Gamma \mathrm{c}_{1^{)\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{e}\mathrm{n}}}\mathrm{t}_{}\mathrm{e}\mathrm{d}$Now we(,$1$$\mathrm{r}\mathrm{e}$$7l$$\mathrm{O}11\mathrm{n}\mathrm{d}_{\subset}\backslash 1\backslash \mathrm{y}_{0}\mathrm{p}\mathrm{e}1^{\cdot}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{s}$$\mathrm{t},\mathrm{h}\mathrm{a}\mathrm{t}_{}$$\mathrm{e}\mathrm{s}$$C_{\text{ノ}}0$$\tau n[]rightarrow\tau n$$=d_{r\iota}^{0}’\cup d_{7}^{1}$.

$C_{\downarrow},arrow C_{rl-\mathrm{l}}\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{l}\cdot \mathrm{e}$$d_{n}^{1}( \mathrm{t}l’[a1|\cdots|a_{1},])=.\bigcup_{\prime=1}’’\{\mathrm{t}l)aj[a_{1}|\cdots \mathrm{v}^{i}..\cdot..|\mathrm{r}J,,,]\}$$d_{1}^{0}(\tau n[a])=\{\tau n\}$and$d_{1}^{1}(\tau n[a])=\{\tau na\}$.

, t,he boundary of aalgebraic treat,ment, of cubes, it, is often convenient to).
as t,he formal slun of pre-cllbes
definit,ion.
boolean coefficients. Hence we also give$\mathrm{F}\mathrm{o}1$$\mathrm{p}_{1\mathrm{C}-}.\mathrm{c}111$$\mathrm{r}\mathrm{c}_{1^{)1}}\cdot \mathrm{c}\mathrm{s}\mathrm{c}\mathrm{n}\mathrm{t}$$\mathrm{c}$$\mathrm{W}\mathrm{i}\mathrm{t},\mathrm{h}$$\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{t},\mathrm{h}\mathrm{e}\mathrm{l}$Definition 3: Let
be t,he set, ofsluns oft,hevect,orwords. , isspace overgenerat,ed by )definition. we will ident,ify
with the vector space $V(M)$ ovelt,heoperator , is t,he linear map, :$S_{r\iota}$$o\mathrm{t},\mathrm{h}\mathrm{e}\mathrm{l}$$\mathrm{f}_{01}\cdot \mathrm{m}\mathrm{a}\mathrm{l}$$\mathrm{p}_{1}\cdot \mathrm{e}7\mathrm{t}-\mathrm{C}\iota 1\mathrm{t}J\mathrm{C}\mathrm{S}$$S_{\iota}$$\mathrm{Z}/(2)$$bo1l7|,d\mathrm{r}r.y$$\cdot$$\partial_{l},=\partial_{n}^{0}+\partial_{1}^{1}$$\partial_{\gamma}$$\partial_{1}^{0},(?\mathit{1}f[a]|\cdots|a,,])=\Sigma_{j}^{?}|[=1\tau l\prime a_{1}|\cdots \mathrm{v}^{j}\ldots|a_{71}]$

when $71\geq 2$ .
call

and
a j-boundary.

$\partial_{\mathrm{l}(}^{0}?l[a])=?\mathit{1}^{f}$$\partial_{l}^{j},(j=0,1)$$\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{l}\cdot \mathrm{e}$’$\partial^{1}$$\partial^{0}\partial^{1}=\partial^{1}\partial^{0}$.

$\partial_{1}^{\mathrm{I}}(\tau v[a])=\tau r)a$t,he dimension
In t,he cont,by omit,ting t,he sllffix . Not,ice
or 1).
and.
$(^{1},\mathrm{x}\mathrm{t},$$\mathrm{s}$$\mathrm{e}\mathrm{s}$$1$$S_{0}$$n$$d^{0}d^{1},=d^{1}d^{0}$’$n$, t,he$\mathrm{Z}/(2)\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{C}\mathrm{l}\cdot \mathrm{a}\mathrm{t},\mathrm{e}\mathrm{d}$$\mathcal{M}$.

$S_{1},arrow S_{-1},,\mathrm{w}\mathrm{h}_{\mathrm{C}1\mathrm{C}}$$\partial_{n}^{1}(?l’[a_{1}|\cdots|a_{1},])=\Sigma_{?}?’\tau r=1fa_{i[}\mathit{0},1|\cdots \mathrm{v}^{i}\ldots|a_{Yl}]$. We will often callis underst,$\mathrm{t}_{r}\mathrm{h}\mathrm{a}\mathrm{t}$with boolean coeflicient, . In)
. As in t,he previousby. Then.

$\mathrm{r}\mathrm{e}7\mathrm{t}-\mathrm{C}\mathrm{l}\mathrm{l}\mathrm{l}$$o\mathrm{o}\mathrm{d}$$\partial_{r\downarrow}$a total$bo$

undary and will

. we will somet,imes dellote as

opelators have the$d..\partial$.

$\partial^{()}$

and) $\mathrm{e}\mathrm{r}\mathrm{t}\mathfrak{l}\mathrm{y}\partial \mathit{0}=\partial^{j}\partial^{j}=0(.?=0$$1^{)1\mathrm{O}}.\iota$

210. example.
again
constraint.
An -cllbe is a pre -cllbc toget.her wit,$\partial(?l’[a|l)])=\taul’[b]+?l’[a]+\tau
va[l)]+?lfl)[a]$.
t,he ). The boundary is-cube $[a|b]$ invert,ices) $[a]$ must, meet at, the$wa[l)]$ and.
be a real cube,
If we wisht,heset,het,hel-cllbcs. Thus $\tau r’[a|l)]$ is aofmust becube and the
of
) .
)
)
This equational relation will be called theif and only if
real$?l$ )$\mathrm{r}\mathrm{e}2$$1$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{i}\mathrm{d}(^{\backslash }\prime 1$$\mathrm{F}_{01}$$\mathrm{h}_{Com}m\mathrm{t}\iota tat?.\cdot vi.ty$

$n$

$n$

$\mathrm{F}\mathrm{i}\mathrm{g}_{1}\mathrm{u}\cdot \mathrm{e}1$$\tau v[l)]$$w[a|1)]\mathrm{t},\mathit{0}$$\tau nl$$?\mathit{1}’[a],$$\mathrm{f}\mathrm{o}\iota \mathrm{l}\mathrm{r}$$\mathrm{b}\mathrm{o}\iota \mathrm{m}\mathrm{d}\mathrm{a}\Gamma \mathrm{i}\mathrm{e}\mathrm{S}$$\mathrm{V}\mathrm{C}^{1},1^{\cdot}\mathrm{t}\mathrm{i}\mathrm{C}\mathrm{e}\mathrm{S}$$\mathrm{p}_{1}\cdot \mathrm{e}$$\mathrm{C}11\mathrm{t}$$=?\mathit{1}^{f}l$$?\mathit{1}\prime al$$e$$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{l}\mathrm{n}\mathrm{l}\mathrm{l}\mathrm{t},\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{V}\mathrm{i}\mathrm{t},\mathrm{y}$$a$const,raint.

t,oget,her with t,he colnInllt,ativDefinition 4: An ?1-cube is a pre n-cllbc,.
that,,
foralbitr$<a_{1}\ldots..a,,$which mems
it,y
t,he
of
for all perinut,ationinsimply by $<a_{1}\ldots..a_{l},>$ . The. We will always denot,of cubes is defined by ) $\mathrm{t}(?l’[a1|a_{2}|\cdots|a_{n}])=.7l$ . The boundary
dimensionfor -cubes are t,he same as those for pre -cubes.
$\tau l’[\mathit{0}_{1},|a_{\mathit{2}}|\cdots|a_{tt}]$$‘\backslash 1\mathrm{y}\{i_{1}.i_{2\cdots\cdot\cdot k}\dot{i}\}\subset\{1.2\ldots..7\mathrm{t}\}$$>,,$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{t}\mathrm{l}’(\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{t},$$\mathcal{M}$$?l’ a_{i_{1}}a_{i}-,$$(\sigma(i|).\sigma(\dot{i}\underline{\cdot)}), \ldots.\sigma(ik))$$\cdots a_{j1\iota}=\tau\iota’ a_{\sigma(i_{\mathrm{I}}})a_{\sigma}(j_{\underline{)}}.)\ldots O_{\sigma},(?.k)$,$(i_{1,2}\dot{i}, \ldots , i_{k})$$\mathrm{e}<a_{\mathrm{l}}\ldots..a_{t},$$\mathrm{s}\mathrm{e}\mathrm{q}_{11\mathrm{c}\mathrm{n}\mathrm{C}(}\mathrm{Y}$$>_{1}$$d,\dot{?,}7$$\mathrm{f}\mathrm{i}_{1}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$$n$$()\mathrm{p}\mathrm{e}1^{\backslash }\mathrm{a}\mathrm{t},\mathrm{Q}\mathrm{r}\mathrm{s}$$7\iota$

Product and Decomposition of Cubes

2.2

Now we will define
and
prod$1lC,t$$\mathrm{t}_{}\mathrm{w}\mathrm{o}$basic const,$\mathrm{r}1\iota \mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$and)$n- \mathrm{c}111$$\mathrm{C}\mathrm{S}$. Ncllnely.

.

$\mathrm{r}l_{C}com\mathrm{P}^{o\mathit{8}}\dot{r}t?,\mathrm{O}7|’$

Definition 5:

Let,$\{a_{1}\ldots..a_{r},, \}\cap\{l)1\cdots.

$?l$ )$[a1| ...

and $u[b_{1}| . . . |l)_{t1}](7ll.7\mathrm{t}\geq 0)$ be, is. Then t,heir|a,,,]$.i)_{\mathit{7}},\}=\phi$with t,he$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{I}\mathrm{n}1\tau \mathrm{t}‘\backslash \mathrm{t},\mathrm{i}_{\mathrm{V}}\mathrm{i}\mathrm{t}\mathrm{y}$$\mathrm{C}11\mathrm{f}$)$\mathrm{C}\mathrm{S}$such t,hat,$\mathrm{p}_{\mathrm{l}\mathrm{o}\mathrm{d}_{11}}\mathrm{c}\mathrm{t}$$?(f[a_{1}|\cdots|_{\mathit{0}_{t1}},,]\star u[b1|\cdots|b_{1},]=?l^{f}?l,[_{\mathit{0}_{1}},|\cdot, .

$\mathrm{t}_{}\mathrm{o}\mathrm{g}_{\mathrm{C}}\mathrm{t}_{}\mathrm{h}\mathrm{C}1^{\cdot}$for$\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{l}\cdot\iota \mathrm{l}\mathrm{C}\mathrm{f},\mathrm{i}0\mathrm{n}\mathrm{o}\mathrm{p}\mathrm{C}\mathrm{l}\cdot \mathrm{a}\mathrm{t},\mathrm{o}\mathrm{r}\mathrm{s}$constl aint,: $<a_{1}\ldots$ . ,|a,,l|l)_{1}|\cdots|b_{\iota},]$$a_{t},,.b_{1}\ldots$

., ),
$l$

$,>_{11’ 1},$, is a non-comlntlt ativ
Notice t,hat, theNext,. We can view
we will define t,he decomposit,ion ).
. Also, eachof $C$ and it, })ofst,ruct,ure. This representat,ion is called cellular decomposition.

$(^{\tau}, 0_{\mathrm{P}^{(^{\backslash }1}},\cdot \mathrm{a}\mathrm{t},\mathrm{i}0\mathrm{n}\mathrm{f})\mathrm{e}\mathrm{C}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{S}\mathrm{e}?l^{)}?l,$$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{d}_{1}1\mathrm{c}\mathrm{t}$$\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{e}\mathrm{q}_{11\subset\backslash }1$$0\iota$

.

alld
an
, of

$?l?l\mathit{1}$$\mathrm{t},\mathrm{h}\mathrm{a}\mathrm{t}$are not, always$?- \mathrm{C}\mathfrak{j}1\mathrm{b}(^{\mathrm{Y}C}$$\mathrm{e}\dot{\mathrm{i}}_{(^{\urcorner}11},1\mathrm{c}\mathrm{n}\mathrm{t}$$\mathrm{O}\iota \mathrm{l}\mathrm{n}\mathrm{d}\mathrm{a}\mathrm{l}\mathrm{y}B=d(C)$$\mathrm{t}_{}\mathrm{h}\mathrm{e}\mathrm{i}11\mathrm{t}\mathrm{e}1^{\cdot}\mathrm{i}_{0}\mathrm{r}$$\mathrm{s}$$B\mathrm{h}‘\backslash \mathrm{s}\mathrm{t},\mathrm{h}\{\backslash$consist,ssimilarinduct,ively folan -cube $?lf[a_{1}|\cdots|a,]$ . we define t,he set,
Definition 6:$C|C\ind(C^{t})$for some $C^{t}\in B_{k+1}$ }.
. . { -cllbc
and.
1a. Als .
cellular decomposition by
Then we define
,end
t,he
set,
$dcco’
nl^{)}(s)=\{decomq)(c)|c\in
S\}$
.
map:
ally
of cubes we$\mathrm{F}\mathrm{o}1^{\cdot}$$\mathrm{s}B0\cdot B\iota\cdot\cdots.B,\iota$$7l$$o\mathrm{w}\mathrm{s}:B_{I1}=\{?lf[0_{1}|\cdots|a_{7l},]\}$$\mathrm{f}\mathrm{o}1^{\cdot}0\leq k<n$

The

$=$

$\lambda 8$($\mathrm{A}:$$deco7 \gamma ll^{)}(\mathrm{r}n[a1|\cdots|\mathit{0}_{1},,])=\bigcup_{k=0}^{1)}B\mathrm{x}\cdot$$\mathrm{t},\mathrm{h}\mathrm{c}$$S$$B_{k}$$\mathrm{c}\mathrm{x}\mathrm{t}$$\mathrm{n}\mathrm{a}\mathrm{t}_{\mathfrak{c}}\iota \mathrm{U}$is$\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{r}_{C}\urcorner \mathrm{c}\mathrm{t}\mathrm{C}\Gamma \mathrm{i}_{7,\mathrm{e}}\mathrm{d}$$\mathrm{c}\mathrm{e}\mathrm{l}1_{111\mathrm{a}1}\cdot \mathrm{d}\mathrm{e}\mathrm{C}\mathrm{o}\mathrm{m}_{1^{)0}}\mathrm{s}\mathrm{i}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$as follows.

Lemma 1 For a cube C. (i) $deco7np(d_{CCom},q)(C))=deco7?7,q)(C)$ . $(??)$ for ($D\in decom_{l(c}))$ if and only if.
for some$\iota rb_{\dot{\mathit{7}}}t_{7\tau}\iota ry$$D\in d^{\prime\downarrow}(C)$

Example 1:$B_{0}$$=$$B_{1}$$=$$B_{2}$$=$

cnbe $D$ .

$77_{\mathrm{J}}\geq 0$$\mathrm{r}l_{Cco}7np(\tau l)[a|b|c])=B_{0}\cup B_{1}\cup B_{\mathit{2}}\cup B_{3}$where$\{?l;[a|l)].8lf[a|tj].\mathrm{t}l’[l)|\subset j].?l’ c[a|b].\mathrm{t}l\prime l)[a|_{C]}.?l^{)\mathit{0}},[l)|c]\}$alld t,he equalit,ies between elements in$<a.b.c>_{1l},$ .

) $1$$\mathrm{f}\subset$$\mathit{0}$$B_{0}\subset\backslash \mathrm{n}\mathrm{d}B_{1}$are$\mathrm{d}11\mathrm{C}$.

to t,he$B_{3}=\{\tau l’[\mathit{0}|l)|ti]\}$$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{n}\mathrm{m}11\mathrm{t}\mathrm{a}\mathrm{t},\mathrm{i}_{\mathrm{V}}\mathrm{i}\mathrm{t},\mathrm{y}\mathrm{c}\mathrm{o}11\mathrm{f}\mathrm{i}\{_{\mathfrak{l}}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}$

,

211
2.3

Well-labeled Cubical Complexes

Now we define well-labeled ctlbical complexes.

Definition 7: Let $C$ be a set of cllbes with $1\in C$ andbe t,he set of -cubes in $C$ .
Then, a-labeled, F. Const) wherecomplex (VVCC) is the t,uple $S=$ (,$S_{<(>}$
is the vector space overgenerat,ed by. $S_{<(’>}$ will oft,en be lepresented by the ,rat,ified form. Namely,
whereis t,he vect,ort,hespace over
, will be
set $C_{n}=\{d_{CC\mathit{0}n}?,p(c)\in C|d?,??\mathrm{t}(C)=n\}$ .
generat,ed byalso denoted by Ba.sc $(s.n)$ .
$C_{0}(\subseteq C)$$cub?,c,\mathrm{r}xl$$\tau nell$$0$$S_{<\mathrm{C}’>}.\partial 0.\partial 1$$dec_{\sim}o7|\iota p(C)$$\mathrm{Z}/(2)$$\bullet$$\mathrm{s}\mathrm{t}$$S_{<C^{\mathrm{Y}}}>=\oplus?\iota\geq 0S^{l}\iota r<c>$$s_{<(}^{tl}’>$$\mathrm{Z}/(2)$$\partial^{0}.\partial^{1}$$\bullet$$\bullet$$\bullet$$F$:$C_{\gamma}$$S_{<C’>}arrow S_{<(^{\mathrm{v}}>}$

is a subset of$C_{0}$

are$\mathrm{t}_{l}\mathrm{h}(^{\backslash },$$j$-boundary operators.

.

Const is the collection of commut,ativityof t,he cubes int,heelement, in
t,ativity. The eqllat,ionalforConst and the following Right Extension Rule$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}_{1}\mathrm{S}$

$C$

and

$\mathrm{o}\mathrm{t},\mathrm{h}e,\mathrm{r}$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{t}_{1}\cdot \mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t},\mathrm{s}$$\mathrm{r}\mathrm{c}_{\subset 1}\mathrm{S}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$$s_{<(>^{\mathrm{i}_{\mathrm{S}}\backslash \mathrm{r}}},\mathrm{c}_{\subset}1\mathrm{i}\mathrm{e}\mathrm{d}$$\mathrm{s}$comInll-ollt, with$?\mathit{1}^{f}1=?l)2(?\mathit{1}^{f}|, \mathrm{t}l\prime 2\in C_{0})\Rightarrow?I\prime_{1}M=\tau l’ 2M(M\in A\mathrm{o}1^{\cdot}M=[a_{1}|\cdots|a_{1},].a_{i}\in A)$

and the reflexity, symmet,ry and tlansit.ivity rules.
Wc will$J^{)}\cdot q>_{a}\})$$\mathrm{b}_{1}\cdot \mathrm{i}\mathrm{e}\mathrm{f}\mathrm{l}\mathrm{y}$. Consider t,he
. $\{apq\}.\{<$
t,he(figure (a) below). We cannot define
space in which

explain well-labeledness’ of

wit,h $C=\{[a].

[l)], b[a].a\beta)|q]\}$$\mathcal{W}CC$$\mathcal{W}CC(s_{<c^{\mathrm{v}}>}.o^{0}.\partial^{1}$, t,he) $a=aq$labels ) and $aq$ denotes
point, because we cannot, 1
const,raint,. Howevcl. we can define a space which has the desired shapeby achanging the labels. Namely, the complex
const,raint,. Notice t,hat $<p.l$)is t,hewith the cllbe $a\lceil p|b$], but the constraint, $<a.b>$ is the addit,ional one onlyt,o link t,he point, ) , and $ab$ . The equat,ion ) $=ab$ andt,he) $=al\eta$) follow)) $=abp$ follows from the const,$<a.l$). but thet,he, ext,ension rlll .
$l$$\mathrm{t},\mathrm{h}e$$\mathrm{t},\mathrm{h}_{\mathrm{C}\mathrm{S}}\mathrm{a}\mathrm{I}\mathrm{n}\mathrm{C}$$a$$e\mathrm{p}_{\mathrm{l}\mathrm{e}}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{t}$$\mathrm{e}\mathrm{q}_{1\iota \mathrm{a}}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}|$$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{l}\mathrm{n}11\mathrm{t},\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{V}}\mathrm{i}\mathrm{t}\mathrm{y}$$(s_{<D>}, \partial 0.\partial 1.

$1)\mathrm{y}$$D=\{[a], [b].l)[a], a[p|l)]\}(\mathrm{f}\mathrm{i}\mathrm{g}\iota \mathrm{l}\mathrm{r}\mathrm{e}(\mathrm{f})))$\{apb\}.

\{<p.l, >_{1},.<a, l)>\})\mathrm{w}\mathrm{i}\mathrm{t}_{}\mathrm{h}$$>_{Cl}$$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{n}\mathrm{n}1\mathfrak{j}1\mathrm{t}_{1}\mathrm{a}\mathrm{t}_{}\mathrm{i}\mathrm{V}\mathrm{i}\dagger,\mathrm{y}$$\mathrm{a}\mathrm{C}\mathrm{C}\mathrm{o}\mathrm{l}\mathrm{n}\mathrm{P}^{\mathrm{a}\mathrm{n}\mathrm{i}}\mathrm{t}^{\backslash }\prime \mathrm{d}$$\mathrm{s}l$$l$$\mathit{0}$$\mathrm{c}o\mathrm{m}\mathrm{m}11\mathrm{t}_{\subset 1\mathrm{t}},,\mathrm{i}\mathrm{V}\mathrm{i}\mathrm{t},\mathrm{y}\mathrm{c}0\mathrm{n}\mathrm{S}\mathrm{t},\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t},\mathrm{s}$$a,$$\mathit{0},p1$$\mathrm{d}\mathrm{i}1(^{\backslash },\mathrm{c}\mathrm{t},1\mathrm{y}\mathrm{f}\mathrm{i}\cdot \mathrm{o}\mathrm{m}$$>\mathrm{a}\mathrm{n}\mathrm{d}$$1^{\cdot}\subset T\mathrm{i}\mathrm{n}\mathrm{t},$$\mathrm{c}\mathrm{q}_{11\mathrm{a}\mathrm{t}\mathrm{i}_{0}},\mathrm{n}l$$\Gamma \mathrm{J},l$$1^{\cdot}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}$$e$$1=\alpha?l_{2}(\alpha\in A)$ . is t,hat,
why we do not allow ’left extensiont,he colnmllt,at,ivit,yraint, is of local nature. Consider t,he $WCC$ in the following.

The$\mathrm{f}\mathrm{f}\mathrm{i}_{\mathrm{C}.?pf}\mathrm{I}=\tau n_{2}\Rightarrow\alpha \mathrm{t}l$$\mathrm{r}e,\mathrm{a}\mathrm{s}\mathrm{o}\mathrm{n}$)$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\dot{\mathrm{t}}$$\mathrm{f}\mathrm{i}\mathrm{g}\iota \mathrm{l}\mathrm{r}\mathrm{e}$We have $<\mathit{0}.b>$ because of t,he exist,ence of the. If we allow left,
obt,ain $<a.b>_{c},$ nalnely $cab=cba$ .
, this does not hold in this.
$2- \mathrm{c}11\mathrm{b}_{\mathrm{C}}[a|l)]$$\mathrm{b}_{11}\mathrm{t}$$\mathcal{W}CC$$\mathrm{e}\mathrm{x}\mathrm{t}$,ension. we212
Reachable Well-labeled Cubical Complexes

2.4. By reachable. we
Now we will define reachable well-labeled cllbical complexes, we can arrive at, any point in t,he space by a pat,from the distingllished point 1. Hence
we will first define the not,ion of pat,hs in cubical complcxes.
$(’\mathcal{R}WCC)$$1\mathrm{n}\mathrm{c}^{\backslash },\mathrm{a}\mathrm{n}$$\mathrm{h}$$\mathrm{t}_{}\mathrm{h}\mathrm{a}\mathrm{t}$Definition 8: Let $S=$ (element, fromwith$\partial^{0}(c_{1})=1$$C_{1}$$\mathrm{s}$$F$$S_{<(>},.\partial 0.\partial^{\mathrm{I}},$and, Const) be a $WCC.$

The11 a$\mathrm{s}\mathrm{e}^{\mathrm{Y}},\mathrm{q}_{11}\mathrm{e}\mathrm{n}\mathrm{c}(^{\mathrm{Y}},$$\partial^{1}(Ci_{?})=\partial^{0}(Cji+1)(i=1, \ldots , t-1)$

is called a path of), Const) is a
Definition 9: A RWCC $S=$ (such.
$?l)\in C_{0}$ . there is a pathwit,hoft,enin. A
will bedenoted
’
not,
)
by
where
other
are
important.
($<’>$$\mathcal{W}CC$$\oplus_{1\geq 0\mathrm{i}’>},S_{<(}7|.\partial^{0.\mathrm{l}}\partial.F$$S$$(c_{1}\ldots..c_{t})$$S_{<C’>}\mathrm{o}1^{\cdot}\oplus,,\geq 0S^{1}$$\partial^{1}(c,)=?\mathit{1})$of$(c_{\mathrm{l}}, c_{2}\ldots..c’)$$\mathrm{t},\mathrm{h}\mathrm{a}\mathrm{t}_{1}$$S$.

$\mathrm{f}\mathrm{o}1c\urcorner 1^{\cdot}\mathrm{f}$$\mathcal{R}\mathcal{W}CC$$\mathrm{i}\mathrm{t},\mathrm{r}\mathrm{a}\mathrm{r}\mathrm{y}$)$\mathrm{s}\mathrm{i}_{\ln_{1}}$$1\mathrm{y}$$\mathrm{a}\mathrm{l}\cdot \mathrm{t}\iota \mathrm{S}$$\mathrm{I}$

RWCC as Noninterleaving bansition System3

as RWCC has nice
. Namely, we can clearly llndel st,alld
bet,ween t,he general not,ion of HDA model andnoninterleaving semant,ics t,heoriest,he, defined int,ernally wit,.
inBecause. which are bllilding blocks of HDA.
cubical. we can
HDA model.
explicitly in.
constraints can be
as t,he )independence relat,ions for Hoaret,races
in t,he.
explicitly cont.ains ast,yle.
, theory.
commut,at,ivity const,raints describe t,he homot, py relat,ion which is aAlso.
central not,ion of HDA lnodcl. In t,his section, we show t,heandt,hose). Also. we definestylesilnilart,hat,in CCS-like process languages in t,he domain of.
the simplicity. we will
) $(c)=C$ in t,hc following.
a RVVCCis such that,

HDA$\mathrm{f}_{0}\mathrm{r}\mathrm{l}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{Z}\mathrm{C}\mathrm{d}$$\cdot$$1^{\cdot}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{c}1^{\cdot}\mathrm{t},\mathrm{i}_{\mathrm{C}_{\iota}\mathrm{S}}$$\mathrm{t},\mathrm{r}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}_{\subset}\prime \mathrm{t}1$$\mathcal{R}\mathcal{W}\dot{C}C$$\mathrm{c}\iota \mathrm{l}\mathrm{b}\mathrm{e}\mathrm{S}$$\mathrm{h}$$\mathrm{a}1^{\backslash }\mathrm{C}^{\backslash }$$\mathrm{d}(^{\tau}\mathrm{s}\mathrm{c}1^{\cdot}\mathrm{i}1)\mathrm{e}\mathrm{H}\mathrm{o}\mathrm{a}1^{\cdot}(\mathrm{Y}\mathrm{t}_{1},\cdot \mathrm{a}\mathrm{C}\mathrm{C}\mathrm{S}$$\mathrm{B}\mathrm{a}\mathrm{r}- \mathrm{n}\mathrm{o}\mathrm{t},a\mathrm{t},\mathrm{i}_{\mathrm{o}\mathrm{n}}$$01\mathrm{U}$$\iota \mathrm{m}\mathrm{d}\mathrm{c}\mathrm{r}\mathrm{S}\mathrm{t},\mathrm{O}o\mathrm{d}$$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}11\mathrm{t},\mathrm{a}\mathrm{t},\mathrm{i}_{\mathrm{V}}\mathrm{i}\mathrm{t},\mathrm{y}$$\mathrm{M}_{01\mathrm{O}\mathrm{o}\mathrm{v}}e1^{\cdot}$$\mathrm{t}_{}\mathrm{h}\mathrm{e}$$1^{\cdot}\mathrm{e}\mathrm{f}\mathrm{i}_{\mathrm{X}}\mathrm{C}\mathrm{d}$$1$$\mathrm{i}\mathrm{n}\mathrm{t}\alpha \mathrm{r}\mathrm{o}\mathrm{d}\mathrm{l}\mathrm{l}\mathrm{C}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{l}\cdot \mathrm{C}\mathrm{f}\mathrm{o}\mathrm{l}\backslash \mathrm{c}$$\mathrm{e}\mathrm{x}_{1)}1_{c\backslash }\mathrm{i}\mathrm{n}(^{\mathrm{Y}},\mathrm{d}$$\mathcal{R}wCc$$\mathrm{M}\mathrm{a}\mathrm{z}\mathrm{l}\mathrm{u}\cdot \mathrm{k}\mathrm{i}(,\backslash \mathrm{W}\mathrm{i}_{\mathrm{C}}\mathrm{z}$$\mathrm{t}_{\downarrow}\mathrm{h}\mathrm{c}$$\mathrm{t}_{\Gamma \mathrm{a}\mathrm{C}\{},\backslash$$\mathit{0}$$1\mathrm{c}\mathrm{l}\mathrm{a}\mathrm{t},\mathrm{i}_{0}\mathrm{n}\mathrm{w}\mathrm{i}\mathrm{t}_{!}\mathrm{h}\mathrm{H}\mathrm{o}\mathrm{a}1^{\cdot}\mathrm{C}\mathrm{t}_{1\mathrm{a}\mathrm{C}(_{\backslash }^{\backslash }},,\mathrm{S}$$\mathrm{M}\mathrm{a}\mathrm{z}\mathrm{l}\mathrm{U}\mathrm{k}\mathrm{i}\mathrm{e}\mathrm{w}\mathrm{i}_{\mathrm{C}\mathrm{z}}$$\mathrm{t}_{1}\cdot \mathrm{a}\mathrm{c}\mathrm{e}\mathrm{t},\mathrm{h}_{\mathrm{C}\mathrm{O}1}\cdot \mathrm{y}$$\mathrm{t}_{J}\mathrm{y}\mathrm{p}\mathrm{i}\mathrm{c}\epsilon\backslash 11$$\prime \mathcal{R}\mathcal{W}CC$$\Gamma \mathrm{o}\mathrm{c}\mathrm{C}\mathrm{S}\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{t},\Gamma 1\mathrm{l}\mathrm{c}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{S}$$\mathrm{t}\prime 0$$\mathrm{F}\mathrm{o}1$$\subset \mathrm{l}\mathrm{t}\mathrm{s}\mathrm{s}\mathrm{l}\mathrm{u}\mathrm{n}\mathrm{C}$$S_{<(^{}>}$

Hoare

3.1

Wc will )$deco\mathit{7}’ ll$$\mathrm{n}_{\mathrm{a}}\mathrm{C}\mathrm{e}\mathrm{s}$$\mathrm{f}$$1^{\cdot}\mathrm{i}\mathrm{e}\mathrm{f}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{i}_{\mathrm{C}\mathrm{w}}$, Homotopy and Mazurkiewicz Tracest,hc idca of HDA as a$\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}1^{\cdot}1_{\mathrm{C}t}\gamma \mathrm{v}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t},1^{\cdot}\mathrm{a}\mathrm{n}\mathrm{S}\mathrm{i}\mathrm{t}\mathrm{i}_{0}\mathrm{n}\mathrm{s}\mathrm{y}\mathrm{s}\mathrm{t},e,\mathrm{l}\mathrm{n}$. Now we will

ansit,ionin. This can besyst,cm when $\tau n=1$ . We findpat,hs $p1=([0], a[b])$ and $p_{2}=(\iota l)],$.
t,hc
trace of action followed by act,ion ). Also.
of act,ioll ) followcd )Thlls t,hc pat,hs in RWCC lepres( Hoarc t,raccs. Then. what, does t,he 2-clllye $?n[a|l$) lncan?
t,o cach.
pat,hs )call bet,hat,
t,hc( . We
)
this
pat,
and
homotopic. According t,o t,hc
t,he highel -dimcnsional , ,at,c. or high)of HDA lnod( . t,hc.
t,hc
ill whichand ) Inayin parallel. Hencc,
is )bet,wecn, ofrelation bctween paths catlscd by thc
them. We
consider higher-dimcnsional homot,of higher dimcnsional. ) , t,het$o olllfollowinghomotopy.
$\mathrm{r}\mathrm{e}\mathrm{c}\dot{\mathrm{o}}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{d}e,1$t,he$2_{-\mathrm{C}\iota}1\mathrm{b}\mathrm{e}?l[a, |1,]$$11\mathrm{n}\mathrm{d}\mathrm{e}1^{\cdot}\mathrm{S}\mathrm{t}\mathrm{o}\mathrm{o}\mathrm{d}\subset 1_{\backslash }\mathrm{S}$$\mathrm{F}\mathrm{i}\mathrm{g}111^{\cdot}(^{\backslash 1},$a nonint,$\mathrm{t}‘ \mathrm{w}\mathrm{o}$$l)[\mathit{0}])$

$l$

$a$

$\mathrm{e}r1(^{\mathrm{Y}}.\tau \mathrm{t}r\mathrm{v}\mathrm{i}1\mathrm{t}_{1},\cdot$$a.$$p_{1}\mathrm{r}\mathrm{e}\mathrm{p}_{1}\cdot \mathrm{e}\mathrm{S}\mathrm{e}\mathrm{n}\mathrm{t},\mathrm{S}\mathrm{t}_{1}\mathrm{h}\mathrm{e}$$l$$\mathrm{t}_{1\mathrm{a}},\cdot \mathrm{c}\mathrm{C}$$l^{)}2\mathrm{r}\mathrm{e}\mathrm{p}r\mathrm{C}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{f}_{\backslash },\mathrm{s}$$\iota$$\mathrm{y}(\eta \mathrm{C}\mathrm{t}.\mathrm{i}\mathrm{o}\mathrm{n}$$11\mathrm{t}$,$]$$\mathrm{t},\mathrm{h}\mathrm{e}^{\mathrm{Y}}$$\mathrm{G}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{n}\mathrm{e}\mathrm{t},\mathrm{r}\mathrm{i}_{\mathrm{C}}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{y}$$2-(11\iota)$$l$$\mathrm{l}\subset\backslash \mathrm{n}\mathrm{d}p\underline{\cdot)}$,$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{l}\mathrm{l}\mathrm{O}\iota \mathrm{l}\mathrm{s}\mathrm{l}\mathrm{y}\mathrm{t},1^{\cdot}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{l}\mathrm{a}\mathrm{t},\mathrm{C}\mathrm{d}$$\mathrm{o}\mathrm{t}_{}\mathrm{h}_{\mathrm{C}}\mathrm{r}\mathrm{t},\mathrm{h}_{\mathrm{l}\mathrm{O}11}\mathrm{g}\mathrm{h}\mathrm{t},\mathrm{h}\mathrm{c}$$\mathrm{s}\mathrm{i}\mathrm{t}_{11\mathrm{a}}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{h}_{\backslash }\mathrm{s}_{l}$$\backslash ,$$\mathrm{L}\mathrm{S}_{C}\backslash \mathrm{y}$$\backslash ,1$$\mathrm{t},\mathrm{h}(^{\backslash },\mathrm{O}1^{\cdot}\mathrm{y}$$l^{)}\mathit{2}\mathrm{a}\mathrm{l}\mathrm{e}$$1$$2- \mathrm{C}11\iota$$\cdot$$\mathrm{t}\mathrm{h}\mathrm{e}_{\subset}\urcorner \mathrm{C}\mathrm{t},\mathrm{i}_{\mathrm{o}\mathrm{n}\mathrm{s}a}$$|$$(^{\backslash },1-\mathrm{d}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}_{0}\mathrm{n}C\backslash 1\mathrm{t}_{1\mathrm{a}\mathrm{n}\mathrm{s}},\cdot.\mathrm{i}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{s}\mathrm{t}$$\mathrm{C}\mathrm{m}\mathrm{C}t\backslash \mathrm{n}\iota \mathrm{S}$$\mathrm{r}\iota\ln$$1^{\cdot}\mathrm{C}\mathrm{S}()11\mathrm{t},\mathrm{e}\mathrm{d}\mathrm{f})\mathrm{y}$$\mathrm{t}_{1\mathrm{t}\mathrm{l}\mathrm{e}\mathrm{C}\mathrm{O}},\cdot \mathrm{n}\mathrm{C}\iota \mathrm{u}\cdot 1^{\cdot}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{y}$$\mathrm{r}\mathrm{t}^{\backslash },1$$\mathrm{h}\mathrm{o}\mathrm{I}\mathrm{n}\mathrm{o}\mathrm{t},\mathrm{o}\mathrm{p}\mathrm{y}$$\mathrm{e}\mathrm{x}\mathrm{i}_{\mathrm{S}}\mathrm{t}.’\mathrm{C}\mathrm{n}\mathrm{c}\mathrm{C}\tau$$\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{e}1-\dim(^{\backslash },\mathrm{I}\mathrm{l}\mathrm{s}\mathrm{i}_{\mathrm{o}\mathrm{n}}\mathrm{a}\mathrm{l}\mathrm{S}\iota)’C\iota \mathrm{c}(\backslash ,\mathrm{s}$$\mathrm{c}\mathrm{a}\mathrm{n}_{\subset}’\iota 1_{\mathrm{S}}0$$\mathrm{p}_{\subset \mathrm{t}\mathrm{t}}’,\mathrm{h}\backslash \mathrm{s}$$1$$\mathrm{t}\mathrm{l}\mathrm{t}$$0_{1^{)}\mathrm{y}}$$\mathrm{s}\iota 1\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{c}\mathrm{C}\mathrm{s}$$1_{\mathrm{o}\mathrm{W}}\mathrm{c}\mathrm{r}-\mathrm{d}\mathrm{i}\mathrm{m}\mathrm{e}.\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}1$$\mathrm{d}\mathrm{i}_{\mathrm{S}}\mathrm{C}\iota!^{\mathrm{S}\mathrm{S}\mathrm{i}\mathrm{n}}\mathrm{O}$))Definition 10: Two pat,in a RWCC,-. . ,
exist,s .
bc arljacent.
if $71=’$ .
and
1. $p_{k}=q_{k}$ for all $1\leq k<\dot{i}$ and $i+1<k\leq n$
2. $l^{)}i+p_{i+\mathrm{l}}+q_{j}+q_{j+1}=\partial(c)$ for some.
relat,ion on thc pat,hs cont,aining
Homotopy.
$\mathrm{h}\mathrm{s}p=(l)_{\mathrm{l},\psi_{2}}$$\mathrm{s}_{t}^{\Gamma}\mathrm{t}\mathrm{i}\mathrm{d}\mathrm{t},\mathit{0}$$p\approx q,\cdot$$l^{)},,$$\mathrm{c}\backslash \mathrm{n}\mathrm{d}q=(q_{1}, q_{2}, \ldots qr|)$$\partial^{1}(p_{rt[]})=\partial^{1}(q_{l},)$$\mathrm{t},\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{C}$$i$$1\leq\dot{i}<n\mathrm{s}\iota \mathrm{l}\mathrm{c}\mathrm{h}\mathrm{t}_{\Gamma}\mathrm{h}\mathrm{a}\mathrm{t}$$c\in C\underline{\cdot)}$$\mathrm{i}_{\iota}\mathrm{s}\mathrm{t}\mathfrak{l}\mathrm{h}\mathrm{e}\mathrm{S}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\{\backslash ,\mathrm{S}\mathrm{t},$$\mathrm{e}\mathrm{q}11\mathrm{i}_{\mathrm{V}}\mathrm{a}\mathrm{l}\mathrm{C}\mathrm{n}\mathrm{C}\mathrm{C}$$S_{<C^{\nu}>}\mathrm{a}\mathrm{l}\cdot \mathrm{e}$$\mathrm{a}\mathrm{d}.|\mathrm{a}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{y}$213
Now we will consider Hoare traces in. Consider a RWCC
. We will callofstate labels. By definition we know that there is a one to one correspondence bet,ween
stateand pat,hs in $S_{<(>},$ . Hence Hoare traces are
represent,ed by t,he lst,atelabels in a RVVCC. Moreover. a comInlltativity constraint of RWCC is an explicit, description ofhomotopy relation. Namely, we have the llowing.
$\mathcal{R}WCC$$S_{<(^{\gamma}>}$$\mathrm{t},\mathrm{h}\mathrm{e}(^{\backslash 1_{\mathrm{C}\mathrm{I}\mathrm{n}\mathrm{C}\mathrm{n}\mathrm{t}}},,\mathrm{s}$$C_{0}\mathrm{t},\mathrm{h}\mathrm{e}$$1\mathrm{a}\mathrm{b}_{\mathrm{C}^{\backslash }},1\mathrm{S}$$\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{f}\iota 11\mathrm{l}\mathrm{y}$$\mathrm{f}o$Lemma 2 Let
iff the state$l^{)}1$and$labeL_{9}i\iota re$

Now we recall t,hebe paths
a RWCC correspo
to some state labels. The.
equal $w?,th$ the commutativity constrai $7l,ts$ of cubes.
$\dot{?_{l}}n$$p_{2}$$\mathrm{M}\mathrm{a}\mathrm{Z}11\mathrm{r}\mathrm{k}\mathrm{i}_{\mathrm{C}\mathrm{w}}\mathrm{i}\mathrm{C}\mathrm{z}$$7|,di_{7},7’.q$$7|,$$p\mathrm{l}\approx p_{2}$t,races.

Definition 11: [11] A $Maznrk?.ew?.cZ$ trace language collsists of $(M, L, I)$ whereis a set,,
is a symmetric, irreflexive
called t,he
, and $M$ is a
, ofnonempty
sllch thatprefix closed:all.
-closed: $sal$) $t\in M\ aIb\Rightarrow.9l$) $at\in M$ for all .9. $\dagger\in L^{*}.a.b\in L$ .
$b\in L$ .
coherent: sa\in M&sb\in M&aIb\Rightarrow sab\in M for allt,o be, equivalence relat,ion sllch that, $.9al$)
definesbat if $aIl$) for$sal)t.s\mathrm{I})at\in M$ .
($Maznrk?,eu$
)
$s\in
M$
,
an
,
Call
class
for
a
trace.
$L$$I\subseteq L\cross L$.
.

$1^{\cdot}\mathrm{c}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$i7l,d(J,peCle7l,ce1e,\mathrm{l}\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{s}\mathrm{u}1)_{\iota}\mathrm{S}\mathrm{c}\mathrm{t}$$\mathrm{s}\mathrm{t},\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}_{\mathrm{S}L^{*}}$$.9a\in M\Rightarrow.9\in M\mathrm{f}\mathrm{o}1^{\backslash }$$.\mathrm{s}\in L^{*}.a\in L$$I$$\bullet$$.9\in L^{\mathrm{x}}.a,$$\mathrm{F}\mathrm{o}1^{\cdot}s.t\in M$$\mathrm{t}_{arrow}\mathrm{h}e\mathrm{s}\ln C\backslash 11_{\mathrm{C}\mathrm{s}\mathrm{t}}$$\wedge\vee$$\mathrm{e}\mathrm{q}_{1}1\mathrm{i}_{\mathrm{V}}\mathrm{a}1$$t\wedge\vee$$\{.9\}_{\wedge}\vee$$\mathrm{Y},\mathrm{n}\mathrm{c}\mathrm{e}$$\prime cZ$

In t,heconcurrency islanguage.
by t,he independencet,hewhich means
commut,ativity of the action labels in Hoare. Hencecommut,at,ivity
is an independence
and prefixed closedness of
Hoaret,race)is assllred in. A
is an equivalence class of avia homot,opy
constraint,. namely a constraint,. If a RWCC does not cont,ain a redundant,$<a,$. for example. sllch that, $?lfa1$)
or. t,hen we know that coherency is assured.
Not,ice t,hat the independence relat,ion $aIb$ should be of local. Namely. if
actions)
and occur Inole t,han once in a wholeand ) lnay
independent,ly in solne, t,hcy may depend on each other in, explicitly 1
part,. The localit, isconst,raint,s do not,inabove t,race. On t,he other hand.
relat,ion but havepecifyas in $<a.b>_{tl}.$ . This )canof t,he act,ions and ). This enriched struct,of colnmlltat,ivit,y const,raint,st,race langllage.
solve t,he locality problem in t,he original$\mathrm{M}\mathrm{a}7\mathrm{c}\mathrm{t}\mathrm{u}\cdot \mathrm{k}\mathrm{i}6\mathrm{w}\mathrm{i}\mathrm{C}\mathrm{Z}\mathrm{t}\mathrm{l}\cdot \mathrm{a}\mathrm{C}e$$\mathrm{t},r11\mathrm{e}$$\mathrm{r}\mathrm{c}\mathrm{p}_{1\mathrm{C}\mathrm{S}}.\mathrm{c}\mathrm{n}\mathrm{t}.e\mathrm{d}$$1^{\cdot}(^{\backslash 1\mathrm{t}\mathrm{i}},’ \mathrm{a}\mathrm{o}\mathrm{n}$$\mathrm{t}_{}1\mathrm{a}\mathrm{C}\mathrm{e}\mathrm{S}(\mathrm{I}-(\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{c}\mathrm{d}\mathrm{n}e\mathrm{S}\dot{\mathrm{s}})$$\mathrm{c}o\mathrm{n}\mathrm{S}\mathrm{t}_{1\epsilon\backslash }\mathrm{i}\mathrm{n}\mathrm{t}$$1^{\cdot}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{O}\mathrm{l}\mathrm{U}$$\mathcal{R}WCC$$\mathrm{t}_{1\mathrm{a}\mathrm{C}\mathrm{C}_{\iota}},\cdot \mathrm{s}$$\mathrm{t},\mathrm{h}\mathrm{c}$$\mathrm{M}\mathrm{a}7_{I}\iota 11^{\cdot}\mathrm{k}\mathrm{i}\mathrm{C}\mathrm{w}\mathrm{i}_{\mathrm{C}}\mathrm{z}$$\mathrm{a}\mathrm{t},\mathrm{h}$$1$$1^{\cdot}\mathrm{e}\mathrm{l}\mathrm{a}\dagger,\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}11\mathrm{t}_{0}\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}\mathrm{y}$$l)>_{\mathrm{I}l},$$\tau nba\not\in C_{0}$$\not\in C_{0}$$\mathrm{n}\mathrm{a}\mathrm{t},11\Gamma \mathrm{c}$$b$$1\mathrm{l}\mathrm{t},\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}.$$\mathrm{c}o\mathrm{I}\mathrm{n}\iota$

$a$

$|$

$a$

$\mathrm{r}\mathrm{l}\mathrm{m}$$\mathrm{n}\dot{\mathrm{o}}\mathrm{t}$$o\mathrm{t},\mathrm{h}\mathrm{e}\mathrm{l}$$\mathrm{p}\mathrm{a}\mathrm{l}\mathrm{t}_{}\iota)11\mathrm{t}$$\mathrm{t}_{1}\mathrm{h}\mathrm{e}$$\mathrm{e}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{e}\mathrm{n}\mathrm{t}e,\mathrm{d}$$\mathrm{y}$$\mathrm{t},\mathrm{h}e$$1\mathrm{a}\mathrm{n}\mathrm{g}_{1}1\mathrm{a}\mathrm{g}\mathrm{e}$$\mathrm{s}_{\mathrm{t}}$$0\iota 1\mathrm{r}\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}\mathrm{u}\mathrm{t},\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{V}\mathrm{i}\mathrm{t}\mathrm{y}$$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{n}\ln\iota 1\mathrm{t},\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}_{}\mathrm{y}$$\mathrm{p}_{1}\cdot \mathrm{e}\mathrm{f}\mathrm{i}\mathrm{x}$)$\mathrm{m}_{c}\prime \mathrm{t}1^{\cdot}(\backslash ,1\mathrm{y}$$1\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{X}$$\mathrm{r}(^{\tau},\iota)1^{\cdot}\mathrm{C}\mathrm{S}\mathrm{c}\mathrm{n}\mathrm{t}\downarrow \mathrm{t}_{1}\mathrm{h}\mathrm{e}$

$1$

$l$

$a$

$\mathrm{c}_{\subset}\urcorner 11\mathrm{s}_{C}\backslash 1\mathrm{i}\mathrm{t},\mathrm{y}$$\mathrm{t}l$$\mathrm{w}\mathrm{o}\iota 1\mathrm{l}\mathrm{d}$$111\mathrm{C}$$\mathrm{M}\mathrm{a}7_{}11\mathrm{r}\mathrm{k}\mathrm{i}e\mathrm{W}\mathrm{i}\mathrm{C}\mathrm{Z}$3.2

CCS-like Process Constructors of$\mathcal{R}\mathcal{W}CC$

We will define CCS-likecesses indomain of. The
will bewit,
definedbasic operations.
. (synchronization) and Rest.
)
, we will assllme t,hat all the commut,ativity const,raint, are thoseIn t,hiswit,h). In order
describe synchronous. we will et, $A$ as follows. Let
where is a denllmcral)le\, set of symbols called labels.
t,he set oft,hat-labelsall. We will lmdeTst,and t,hat, t,he labeledt,heismacro of the. Namely.
$\mathcal{R}WCC$,$\mathrm{t},\mathrm{h}(^{\backslash }$$\mathrm{p}\mathrm{r}o$$\mathrm{h}\mathrm{t},\mathrm{h}_{1}\cdot ee$$\mathrm{S}\mathrm{l}\mathrm{l}\mathrm{l}$$\mathrm{p}_{\mathrm{l}\mathrm{O}\mathrm{C}}\mathrm{e}\mathrm{S}\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}_{11}\iota 1\mathrm{C}\mathrm{t},\mathrm{O}\Gamma \mathrm{s}$$\ominus$$\star(\mathrm{P}\mathrm{l}\cdot \mathrm{o}\mathrm{d}\tau \mathrm{l}\mathrm{C}\mathrm{t})$$(\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{t}_{1\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}},\cdot \mathrm{c},11)$$\mathrm{s}\mathrm{e}\mathrm{c}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$,$\mathrm{c}\iota \mathrm{s},\mathrm{s}\mathrm{o}\mathrm{c}\mathrm{i}\mathrm{a}\mathrm{t}(^{\backslash \mathrm{d}}$$\backslash \mathrm{s}$$\mathrm{C}11\iota$$\mathrm{t},\mathit{0}$$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{n}\mathrm{m}11\mathrm{n}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{t},\mathrm{i}_{0\mathrm{n}}$$\mathrm{e}_{\mathrm{c}}\mathrm{s}$$\mathrm{s}_{\iota}$$A=\mathcal{L}\cup\overline{\mathcal{L}}\cup\{\tau_{r\iota}|a\in \mathcal{L}\}$$\mathcal{L}$$\overline{\mathcal{L}}=\{\overline{o}|a\in \mathcal{L}\}$$\overline{\overline{a}}=a$$\mathrm{s}\iota \mathrm{l}\mathrm{c}\mathrm{h}$$\mathrm{i}_{\iota}\mathrm{s}$$\mathrm{c}\mathrm{o}$$a\in \mathcal{L}\cup\overline{\mathcal{L}}$$\mathrm{f}\mathrm{o}1^{\cdot}$$\mathrm{w}\mathrm{o}\mathrm{l}\cdot \mathrm{d}a\overline{a}$$\tau- \mathrm{a}\mathrm{c}\mathrm{t}\mathrm{J}\mathrm{i}\mathrm{o}\mathrm{n}\mathcal{T}_{a}$Definition 12: Let, $S_{1}=$ (RWCCs. Then t,heir product,,$\tau_{ll}=\mathit{0},\overline{a.}$$S_{<(_{1>}^{\tau}},$ $\partial^{0}.o^{1}.F_{1}$$S_{1}\star S_{2}$, is (. Const 1) and($s_{<C_{\mathrm{I}}\star},$$>.\partial^{0},$$\partial^{1},$$S_{arrow)}.=(s<c’-,>.o^{0}.o^{1}.F\underline{.)}.C_{on}.9t.2)$$F$$Cj\in C_{i}(i=1.2)\},$ $F=F_{1}\star F_{2}.=\{u?l’|u\in F_{1,?lf}\in F_{2}.\}$

commut,ativity const,raints for the cllbes in$C_{1}\star C_{\mathit{2}}$.

, Const) wherebe$C_{1}\star c_{2}=\{c_{1}\star \mathrm{r}i\underline{\cdot)}|$and Const is t,he collection of t,he214)define t,he fimction
Before we define t,he synchronization,
is obtained from} as follows: If t,hereA.
on finite sets of) and)t,hen replace ) by
if
(if
is a pair ) and )$j(\dot{i}<j)$ sllch that )new.
such pairs in. Carry out the same procedure forby scal.ching the lab . -label pairs in every cube fromlabels fromcubeswith the fimct,ion .
$\ominus.\mathrm{w}\mathrm{e}\sim$$\varphi(\{|_{)_{1}}\ldots..l)_{?\downarrow}\})=\{C\mathrm{I}\cdots.

.C_{m}\}$$\mathrm{m}_{c}\backslash _{1}$$\{c_{1},$$e,1\mathrm{e}\mathrm{m}(\backslash ,\mathrm{n}\mathrm{t}\mathrm{s}\mathrm{f}\mathrm{i}\cdot \mathrm{o}\mathrm{m}$$\ldots$

$i$

$i$

$e1$

$l)_{j}\in\overline{\mathcal{L}}$$01\tau_{\overline{(_{)}j}}$$\{l)1, \cdots.b,\}\}$$\{\tau_{C1}|a\in \mathcal{L}\}$$\mathrm{w}\mathrm{i}\mathrm{t}_{1}\mathrm{h}$$($$\tau_{b_{i}}$$\subset \mathrm{T}\mathrm{I}1\yen$$1^{\cdot}\mathrm{e}\mathrm{m}0\mathrm{V}\mathrm{e}l)j$$\ldots,$$b_{j}\in \mathcal{L}$$|$$=b_{j}$$l_{i}^{-}$

$|$

$|$

$l)_{l},$$\{b_{1},$$c_{m}\}$$\ominus(s)\mathrm{g}\mathrm{C}\mathrm{l}\mathrm{l}\mathrm{e}\Gamma \mathrm{a}\mathrm{t}\mathrm{C}\mathrm{s}$$S$$\mathrm{c}\mathrm{o}$$\varphi$

Definition 13: Let $S=$ (of $S,$ $\ominus(S)=$ ($\oplus_{7’\geq 0}s_{<}^{n}o^{0}.o^{1}c’>\cdot$$\oplus_{\iota\geq 0D>},s_{<}^{r}\iota.\partial^{0},$$o^{1},$, F. Const) be a RVVCC. Then t,he$synch\prime ro7|,i,7_{\vee}at?\prime on$$F’$ Const),
is the $\mathcal{R}WCC$ such t,hat $F’=F\cap deco7$)$p(D)$ and$D=$deconlp $(\Phi(c))$$\cup$$\mathrm{r}\cdot\in C$$(lj\mathrm{p}\prime 1(Ci)\geq 2$

where
if
if

$\mathrm{t}l’[|)]|\cdots|b_{ln}]$$\Phi(?\iota’[a1|\cdots|a_{\downarrow},])=\{$

Example 2: Let $S=$ (1$s_{<C^{\gamma}>}.o^{0}.\partial 1$$\varphi(\{a_{1}\ldots , .

. F. Const)

Next we define the.

$(\{[\tau]c|\cdot[a\overline{a}\tau a|b]\})$$1^{\cdot}\mathrm{e}\mathrm{s}\mathrm{t}_{T}\mathrm{i}\mathrm{c}\cdot \mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$witha. Then. $\Theta(S)=$ (, , ..

l)_{\}},,\}\neq\{a_{1},\ldots..a_{t}, \}$$C=\{[a|\overline{a}]_{:}a\overline{a}[a|\overline{o}.

$\mathcal{R}\mathcal{W}CC$$\mathrm{t})\mathrm{e}$$F=\{a\overline{a}a\overline{\mathit{0}}_{b\}},\mathrm{c}\backslash \mathrm{n}\mathrm{d}co7\mathrm{t}st=\{<a.\overline{a}>, <a,\overline{a}.l)>_{t\ell\overline{cl}}\}$

a RWCC wit, $\mathrm{h}D=dCCO7\gamma ll$ )a_{t\downarrow}\})=\{l)_{1}.

$\varphi(\{a_{1}\ldots..a,’\})=\{a_{1}\ldots..\mathit{0},,,\}$$S_{<D>}.\partial^{0}.\partial|.F’$||)]\}$.

. Const) is

and $F^{l}=F$ .

operation. $Re.9t(S.L)$ relnoves all t,he$\mathrm{c}\mathrm{t}\mathrm{l}\mathrm{l}$)$\mathrm{e}.\mathrm{s}$involving t,he lab$e1_{}\mathrm{s}$$\mathrm{f}_{1}\cdot \mathrm{o}\mathrm{m}L\cup\overline{L}$. F. Const) be a RVVCC and let, be a finit, . subset,
Definition 14: Let, $S=$ (. Const) is a RWCC wit,of . Then t,he restrictio , of S. $Re.9t(S.L)=$ ($F’=F\cap d_{CiC\mathit{0}l}p(D)$ and$L$$\oplus?\iota\geq 0<\mathrm{r}’>’\partial^{1}S^{\prime\iota}o^{0},$$(^{\tau}$$\partial^{1}.$$\oplus_{l\geq l)},0^{S}<>.F’\prime\prime o^{0},$$7|$$\mathcal{L}${if$\mathrm{h}$$\alpha\in L\cup\overline{L}\mathrm{O}\mathrm{C}\mathrm{c}\mathrm{l}\mathrm{u}\backslash \mathrm{s}$$1,. \cdot\cdot\prime 1\cap(L\bigcup_{\mathrm{C}\mathrm{S}0O}\overline{L}).=\phi.\mathrm{a}\mathrm{n}\mathrm{d}\mathit{1}\mathrm{t}\mathrm{h}\mathrm{C}\mathrm{n}\frac{\}}{\alpha}\mathrm{a}1c111\iota \mathrm{s}\mathrm{i}\mathrm{n}?l|$$D=\{?lf[a_{1},|\cdots|a_{?t}]\in c|\mathrm{i}\mathrm{n}\eta$

}

a few
. We first,
Using t,here basic operations. we define CCS-like ),by a set, of
notat,ions. Let S.
space over
. Let, $V(B)$ be
aints. Thell, and let, Const be a set, of. $S\cdot V(B)=V(S\cdot B)$ with $S\cdot B=\{?l?l[a_{1}|\cdots|a_{r\iota}]|?l)\in S. ?(,[\mathit{0}_{\mathrm{I}}|\cdots|a_{1},]\in B\}$ and. Const.
$\mathrm{i}_{11}\mathrm{t}_{1},\mathrm{o}\mathrm{d}\iota 1\mathrm{t}’ \mathrm{e}$$\mathrm{r}\mathrm{o}\mathrm{C}\mathrm{e}\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{t}\mathrm{l}\iota \mathrm{l}\mathrm{C}\mathrm{t},0\mathrm{l}\mathrm{S}$$1$$S_{1},$$\mathrm{t},\mathrm{h}e\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}_{\mathrm{o}\mathrm{r}}$$S\underline{\cdot)}\subseteq \mathcal{M}$$\mathrm{c}1\iota \mathrm{b}_{\mathrm{C}\mathrm{k}}\mathrm{s}B$$\mathrm{Z}/(2)\mathrm{g}e.\mathrm{n}e,r\mathrm{a}\mathrm{t}_{\mathfrak{l}}e,\mathrm{d}$$S_{\mathrm{l}}\cdot S_{\underline{)}}.=\{?\iota\tau’|u\in S_{1}.\tau)\in$$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{n}\mathrm{m}\mathrm{l}\mathrm{l}\mathrm{t},\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{V}\mathrm{i}\mathrm{t}\mathrm{y}_{\mathrm{C}}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{t},r$$S_{2}\}$$=\{<a_{1}\ldots..a_{n}>_{u’ u}|\tau v\in S.<a\mathrm{l}\cdots ., a_{n}>_{u}\in c_{\mathit{0}\mathit{7}1S}t\}$$S$

is called a process if it, is const,
Definition 15: A
for
.
Atm:
.
Sum:
where (Par:.
. Const)
and (
.
;
Seq:
( (1. X. [X]),.
: $P\backslash L\equiv Rest(P.L)$ . Var:$\mathcal{R}WCC$$\alpha\equiv((1.\alpha.

[\alpha]), o^{0}, \partial^{1}.

induct,ively as follows:$1|1\mathrm{c}\mathrm{t}_{\mathrm{C}},\mathrm{d}$\{\alpha\}.\phi)$$\alpha\in A$$P+Q\equiv(S_{\mathit{1})}+S_{q}.\partial^{0}, o_{1}, F_{I^{y}}\cup F_{q\cdot p\prime_{j}}C_{\mathit{0}7lS}t\cup c_{\mathit{0}}7\iota st)$$s_{1},$$P||Q\equiv(S_{1}+S_{2}, \partial^{0}, \partial^{1}, F_{1}, c_{\mathit{0}?\mathrm{r}9}.t)$$S_{\underline{)}}.,$$P$$\partial 1.F_{2}.$.

$Q\equiv(S_{p}+F_{\mathit{1})}\cdot s_{c_{\mathit{1}}}, \partial 0,\mathit{0}1.F?)$$X=x_{\mathrm{t}l}X|X?\{[X]\in x\cdot s_{\mathit{1}^{)}}\}$

),
) and

$F_{\mathit{1}}‘.Co7l.9t_{l^{)}}\cup F_{I)}\cdot C_{\mathit{0}}nSt_{\mathit{1}},$$\partial^{0}.\partial^{1}$$f_{i}x(X=\Gamma)\equiv((1, X, [X])+X\cdot S_{l^{)}}.\mathit{0}0.o^{1}.F_{1^{J^{-}}}\{X\}.

{, Const) $=P\star Q$$=\Theta(\Gamma\star Q)$$X\equiv$${\rm Res}$$\mathrm{R}\mathrm{e}\mathrm{c}:$$\partial 0,$$o^{0}.o^{1}.F_{1}$$\{X\}.\phi J$

withand sequential in\{X\}\cdot C_{\text{ノ}}\mathrm{o}71.9t_{\iota\prime})$where $X$ is$\Gamma$$\mathrm{g}_{11\mathrm{a}\mathrm{r}\mathrm{d}_{\mathrm{C}}\mathrm{d}}$,ra$\mathrm{e}\mathrm{x}\mathrm{t}$$\mathrm{C}(1^{\iota 1\mathrm{a}\mathrm{t}\mathrm{i}}\mathrm{o}\mathrm{n}\mathrm{S}$215$F)\cdot ConSt)$ andwhelc $P=(s_{\iota\iota p})’\partial^{0},$$\partial^{1},$$Q=(S_{q’ q’ \mathit{1}}o^{0}, \partial^{1}, FC_{\mathit{0}}nst_{t})$are processes.

The idea of defining processes in RWCC is basically the same as t,he HDA int,erpretat,ion of
given in [3]. Bllt we need to give a few words t,o our definit,ion of
a CCS-like process
recursive processes.
processes. We gave a finite representation of guarded and$X$,ra$w[\cdots|X|\cdots]$(
is a process variable) with the
The special cllbes,end t,he language
only describe t,he loop struct,ure and do not, represent any actions. When wet,hat, with guarded but, llot always sequential
processes, we need t,o introduce lnore
processes in. We will give a few examples of ollr
mplex relations wit, regard$\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{e}\mathrm{b}_{1}\cdot \mathrm{a}$$1\mathrm{e}\mathrm{c}11\mathrm{r}_{\backslash }\mathrm{s}\mathrm{i}\mathrm{V}\mathrm{e}$$\mathrm{s}_{\Lambda}\mathrm{e}\mathrm{q}_{11\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}},\mathrm{a}1$$\mathrm{e}\mathrm{x}\mathrm{t}$$\mathrm{e}\mathrm{q}_{11\mathrm{a}\mathrm{t}}\mathrm{i}\mathrm{o}\mathrm{n}x=Xn’ X$$\mathrm{e}\mathrm{x}\mathrm{t}$,$\mathrm{r}\mathrm{e}\mathrm{c}11\mathrm{r}\mathrm{S}\mathrm{i}\mathrm{v}\mathrm{e}^{\iota}$$\mathrm{t},\mathit{0}$$\mathrm{t},oX$$\mathrm{h}$$\mathrm{c}o$$\mathrm{F}\mathrm{i}\mathrm{g}\iota\tau \mathrm{r}(^{\mathrm{Y}},$$2$$\mathrm{r}\mathrm{e}\mathrm{C}\tau \mathrm{l}\mathrm{r}\mathrm{S}\mathrm{i}\mathrm{V}\mathrm{e}$.

$(\mathrm{b})\iota_{1}\mathrm{x}(\mathrm{X}=\mathrm{a};\mathrm{x})+\mathrm{r}\mathrm{l}\mathrm{X}(\mathrm{v}=\mathrm{b};\mathrm{v})$$(\mathrm{a})\mathrm{t}\mathrm{l}\mathrm{X}(\mathrm{X}=(\mathrm{a}+\mathrm{b});\mathrm{X})$

Figure 2:$\mathrm{R}\mathrm{e}\mathrm{c}11\mathrm{r}\mathrm{S}\mathrm{i}_{\mathrm{V}\mathrm{c}}$Processes

const,raints of a )We know from t,he definition that, all thewit,h cubes in the RWCC. Alt,cach element, of in a RWCC (S.
. we can define t,hein t,heis a higher$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}\mathrm{l}\mathrm{l}\mathrm{t},\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{V}\mathrm{i}\mathrm{t},\mathrm{y}$$\subset \mathrm{L}\mathrm{S}\mathrm{S}\mathrm{o}\mathrm{c}\mathrm{i}\mathrm{a}\mathrm{t},\mathrm{e}\mathrm{d}$

$1$

$S$

$\mathrm{h}_{0\iota 1}\mathrm{g}\mathrm{h}$$\mathrm{t},\mathrm{r}t\backslash 11\mathrm{S}\mathrm{i}\mathrm{t},\mathrm{i}_{0}\mathrm{n}$$\mathrm{d}\mathrm{i}_{\mathrm{l}\mathrm{n}\mathrm{C}\mathrm{n}\mathrm{S}}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{t}_{1}\cdot \mathrm{a}\mathrm{n}\mathrm{S}\mathrm{i}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$are t,hose, F. Const)
sense.

$\mathrm{l}\mathrm{o}\mathrm{c}(1,\mathrm{s}\mathrm{s}$$\partial^{0}.\partial^{1}$$\mathrm{t}_{\Gamma\subset},\ovalbox{\tt\small REJECT} \mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}1$and $Q=S_{<D>}$ be RWCCs and $\alpha\in A$ . We will say t,hat,Definition 16: Let$Parrow Q\alpha$is a lower dimensi.onal transition if one of t,he following holds:
and $D(-\alpha)$
Case 1:a path $([X].x[\alpha.], x\alpha[X])$ in $P$ and $D=C[X]\cup\{c\in C|c$ is in t,he form
Case 2:of $?l’[\cdots|x|\cdots]\}$and $D=C(-x_{\alpha)}\cup F(c(-x\alpha))\cdot c(-x)$
Case 3: There is a path $([X].X[\alpha])$ in P.
) $=\{u[\mathit{0}_{1}.|\cdots|a_{l}]|?l?l[\mathit{0}_{1}|\cdots|a_{l}]\in C\}$ andwhere $C[?f]=\{\tau nu[a1|\cdots|a_{l}](\in C)\}$ .
$F(S)=$ {is a maximal path in }.
.,$P=S_{<\mathrm{C}’>}$$[\alpha]\in C_{1}$$\mathrm{T}\mathrm{h}_{\mathrm{C}1}\cdot \mathrm{e}^{\mathrm{Y}},$$\mathrm{e}\mathrm{x}\mathrm{i}_{\mathrm{S}}\mathrm{t},S$$X\alpha[X]\not\in C_{1}$$c_{(-\tau n}$$\partial^{1}(p’)|(p_{1}\ldots$$S$$p_{t})$

Lemma 3 The $followi,ngtra77,s?,t?,onr\tau\iota l\theta,s$ hold for processes where$\alphaarrow\oint)\alpha$$\frac{parrow l)\alpha\prime}{(p||q)arrow(\mathit{1}^{)}|\prime|q)\alpha}$$\frac{\Gamma j^{arrow}q\alpha\prime}{(p||q)arrow(l)\alpha\prime||q)}$$\frac{parrow p’\sim\alpha}{p\cdot qarrow l^{y}’;\alpha q}$

4

ancl

$a\in \mathcal{L}$:,$\frac{p-^{C\mathrm{J}}\prime>p^{\prime\overline{a}}(\mathit{1}^{arrow}q’}{(p||q)arrow\tau_{c\prime}(_{l})||q’)}$$\frac{\int)[fiT(x=p)/X]arrow\alpha p’}{\alpha}$$\frac{p_{j}arrow\alpha_{j}q_{j}}{\alpha_{j}}$$\Sigma_{jpj}arrow(lj$$\alpha.\alpha_{j}\in A$$\frac{parrow p’\alpha\not\in L\alpha\cup\overline{L}}{p\backslash Larrow p’\backslash L\alpha}$

fix $(X=q)) arrow\int)$,,

Cycle Filling as Parallelizationa given RWCC process wit, t,he idea of
we can )In this section, we will consider
is to find which
cycle filling parallelization. Recall the example in Introdllct,ion. The first,
t,heme
procedure. The
part, of
RWCC shollld be identified. This step will be called$\mathrm{h}o\mathrm{w}$$\mathrm{h}$$\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{l}\mathrm{i}_{\mathrm{Z}}\mathrm{C}$$1$$\mathrm{s}\mathrm{t},e\mathrm{p}$$\mathrm{e}\lambda_{\iota}\mathrm{S}$$\mathrm{t},\mathrm{h}e$$7\mathrm{Y}.\prime i,n,.q$216
is essentially equivalent to finding additional prefixed independence
merging, we find cycles to bein the RWCC. The cycles in HDA.
as explained incycle
are found by calculat,ing mology groups. The final step is to fill the cycles wit,
t,he
t,hc
t,hc
and
secondcycles.
newprocedure
cycle fillinglnay
filling map. Because
first,
t,hird steps Inllst, be repeat,ed lmtil there is no cycle any more. We
explain homology groups.
t,healgorithm.
a
we
will
Finally
give
map.
cycle
fillingwedefineThen$1^{\cdot}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}$$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{C}(^{\backslash \mathrm{d}\iota}\prime 1\mathrm{r}\mathrm{c}$$\mathrm{I}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{o}\mathrm{d}_{11}\mathrm{c}\dagger,\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{f}\mathrm{i}11e,\mathrm{d}$$\mathrm{N}e,\mathrm{x}\mathrm{t}$$\mathrm{h}\mathrm{t},\mathrm{h}\mathrm{e}$$\mathrm{h}o$$\mathrm{p}_{\mathrm{l}\mathrm{o}\mathrm{d}_{1}1\mathrm{c}}\mathrm{e}$$\mathrm{p}\mathrm{a}\mathrm{l}\mathrm{e}\backslash 11\mathrm{e}\mathrm{l}\mathrm{i}_{\mathrm{Z}}\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$Cycles and Homology Groups

4.1

A cycle is a$\mathrm{S}\mathrm{l}\mathrm{l}\mathrm{b}s1$)$\mathrm{a}\mathrm{C}\mathrm{e}$ofDefinition 17: Let
cont,ain cubes
space ofis a$\prime \mathcal{R}WCC$$S_{<\mathrm{C}’>}$$\tau\downarrow$

wit,h no boundary. The formal definit,ion is as follows.

be a RWCC. Let
cont,ains process variables.}. Then
such
,
be
will
called n-cycles.
and$K(,\supset r^{\mathrm{x}}\partial_{\mathrm{I}},=\{D\in S_{<C’>}^{\prime 1}|\partial_{\downarrow},(D)=0.D\mathrm{d}_{0}e,\mathrm{s}$) $[a_{1}|\cdot\cdot, |\mathit{0}_{l},,]$$\mathrm{l}\mathrm{s}\iota \mathrm{l}\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{a}\mathrm{r}$$\mathrm{t},\mathrm{h}\mathrm{a}\mathrm{t}_{t}\{\mathit{0},1 , ....

a,, \}$

not,,$Ker^{\mathrm{x}}\partial_{l}$$\mathrm{i}\mathrm{t}_{\iota}\mathrm{S}e1\mathrm{e}\mathrm{l}\mathrm{n}\mathrm{C}\mathrm{n}\mathrm{t}_{\mathrm{S}}$$S_{<C’>}^{\iota}|$.

The reason why we postulat,ed t,he condit,ion $?l’[\cdot\vee\cdot|X|**\cdot]\not\in D$ is t,hat, we do not, want
be filted.
recursion as a cycle
legard t,he loop reptcs($\mathrm{t},\mathit{0}$$\mathrm{t},\mathit{0}$$\backslash ,\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}$hole in the space. For example. consider
an -cycle does not, always meallis a 1-cycle. but, it, is. $\{<a.l)>\})$ .
RWCC
t,ime the t,ot,alat, t,he ,of the 2-cube $[a|l)]$ . Hence. t,he 1-cycle isfilled. Ift,o t,hea cube does not exist. the cycle means a real 2-dimensional hole. This idea leads.
notion of homology
Notice$\mathrm{t},\mathrm{h}e$$\mathrm{t},\mathrm{h}\mathrm{e}$$n$$\mathrm{t},\mathrm{h}\mathrm{a}\mathrm{t}_{}$$(s_{<\{[\iota\iota}|b]\}>.o^{0}.\partial^{1}.

$[a]+[l)]+\mathrm{c}r[l)]+l)[a](\in S_{<\mathrm{C}’>}^{\mathrm{I}})$\{al)\}$$\mathrm{a}1_{1\mathrm{C}}\mathrm{e}\gamma \mathrm{d}\mathrm{y}$$\mathrm{b}\mathrm{o}\iota \mathrm{m}\mathrm{d}\mathrm{a}\mathrm{r}\mathrm{y}$$\mathrm{s}_{t}\backslash \mathrm{I}\mathrm{n}\mathrm{C}$$,\mathrm{s}\iota\tau \mathrm{C}\mathrm{h}$$11\mathrm{S}$$\mathrm{g}_{\Gamma \mathrm{O}11}\mathrm{P}^{\mathrm{S}}[7]$$’>n.o^{0}.o1$. F. $Co?7,.9t$ ) be a
Definition 18: Let(t,hat,
notcont,ain
does
Then, the residue classspace
n- homology group of .
called$\mathcal{R}WCC$$S=(\oplus_{l’\geq<}\mathrm{o}^{S}$$D\in S_{<(>}^{\prime l+1}..D$$c\iota 1\mathrm{b}_{\mathrm{C}}\mathrm{S}\tau n[a_{1}|\cdots|a_{\gamma\downarrow}]\iota \mathrm{s}\mathrm{l}\mathrm{l}\mathrm{C}\mathrm{h}$$I_{77\lambda}\mathrm{X}\partial_{l},+1=\{\partial_{t’+1}(D)|$$\{a_{1}\ldots..a_{tt}\}_{\mathrm{C}\mathrm{O}11\mathrm{t}l}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{s}\mathrm{p}_{1}\cdot 0\mathrm{c}\mathrm{e}s\mathrm{s}$$H_{t},(S)=Kcr^{\mathrm{x}}\partial_{n}/I7\}l^{\mathrm{x}}\partial_{??+}$$\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{C}\mathrm{a}\mathrm{l}$. Let,[

ovel$\mathrm{Z}/(2)(?7_{0}\geq 1)$

variablcs.}.

will be$S$$\mathrm{t},\mathrm{h}e,$

The 71-cycles
71-homology$1\mathrm{e}\mathrm{p}_{\mathrm{l}\mathrm{e}\mathrm{s}}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}$$\mathrm{g}_{\mathrm{l}\mathrm{O}11}1^{)}$

real$(71+1)- \mathrm{d}\mathrm{i}_{\mathrm{I}}\mathrm{n}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}1$holes are described by the$\mathrm{e}1(^{\mathrm{Y}},1\mathrm{n}\mathrm{e}^{\tau},\mathrm{n}\mathrm{t},\mathrm{S}$of the.

.
. F. Const) wit, $C=\{[a]$ . .
Example 3: Consider t,he RWCC $S=$ ($bc[a].C[|y].b[C].a[l)|c]\}$ and Const $=\{<a.l)>, <l), c>, <c.a>$ . $<|).c>_{C1}.<c.a>_{J},\}.$ Figtlle 3t,he geometricof $C’=d_{CCO}\mathit{7}p(C)$ . $S_{<(’>},=\oplus_{r\iota 0}3S’=<(">l$ is as follows:$S_{<C’>}.\partial 0.\partial 1$,,$S_{<(>}^{1},$$[\mathrm{r}i].|)[a].c[a]$$\mathrm{r}\mathrm{e}_{\mathrm{c}}’\iota 1\mathrm{i}_{7}l\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$$\mathrm{i}\mathrm{l}1_{11\mathrm{S}}\mathrm{t},\mathrm{r}\mathrm{a}\mathrm{t},\mathrm{C}\mathrm{s}$$S_{<(^{t}>}^{0}$$[l)]$$\mathrm{h}$$=$$(1. a.b.c, aly(=l)a).aC(=ca).bC(=cl)).al)C(=acb=bac=l)ca=cal)=cl)\mathit{0},)\rangle$.

$=$$([a], [b], [\mathrm{r}i], a[b].a[\mathrm{r}i], |)[a].l)[\mathrm{r}i],$denotesthe homology groups are$\mathrm{w}\mathrm{h}\mathrm{c}\mathrm{l}\cdot \mathrm{e}(g_{1}\ldots..g_{?}, )$$H_{1}(S)$$=$$H_{2}(S)$$=$,$\mathrm{t},\mathrm{h}\mathrm{e}^{\mathrm{Y}}$$C[a].c[l)].al)[(j].ac[|)].|)c[a])’‘ \mathrm{m}\mathrm{d}s_{<^{c^{l}>}}\underline{)}’=(a[l)|c]\rangle$

vector space over$\mathrm{Z}/(2)\mathrm{g}e\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t},(\backslash ,\mathrm{d}$by t,he set,$\{.q_{1}\ldots...q,,\}$. Then$0$.
of $H_{1}(S)$ sllch as $([l)]+[\mathrm{r}i]+l)[\mathrm{r}i]+c[b])+(l)[a]+l,[c]+\mathit{0},b[c]+l)c[a])=[l)]+[c]+$$c[|)]+l)[a]+al)[\Gamma i]+l)c[a]$ also represent, 2-dimensional holes but, t,hey areby colnbinat,ioll

Not,ice that, the generators of $H_{1}(S)$ rcprescnt, the obvious 2-dimensional holes in t,he ,$\mathrm{s}_{1^{)_{\subset \mathrm{t}\mathrm{C}}’}}\mathrm{e}$Ot,her element,$\mathrm{s}$$\mathrm{o}\mathrm{b}\mathrm{t}_{\subset}\backslash \mathrm{i}\mathrm{n}(^{\tau}\mathrm{d}$217$\mathrm{F}\mathrm{i}\mathrm{g}_{11\mathrm{r}\mathrm{C}}3$: Geometric Realization ofof the holes represented by the generators. Also t,here isThis is indicat,ed by t,he vanishing of.

$d_{CC}o\mathit{7}l?,t^{)(}c$$11\mathrm{O}3$)-dimensional hole in t,he$\mathrm{s}_{1^{)\mathrm{a}\mathrm{C}\mathrm{e}}}$.

$H\underline{\cdot)}(S)$Of course. the gencratols of a linear space are not, luliqllcly determined and we will call thegenerat,ors sllch as in t,he above example the $\min,$ $?,mal$ generators. A minimal generator is t,hebolmdaly of a single cube. The
definition isfoll.
$\mathrm{P}^{\mathrm{l}\mathrm{e}\mathrm{C}\mathrm{i}_{\mathrm{S}}\mathrm{C}}$$\subset\backslash _{\iota}\mathrm{s}$Definition 19: The set of generators
if eachis the$m?,\dot{?,}mal$$\{.q_{1}, \ldots, .q_{k}.\}$$\mathrm{f}_{01\mathrm{m}\mathrm{a}}1\mathrm{S}11\ln$$e1\mathrm{e}\mathrm{m}\mathrm{C}\mathrm{n}\mathrm{t}3.q_{i}$of$o\mathrm{w}\mathrm{s}$of t,he holnology.

$H_{l},(S)$)$\mathrm{g}_{\mathrm{l}\mathrm{O}11}1$

is called$1\mathrm{c}\mathrm{n}\mathrm{g}\mathrm{t}_{l}\mathrm{h}2(7+1)$

Lemma 4 For a RWCC S. the set of minimal $.qe7|,erat_{or9}$. of the -homology $grollp..H,l(S)alu)ayS$
uni.quely.
$?l$$ex?_{\text{・}}stS$In
following, when we
generators of a homology group. we will always
therat,herminimal ones. The
of a homology group can be comput,ed by aeasy algorit, .
as Gallss method. in linear algebra as demonstrat,ed ill [2].
$\mathrm{t},\mathrm{h}e$$1^{\cdot}\mathrm{e}\mathrm{f}\mathrm{e}\mathrm{r}$($\backslash \mathrm{S}\mathrm{S}\mathrm{l}\mathrm{u}\mathrm{n}\mathrm{e}$$\mathrm{h}\mathrm{l}\mathrm{n}$$\mathrm{g}_{\mathrm{C}\mathrm{n}\mathrm{e}\mathrm{l}\mathrm{a}}\mathrm{t},\mathrm{o}\mathrm{r}\mathrm{s}$$\mathrm{s}\iota \mathrm{l}\mathrm{c}\mathrm{h}$Cycle Filling Map

4.2

Now we will define t,he cycle fiIling map
t,ot,al bollndal y of an
be
from
.
$\mathrm{t},\mathrm{h}e$of RWCC. Consider a RWCC $S_{<C’>}$ . Let,
:
.
will

$cj_{?l}\in K<^{\supset},r^{\mathrm{x}}\partial,$$s_{r\iota}$$\cdot$$(n+1)-\mathrm{C}\iota 1\mathrm{b}(^{\backslash },$$cin+1\in C_{tl+1}$$cj_{?1}=\partial_{?\downarrow+1}(c_{l\iota+1})$$\mathrm{t},\mathrm{h}\mathrm{e}\backslash ,\mathrm{n}.9,l$,,$\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{l}\dot{\mathrm{l}}\mathrm{S}\mathrm{t},1^{\cdot}|\mathrm{l}\mathrm{c}\mathrm{t}$$c_{7l}:.\mathrm{s}_{\iota},(c_{?\iota})=c_{n+1}$$c_{r\iota+1}$

Definition 20: Letbe a RWCC. Then, the cycle filling map , :$(7l\geq 1)$ is a fimction such that, for arbitraly. $S_{l},(M)$ is
computed as follows:
Step 1: Let,
where the word is t,he longest wold sllch
all .
for
some word .
Step 2: Calculate
where , is t,he linear map $S_{<(^{}>}^{l}’arrow V(A\cross P_{ol(}A))$ such t,hat,. $\{a1\cdots., a,\}n>$ .
Step 3: If there is a set $\{l)1, \ldots.l)n+1\}(\in Pou’(A))$ suchis in t,he folIn of$S_{<\zeta^{\mathrm{Y}}>}$$s,$$S_{<(>}|’,arrow S_{<>}^{ll+\mathrm{l}}c$’$M=\Sigma_{j}\tau v_{7}\cdot[a(j)1|a_{\mathit{2}}^{\langle)}?|\cdots|a_{r\iota}^{1i)}](\in S_{<(>}’’,)$$M=?\mathit{1}’ N$$klf$$\mathrm{t},\mathrm{h}\mathrm{a}\mathrm{t}_{}\mathrm{f}\mathrm{o}1$$\dot{i}$$\tau n_{j}=\tau n\tau|,j$$?|,i$$\varphi_{n}(N)$$\varphi_{\eta}$$\varphi_{?\downarrow}(\tau\iota[a1|\cdots|a_{\tau l}])=<\tau\iota$$\varphi_{?\iota}(N)=$$\mathrm{t},\mathrm{h}\mathrm{a}\mathrm{t},\cdot\varphi_{n}(N)$$\Sigma_{i1}^{r\iota+1}=<1.P_{i}>+\Sigma_{i=1}^{n+1}<b_{?}\cdot.P_{i}>$...

$|l)_{n+1}$, where $P_{\mathrm{i}}=\{b_{1}\ldots. ..., l)_{\gamma+1},\}$ .

then $s_{l},(M)=?If[l)\mathrm{I}|$] ot,herwise $s_{n}(M)=0$ .

Notice t,hat, t,he cycle filling map
checks whet,her $M$ is a minimal generat, $or$ ofn-homology, t,o fill
and construct the sllitable
cycle. Hence we .an define thecycle filling algorit,hm as follows.
$\mathrm{t},\mathrm{h}\mathrm{e}$$.9_{n}$$\mathrm{g}_{\mathrm{l}\mathrm{o}\mathrm{t}1}\mathrm{p}H,(C)$$(n+1)- \mathrm{C}1\iota \mathrm{b}\mathrm{e}\backslash$$\mathrm{t}_{}\mathrm{h}\mathrm{e}$$\mathrm{c}$218
Cycle Filling Algorithm: Given a RWCC
1. If $H_{n}(S)=0$ for all $n\geq 1,$ thcn.. goto 4.
t,hat
2. Let $N$ bc the smallest number
is a (minimal) genelator}.
$C:=C\cup
NewCubes$ , then goto 1.
3. Lett,he obt,ained RWCC.
4.

$S=S_{<\mathrm{C}>},$$\mathrm{s}\iota \mathrm{l}\mathrm{c}\mathrm{h}$. then$H_{l}\mathrm{v}(S)\neq 0$

and let

$N_{C?}r’ C\tau ll$)$e.9=\{S_{N(C)}|C\in$$H_{\mathrm{V}}.(S)$$\mathrm{R}\mathrm{e}\mathrm{t}\iota\iota \mathrm{r}\mathrm{n}$Notice t,hat, t,he cycle filling map does not increase the 1-cubes nor thein the given RWCC. Flom this fact. we obt,ain t,he following.

$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}11\mathrm{t},\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{V}\mathrm{i}\mathrm{f}_{}\mathrm{y}$,$such$ that
set. the cycle
is aLemma 5 For arbi.trary RWCC $s_{<(>}$$term?,nates$ in finite steps rrnd the obtained data is again a RWCC.
$C$$fi_{71_{\text{ノ}}}?,te$const,raints$fill’i_{71},,.\mathrm{r}/al.q_{\mathit{0}r\dot{?,}t}hm$

Example 4: We will reconsider the RWCC in Example 3. By applying t,he cyclc filling Inap
) . $[b|$,ain the newof $H_{1}(S)$ weto the (,. Then $H_{1}(S’)=0$ and $H_{2}(S’\rangle=([a|b]+[l)|c]+[a, |\mathrm{r}i]+l)[a|c]+c[a|$t,o,ain t,het,o t,he gencrat,or of$l)]+a[l)|c])$ . Thusa 2-cycle. Now we apply,
that, $C’=decolp(\{[a|l)|c]\})$ .
is. The
RWCC $S’=S_{<(^{::}>}$
3-cubet,erminates$71\geq1$
by ,urning t,he RWCC ”.
. Then the algorit,hm
for allNow$S$$\mathcal{R}WCcS’=S_{<c^{t’}>^{\mathrm{w}}}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}C’=C\cup\{[a|l$$\mathrm{o}\mathrm{b}\mathrm{t}$$\mathrm{n}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t},\mathrm{o}\mathrm{r}\mathrm{S}$$s_{1}$$]$$\mathrm{g}$$c].[a|\mathrm{r}i].lJ[a|\mathrm{r}i].c[a|\mathrm{I})]\}$$H_{\underline{)}}.(S^{t})$$S’\mathrm{h}\epsilon\gamma_{\iota}\mathrm{s}$$\mathrm{o}\mathrm{b}\mathrm{t}$$s\underline{\cdot)}$$[a|b|\mathrm{r}i]$$\mathrm{s}\iota \mathrm{l}\mathrm{c}\mathrm{h}$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{t}\mathrm{r}\iota \mathrm{l}\mathrm{c}\mathrm{t},\mathrm{e}\mathrm{d}$

4.3

$S$

$\mathrm{r}\mathrm{e}\mathrm{t}$$H_{r\iota}(S_{<C>}\mathrm{Y}..)=0$

Parallelization Algorithm with Cycle Filling Map

in t,he language of RWCC according t,o t,he
Now we will forInlllate t,he parallelization ) ).
ofgeneral idea given by E. Goubault [2]. First of all. we define t,he$\mathrm{l}\mathrm{o}\mathrm{l}$$\mathrm{l}\mathrm{e}\mathrm{m}$$1$$\deg_{1(^{\backslash }},\mathrm{e}$Definition 21: Letparallelism of .

,($P=\oplus_{l=0},\mathrm{v}S_{<(>}’$

be a$R\mathcal{W}CC$$\mathrm{p}\mathrm{a}\mathrm{l}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{C}^{\mathrm{Y}},1\mathrm{i}\mathrm{s}\mathrm{l}\mathrm{n}$. Then $por(P)\equiv N$ is called t,he degree of$P$

Lemma 6 For $arbi,trary$ processes and Q. ) have
1. par $(\alpha)=1$ if is an Atm.
2. $pa,r(P+Q)=par(P : Q)=\mathit{7}l\mathrm{z}aX\{par(P).l)ar(Q)\}$ .
3. par $(P||Q)=par(P)\cross par(Q)$ . and 4. par $(f_{\dot{i}}x(X=P))=par(P)$ . .
$\Gamma$$u$$e$$\alpha$This lemma claims that the definition of par is an acceptable definit,ion degree of parallelism offor labelprocesses. Although there seems t,o be no synt,actical definition of degree oft,heselnant,ics), we can defineatlevel.
$\mathrm{p}_{C}’\mathrm{t}1^{\backslash }\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{S}\ln$$1\mathrm{e}\mathrm{s}\mathrm{t},1\mathrm{i}\mathrm{c}\mathrm{t}\mathrm{i}_{0\mathrm{n}}\Gamma\backslash L$$l$$a,r(P\backslash L)$

be RWCC. If
and
:
maps
$\varphi_{j}(c)=c$
sllch that (i)for all $c\in Basc(s1\cdot\dot{i})$ .
maximal Hoare traces ofand. and (iii) andt,heresay thatis an embedding:.

Definition 22:

Let,$BaSc(S_{1}.\dot{i})arrow Basc(s\underline{\cdot)},\dot{i})$$\mathrm{t},\mathrm{h}\mathrm{e}\mathrm{r}e\mathrm{a}\mathrm{r}e$$S_{2}$$S_{1}$$\varphi_{j}$$(0\leq\dot{i}\leq par(S_{1}))$$\iota)\mathrm{C}\mathrm{t},\mathrm{w}(^{\mathrm{Y}},\mathrm{e}\mathrm{n}$$S_{2}$$S_{1}$$\varphi_{0}$$(\mathrm{i}\mathrm{i})\varphi_{0}$indllce\iota s a.

$\mathrm{S}111\mathrm{j}\mathrm{t}^{\backslash },\mathrm{C}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{t},\mathrm{h}e,\mathrm{n}$$\varphi_{1}\subset\backslash 1^{\cdot}\mathrm{C}\mathrm{s}\mathrm{l}\mathrm{u}\cdot.|\mathrm{e}\mathrm{C}\mathrm{t},\mathrm{i}_{0}\mathrm{n}\mathrm{s}$we will$S_{\mathrm{I}}arrow S_{2}$$\varphi=\oplus_{i}\varphi_{j}$. We haveandsuch t,hat, $\varphi_{0}(1)=1$ .
.
.
. $\varphi_{1}([a])=[a]$ ,$\varphi_{1}(a1^{l})])=a[b]$ . $\varphi_{1}(l)[a])=l)[a]$ and $\varphi_{1}(ol)[C])=al)[c]=l)\mathit{0}[C]=\varphi 1(l)a[C])$ .
The
a
. so
of maximal Hoare traces in and are $\{al)C.l)ac\}$ andthem.

Example 5: Let $P$ and$\varphi_{0}(a)=a$$\varphi_{0}(l))--|),$$Q$

be as in$\mathrm{F}\mathrm{i}\mathrm{g}\ln(^{\mathrm{Y}},$$4$$\mathrm{s}\iota \mathrm{u}\cdot.|_{\mathrm{C}}\mathrm{c}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\varphi 0$$\varphi_{1}$$\varphi_{0}(al))=\mathit{0},b=ba--\varphi_{0}(l)a)$$\varphi \mathrm{o}(alyc)=a|_{)C}=l)ac=\varphi \mathrm{U}(l)aC)$$\varphi_{1}([l)])=[1)],$$\mathrm{s}\mathrm{e}\mathrm{t},\mathrm{s}$

$P$

$Q$

$\{\mathit{0},l)c(=|yaC)\}$$\mathrm{t}_{\vee}\mathrm{h}\mathrm{a}\mathrm{t},$$\varphi 0\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{l}\mathrm{l}\mathrm{C}e,\mathrm{S}$$\mathrm{s}\iota 11\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t},\mathrm{i}_{0}\mathrm{n}\mathrm{b}\mathrm{C}\mathrm{t},\mathrm{w}\mathrm{c}\mathrm{t}^{\backslash },\mathrm{n}$We will say t,hat, a RWCC
and par:$\varphi$$S_{1}arrow S_{2}$$S_{2}$

is a parallelizati.
ifof a RWCC. Now we will give an parallelization$(s_{1})\leq par(S\underline{\cdot)})$$\mathrm{O}7l$$S_{1}$$\mathrm{t},\mathrm{h}\mathrm{c}\mathrm{r}e$is an ernbedding$\mathrm{a}_{01}\cdot \mathrm{i}\mathrm{t},\mathrm{h}\mathrm{m}$wit,h t,he219$\mathrm{F}\mathrm{i}\mathrm{g}_{11\Gamma}\mathrm{e}4$: Embedding of Processes

cycle filling map. Recall t,he example of parallelization in Introduct,ion. The first ,ep is themerging procediuie: to find which part, of the given RWCC should be ident,ified. Such part, ofthe space is detelmined with the merging candidate defined below.
$\mathrm{s}\mathrm{t}$be a RWCC. Then a pair of stat labels in t,he form
is called the merg $i_{7}|,.q_{Ca}r|,didate$ of if $C_{i}(-8n\alpha_{l}i)=C_{j}(-uf/i\alpha)(\dot{i}=0,1)$
where $C_{j}(-w)$ is as in Definition 16.

Definition 23: Let$(\tau n\in \mathcal{M}.

$S$$\mathrm{o}\mathrm{f}\ll\tau n\alpha/i.\tau\iota f/i\alpha\gg$

$e$

$S$

\alpha.l^{i}\in \mathcal{L}\cup\overline{\mathcal{L}})$

Not,ice that, the cycles are generat,ed only by equating t,he merging candidat,es because we havet,he following.

Lemma 7 Any process $P?,S$ cycle free. Namely. $H_{n}(P)=0$ for all $n\geq 1$ .
A merging candidat, is a pair oflabels to be equated in t,he lnelging. If t,he,ate labels in the merging candidate are equat,ed.
of other cubes in the RWCC
also)
with t,he light, ext,ension rlde. The reason why we post,
the conditiont,heas follows. We cannot equate all the pair of elements inform.
For example. consider a process $R=a$ ) $+b;a$ $c(a, l),$ are Atms). Then Ba.se $(R.0)=$$ab=l$) . and. If we{ $1.a.l)$ . ab. $l)a,$ $bac$ } so that we have acycle. we )fill
the RWCC $Q=(S_{<(>},.o^{0,1}\partial. \{al)(^{\backslash },\}. \{.<a.b>\})$ wit,h $C=\{[a|l)].al)[C]\}$(see
4).
is no mbedding of int,obut$\mathrm{s}\mathrm{t}_{}\mathrm{a}\mathrm{t}\mathrm{e}$$\mathrm{e}$$\mathrm{P}^{\mathrm{r}\mathrm{o}}\mathrm{C}\mathrm{C}\mathrm{d}\iota \mathrm{u}\cdot \mathrm{e}$,$\mathrm{s}\mathrm{t}$$\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{n}\mathrm{e}^{\mathrm{Y}}$($\mathrm{a}1^{\cdot}\mathrm{C}$,$\iota 11\mathrm{a}\mathrm{t}_{\mathrm{C}^{\backslash }},$$,\mathrm{q}_{11\subset\backslash }\mathrm{t}\mathrm{e}\backslash ,\mathrm{d}$.

$C_{i}(-\mathrm{t}lf/i\alpha)\mathrm{i}\iota \mathrm{s}$

$l$

!

(

$o1$

$=$

$c$

$\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}\ll ab.ba\gg \mathrm{i}\mathrm{n}Ba.9e(R_{:}.0)$$\mathrm{t}_{j}\mathrm{h}$$c_{i(-?\mathit{1}^{f}}\alpha\beta$$\mathrm{o}\mathrm{f}\ll\tau n\alpha/i.m/i\alpha\gg$$\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}_{11}1\mathrm{a}\mathrm{t},\mathrm{c}$$\mathit{0}$$\mathrm{t}_{\mathrm{e}\gamma},\dot{\mathrm{m}}$$,$,$\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{C}^{\mathrm{Y}}$

$R$

$e$

$Q$

Now we cm define olll parallelizat,ion$\mathrm{F}\mathrm{i}\mathrm{g}\iota \mathrm{l}\mathrm{r}\mathrm{C}$$\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{l}\cdot \mathrm{i}\mathrm{t},\mathrm{h}\mathrm{m}$.

Parallelization Algorithm: Given a RWCC $S=$ ( $s_{<(>},,$. F. Const). t,hent,hecandidat,es
1. Findset of merging
2. Make t,he set
3. Replace Const byout, t,he cycle filling algorithm on
4.
with t,he new Const.
$\partial 0.\partial^{\mathrm{l}}$$MCP\mathrm{f}\mathrm{i}\cdot o\mathrm{m}c_{0}$$C_{on\mathit{8}}t_{0}=\{<\alpha, /i>_{ll}, |\ll w\alpha \mathit{1}^{i.\mathrm{t}l}/3\alpha\gg\in MC\Gamma\}$$C_{on9}.t\cup C_{\mathit{0}\prime}\mathrm{r}St_{0}$$S$$\mathrm{C}_{\subset}\urcorner 11\mathrm{y}$Example 6: Consider the process $P=a$ : $(l)||c)+l)$ : $(a ; c+c_{\backslash }a)+c:\{a\backslash b+b$ : ) given in
hlt,lod\iota lct,ion. It is realized as
RWCC $\Gamma=(S_{<(>},.o^{0}.\partial^{1}. \{al)c(=acl)).baC.|)ca$ . cab. ) } . $\{<$$ba.b_{C,C}ly.ca,$$l).c>_{C1}\})$ where $C_{0}=$$1.a.b.c$$aC,$ $abC.acb,$ $bac.l)Ca.cal).cba$ } . $C_{1}=\{[0,]$ .
. ab.
.
.
{
$a[c].l)[a].l)[C].c[a].C[b].\mathit{0}.l)[C1, aC[l)].ba[\Gamma i],$ $bc[\mathit{0}].ca[b].Cl)[a]\}$ . $C_{\mathit{2}}=\{a[a|l)]\}$ .
We find t,he set, of$\gg.\ll$)ab, ) $a\gg.\ll l$) $c.cl$) $\gg.\ll ac,$ $ca\gg.\ll cal$) $.Cl$) $O\gg.\ll al$)Inerging candidate {$a$),$\mathrm{t}_{e}\mathrm{h}\mathrm{c}$$cl$ $a$$[l)]$$\ll$$l$$c.\mathrm{c}’ Cl$$[\mathrm{r}i].a[b]$220$l)ac.l)ca\gg\}$ fi.oIn which we obtain the additional$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{I}\iota \mathrm{n}\mathrm{l}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{V}}\mathrm{i}\mathrm{t}\mathrm{y}$constraints $\{<a.l)>,$ $<l),$ $c>$
,ension rule alld$l)>_{c}$ . $<b.c>_{a},$ $<a.c>_{b}\}$ .
$:<a.c>$ .
) $ca=cab$ $=cba$ . $al$) $[c]=l)a[c].ac[l)]=$we know other$ca[\mathrm{I})].bC[a]=cl)[a]$ . Then the obtained RWCC is in fact equal to the RWCC in Example 3. and, as in Example 4.
RWCC is in fact,
is carri
the cycle filling

Notice t,hat with the right,$<\mathit{0},,$$\mathrm{o}\mathrm{t},\mathrm{h}e,\mathrm{r}$$\mathrm{e}\mathrm{x}\mathrm{t}$$\mathrm{e}\mathrm{q}_{11\mathrm{a}}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{S}abc=acb=bac=l$$\mathrm{r}111\mathrm{C}^{\mathrm{Y}},\mathrm{S}$$\mathrm{a}_{0\Gamma \mathrm{i}\mathrm{t}\mathrm{h}},\mathrm{m}$$\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{t}.\mathrm{h}\mathrm{C}\mathrm{o}:’$\mathrm{o}\mathrm{d}\mathrm{o}1r_{\wedge}\backslash ...1\mathrm{t}$t,he process $Q=(a||l)||c)$ . ,..

.:$\cdot$\mathrm{b}\mathrm{t}0\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{d}$.::.

$\cdot$ofour parallelization algorithm does not always generate a RWCC in
,ain
;
$b+b$
;
$(a+c)$
the$P_{1}=a$we.
algorit,hm to. by applying.
. Thi does not$R\mathcal{W}CCQ_{1}=$ ({ab, $bo.lyC\},$ $\{<a.l$)denot, any process.
Notice$\mathrm{t},\mathrm{h}\mathrm{a}\mathrm{t}$,$\mathrm{t}_{\downarrow}\mathrm{h}\mathrm{e}\mathrm{f}\mathrm{o}1^{\cdot}\ln$$\mathrm{o}\mathrm{b}\mathrm{t}$$\mathrm{t},\mathrm{h}\mathrm{e}$$\mathrm{F}o\mathrm{r}e,\mathrm{x}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}$$\mathrm{p}_{1}\cdot \mathrm{o}\mathrm{c}\mathrm{C},\backslash \mathrm{s}\mathrm{s}$$S_{<C^{}>},$$\partial 0,$$\partial 1.$$>\})\mathrm{w}\mathrm{i}\mathrm{t},\mathrm{h}C=\{[\mathit{0}|l)].|)[Ci]\}$$\backslash \mathrm{s}$$\mathrm{e}$$\mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}[\mathrm{l}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{Z}\mathrm{a}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{n}$rithm$\mathrm{a}\dot{\mathrm{o}}$cannot,of a process P. our parallelizat ion alis a) : $q+q$ : $p+a_{\backslash }b+b_{\backslash }(a+c)$ .
. For example. consider a$b+b$algorit,hm$(a+c)$
bllt ollr;
is a parallelizat,ion of; ) $+a$ ;wit,h$D=\{[p|q]$ . $[a|$const,ruct $Q_{3}=$ (. {ab. $bo,$ ) $c.pq.qp\}$ . $\{<a, l)>$ . $<p.q>\})$
be callied
is not a process. This indicates that t,he Inerging
andollr with more sllbtlc information on the given process.

Also, if a )always const,$1$$\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}8\mathrm{s}Q$$\mathrm{r}\mathrm{l}\iota \mathrm{c}\mathrm{t},$$\mathrm{T}\mathrm{h}\mathrm{e}\backslash ,\mathrm{n}Q_{2}=\langle_{l^{y}}$

${ }$

$Q$

$\mathrm{p}_{\mathrm{l}\mathrm{O}\mathrm{C}}\mathrm{e}\mathrm{s}\mathrm{s}P_{2}.=l$$P_{arrow)},$$q$$S_{<D>}.\partial^{0}.\partial^{1}$$l)].l)[\prime j]\}$Despit,$\mathrm{e}$$go1^{\cdot}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}$$\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{l}16^{\mathrm{Y}},1\mathrm{i}_{7\mathrm{a}}r\mathrm{t},\mathrm{i}_{0}\mathrm{I}1$$\mathrm{p}r\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{Y},\mathrm{d}\mathrm{l}\mathrm{l}\mathrm{l}\mathrm{C}\mathrm{s}\mathrm{h}\mathrm{o}\iota 1\mathrm{l}\mathrm{d}$$\mathrm{t}\mathrm{l}\dot{\mathrm{u}}\epsilon$t,hese problems, we have$\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{Z}\mathrm{a}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{l}\mathrm{l}$$l$$\mathrm{t},\mathrm{h}e$following.

Theorem 1 (1) For any process P. if the parallelization al.qorithm$al.q_{or?}.thm$ doesa $parall_{\ell},li,zati,on$ of P. (2) If the
7l,on-triv?,al.
parallelization ofnoP. the$i,s$$parallel\dot{i}Zat?.\mathrm{O}7l,$$7l,$$th,ere,\dot{i}S$a processchange the$\mathit{0}\tau\iota tp\mathrm{t}ts$$?l_{S}ot$

$Q$

the

$7|,$

$Q$

$in.p\mathrm{t}\iota tproc,es.9$$\Gamma$

Whcthcr the parallelized RWCC is a process or not can be checked by t,he colnbinat,olial geoInet,analysis called reverse interpret,ation [9].
$\mathrm{r}\mathrm{i}\mathrm{c}$2215Discussion and Conclusion

We present,ed a new formulation of Pratt-Glabbeck-Gollba\iota llt-Jensen style Highcl.-Dinlensional(HDA) modcl. The idea is to give an intrinsic definition of)with cubical Bar-not,ation. The obtained formulation is called rcachable well-labeled
complex(RVVCC) and it nlakel,s clear relation between the general idea of HDA andsemaIltics
sllch as Hoare tlaces andtraces. Using the langllage of RWCC. wet,heto solve
parallelization problem of CCS-likealgebra, which is a refinement, of t,hewolks by E.
andallthor [8]. The cycle filling map can be
defined in). As explained in sect,ion 4.
RWCC and we gave a parallelization algorithm using thealgorit,hm does not, always const,ruct, parallelized)
cesses from given processes. E.
[2] seems t,o indicat, the basic idea to solve t,his. Namely. a
CCS-like ),endedcess is generally a part of a more parallel process in anprocess calcllli. This idea has
not, been
imulat,ion issues
investigat,ed intheory. Also, we did not, considel.
t,hist,echnical
,ail
,
t,o
in
paper. Morebediscuss
and it,will beinoccasion.
$\mathrm{A}\mathrm{l}\mathrm{l}\mathrm{t},\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{a}$$\mathrm{h}\mathrm{y}1^{)e\Gamma}\mathrm{C}\iota\iota \mathrm{t}$$\mathrm{e}\iota \mathrm{S}$$\mathrm{c}\iota \mathrm{l}\mathrm{b}\mathrm{i}\mathrm{C}‘\backslash 1$$\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}$$\mathrm{t}_{}\mathrm{h}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{C}\mathrm{s}$$\mathrm{M}\mathrm{a}\mathrm{z}11\mathrm{r}\mathrm{k}\mathrm{i}_{\mathrm{C}}\mathrm{w}\mathrm{i}\mathrm{c}\mathrm{Z}$$\mathrm{t},\mathrm{r}\mathrm{i}\mathrm{e}^{\backslash },\mathrm{d}$$\mathrm{p}_{10\mathrm{C}}\mathrm{e}\mathrm{s}\mathrm{S}$$\mathrm{t},\mathrm{h}e$$\mathrm{G}\mathrm{o}\iota \mathrm{l}\mathrm{b}\mathrm{a}\iota 1\mathrm{l}\mathrm{t}[2]$$\mathrm{f}_{0\mathrm{r}}\mathrm{I}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{y}$$01\mathrm{U}^{\cdot}$$\mathrm{m}\mathrm{a}_{1}$$\mathrm{G}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{l}$$\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{l}\mathrm{t}$$\mathrm{p}_{1}\cdot \mathit{0}$$\mathrm{e}$$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{b}1\{^{\backslash },\mathrm{l}\mathrm{n}$$\mathrm{p}_{C\backslash 1\subset\backslash }.11\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{Z}\mathrm{C}\mathrm{d}$$1$$\mathrm{r}\mathrm{o}-$$\mathrm{e}\mathrm{x}\mathrm{t}$$\mathrm{t},\mathrm{h}_{\mathrm{o}\mathrm{r}\mathrm{o}1}1\mathrm{g}\mathrm{h}\mathrm{l}\mathrm{y}$$\mathrm{d}\mathrm{c}\mathrm{t}$$\mathrm{e}\mathrm{x}\mathrm{t}_{}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}_{\mathrm{V}}e1\mathrm{y}$$\mathrm{r}\mathrm{c}\mathrm{p}\mathrm{o}\mathrm{l}\cdot \mathrm{t}\mathrm{e}\mathrm{d}$$\mathrm{b}\mathrm{i}\mathrm{L}\mathrm{S}$$01\iota \mathrm{r}$$\mathrm{m}\iota \mathrm{l}\mathrm{s}\mathrm{t}$$\mathrm{t},\mathrm{h}\mathrm{i}s\mathrm{i}_{\mathrm{S}\mathrm{s}\mathrm{t}1}(\backslash$$\mathrm{p}_{\mathrm{l}\mathrm{e}\mathrm{S}}\mathrm{e}11\mathrm{t}_{\wedge}\mathrm{e}\mathrm{d}$,$o\mathrm{t},\mathrm{h}\mathrm{c}\mathrm{r}$References[1] E. Goubault,. Domains of Higher-Dimensional Aut,omat,a. In 4th
on Concurrency Theory, LNCS 715.
Verlag. 1993.

$I_{7|,te\Gamma|}lC\iota t?,onalC_{\mathit{0}nfCr\rho},,7|,C(,g$$\mathrm{s}_{\mathrm{P}^{\mathrm{r}\mathrm{i}\mathrm{n}}\mathrm{g}\mathrm{e}}1$[2] E. Goubault.
asIntelprctations of Higher-Dimensional Aut,omat,a. In
Proc,. of FEPM g5. ACM Press. 1995.
$\mathrm{S}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}\iota 1\mathrm{l}\mathrm{e}\mathrm{r}\mathrm{s}$$\mathrm{A}\mathrm{b}_{\mathrm{S}}\mathrm{t}\mathrm{l}\mathrm{a}\mathrm{C}\mathrm{t},$[3] E. Gollballlt and T. P. Jensen. Homology of Highcl Dimellsion\subset \l Aut,omata. In 3rd $I7|,ier-$
national Conference on
Theory. LNCS 630. Springer Verlag. 1992.
$c_{\mathit{0}71,Cu}rr\rho_{J}nc.y$[4] J. F. Groote and R. Moller.
$I_{71,t7}er|,at?,onalc_{on}fe,rC,7l,ce$ on

Verificat,ion of Parallel Syst,ems via$Conc1\iota rrC^{\lrcorner}ncy$. In 3rd
Theory. LNCS 630. Springe,r Verlag. 1992.
$\mathrm{D}\mathrm{c}^{\mathrm{Y}},\mathrm{c}\mathrm{o}\mathrm{m}1^{)0\mathrm{s}}\mathrm{i}\mathrm{t},\mathrm{i}\mathrm{o}\mathrm{n}$[5] A. Mazllrkiewic7r. Trace Theoly. In Petri Nets: Applications $a7|,d$ Relati.onships to Other
Models of Conc.urre,ncy. LNCS 255. Springer Verlag. 1986.
[6] V.
. Modeling Concurrency wit.h Geometry. In 18th
Frinciples of $\Gamma ro.qramm?,7\iota.qLa7|,.quageS$ . ACM. 1991.
$\mathrm{p}_{\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{t}t}$[7] E. H. Spamier. Alqebrai. c Topology.

$\mathrm{M}\mathrm{c}\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{w}$$A_{\mathit{7}l71,1}\iota al$

ACM Symposium 077,

-Hill. 1966.

[8] Y. Takayama. Parallelizat,ion of Concurrent Processes in Higher Dimensional Aut,omat, . In
RIMS Workshop on Term
Application. RIMS Kyot,0 University.
’ Systems and$\subset \mathrm{t}’$$Rewr\dot{i}ti_{\mathit{7}\prime},,.r$$?,ts$

1995.

[9] Y. Takayama. Ext,raction ofPr0cesses from Higher Dimensional Automat,a. In
g6.
CAAF
LNCS 1059. Springer Verlag. 1996.
$\mathrm{c}_{0\mathrm{n}\mathrm{c}}11\mathrm{r}re\mathrm{n}\mathrm{t},$[10] R. van Glabeek. Bisimulation semantics for higher dimensional automat,a. TechnicalSt,anford University, 1991.

${\rm Re}_{1^{)\mathrm{o}\mathrm{r}\mathrm{t}}},$.

[11] G. Winskel and M. Nielsen. Models for concurrency. In Handbook of $Lo.q?,C$ i,7|, Computer
Sci,ence. Vol.4. Oxford Science. 1995.
$\mathrm{P}11\mathrm{b}\mathrm{l}\mathrm{i}\mathrm{C}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}\mathrm{S}}$