Re: computation in CPS

Re: computation in CPS

[Sjoerd CRANS]

Philippe Gaucher <gaucher@irma.u-strasbg.fr> asked:

> for a CPS, is there a way to compute 
> the source and target of a R({x}) using only compositions of elements 
> like R({y}) ?

Yes and no.

Yes in the sense that because the source and the target are pasting
schemes themselves, Johnson's pasting theorem gives that 1. they
are compositions of R({y})'s and 2. *any* way you do this gives the
same result.
No in two senses: although Johnson's proof actually gives an algorithm,
I don't think this algorithm has ever been implemented (in AXIOM for
example); and secondly, there is (as far as I know) no *general*
expression which works for cubes of all dimensions.

Sjoerd Crans

Re: computation in CPS

[Ross Street]

Dear Categories:

I sent this yesterday but I notice I had mixed up the address. I'll try again.

--Ross

>In the omega-category In generated by the n-cube, is it possible to
>find a kind of "general" formula for the (n-1)-source (target) of
>the n-morphism corresponding to the interior of In ? I can do
>mechanical computation in low dimension but I am not able for the
>moment to imagine a formula for any dimension. In high dimension ,
>computations become very long.

There are two algorithms: my excision of extremals and the Aitchison-Pascal
triangle.  The former starts with the top dimension cell and works down
while the former builds up the cocycle identities recursively from
dimension 0.

Excision of extremals was done for simplexes on page 325 of [1] resulting
in the formulas on page 330 and 331. The cubes case was done around the
same time but not published. At the end of the 1980s, Ross Moore
implemented this algorithm on a Mac; but things do get big quickly after
the cases given in [1]. For general parity complexes, see page 330 of [2]
where, even after [3], two expository mistakes remain: in the first line of
the Algorithm, "largest" should be "smallest"; on the fourth line the plus
signs should be unions; and on the fifth line the element  w  should be
chosen to be not in  "mu"(u)_(n+1).

Aitchison presented his algorithm for simplexes and cubes at the 1987
category conference in Louvain-la-Neuve, Belgium.  I explain it somewhat on
page 68 of [5]; also see page 559 of [4].  The simplex case can be obtained
from the cube case which has more symmetry.

1. The algebra of oriented simplexes, J. Pure Appl. Algebra 49 (1987) 283-335

2. Parity complexes, Cahiers topologie et géométrie différentielle
catégoriques 32 (1991) 315-343

3. Parity complexes: corrigenda, Cahiers topologie et géométrie
différentielle catégoriques  35 (1994) 359-361

4. Categorical structures, Handbook of Algebra, Volume 1  (editor M.
Hazewinkel; Elsevier Science, Amsterdam 1996; ISBN 0-444-82212-7) 529-577

5. Higher categories, strings, cubes and  simplex equations, Applied
Categorical Structures  3 (1995) 29-77 & 303

Don't be surprised that the formula was hard to imagine. John Roberts said
that no amount of staring revealed the pattern. Yet, the Aitchison-Pascal
triangle is the solution! I seem to remember Iain Aitchison got it first
for the cubes and then, by geometry, transferred to simplexes (which is
where Roberts was looking).

<== Ross

computation in CPS

[Philippe Gaucher]

Bonjour, 

Here is a question about composable pasting schemes (CPS).

In the omega-category In generated by the n-cube, is it possible to
find a kind of "general" formula for the (n-1)-source (target) of 
the n-morphism corresponding to the interior of In ? I can do 
mechanical computation in low dimension but I am not able for the
moment to imagine a formula for any dimension. In high dimension ,
computations become very long.

For example, using notations of Crans/Johnson/Street etc..., in I2, we
have (R(x) means the CPS generated by x, sometimes also denoted by (x)) : 

s_1(00)=R(-0,0+) (almost the definition in a CPS)
and t_0(-0)=s_0(0+)=-+ => s_1(00)=R(-0) o_0 R(0+) (1) because the
union is the composition in the framework of CPS. And 
t_1(00)=R(+0,0-)=R(0-) o_o R(+0) (2). Obvious with a picture.

In I3, we have : 

s_2(000)=R(-00,0+0,00-)=R(-00,0++,-0-,0+0,00-,++0)
t_0(-00)=s_0(0++) => R(-00,0++) = R(-00) o_0 R(0++)
t_0(-0-)=s_0(0+0) => R(-0-,0+0) = R(-0-) o_0 R(0+0)
t_0(00-)=s_0(++0) => R(00-,++0) = R(00-) o_0 R(++0)

and 

t_1(R(-00) o_0 R(0++)) = t_1(-00) o_0 R(0++) (axiom of omegaCat)
                       = (-0-) o_0 (-+0) o_0 (0++) with (2)
                       
s_1(R(-0-) o_0 R(0+0)) = R(-0-) o_0 s_1(0+0) (axiom of omegaCat)
                       = (-0-) o_0 (-+0) o_0 (0++) with (1)
                       
=> R(-00,0++,-0-,0+0) = R(-00,0++) o_1 R(-0-,0+0)

and in the same way, we preove that 
t_1(R(-0-,0+0))=s_1(R(00-,++0))  

=> s_2(000) =((-00) o_0 (0++)) o_1 ((-0-) o_0 (0+0)) o_1 ((00-) o_0 (++0))

For t_2(000), read the above formula from the right to the left and 
replace - by +. Almost obvious with a picture.

For I4 now : 

I have found a formula for s_3(0000)... A little bit long and not
interesting. 

For I5 : Too long. 


More generally, the question is : for a CPS, is there a way to compute 
the source and target of a R({x}) using only compositions of elements 
like R({y}) ?


Thanks in advance for your help.

pg.