What happens if we use the sticks and rings description of oriented fatgraphs, like in this post, but we drop the orientation? Moreover, what if we use as few colors as possible and as few rewrites as possible?

For the sticks and rings version of chemlambda see this.

If we have oriented edges then the sticks and rings image is equivalent with the usual oriented trivalent fatgraph. But if we drop the edges orientation something interesting happens. The trivalent nodes become invertible. Indeed, take for example, with the notations from chemlambda, a node as seen in a mol file:

A 1 2 3

It means that we have a node “A” (i.e. application) with a left.in port named “1”, a right.in port named “2” and a out port named “3”. To get a more precise idea, think about “1” as a term “T_1”, about “2” as a term “T_2” and about “3” as the term “T_1 T_2”.

In the sticks and rings version there is an edge which connects “1” and “3”, which is perhaps part of a stick (which has two ends) or a ring (which has none). “1” and “3” appear as marks on that stick (or ring) and the stick (or ring) has an orientation so that the successor of “1” is “3”.

Another stick, which ends with the mark “2” and the node “A”, is glued between the marks “1” and “2”.

For a node like

FO 1 2 3

(i.e. a fanout) the oriented stick passes from “1” to “3” but this time the second stick starts with the node “FO” and the mark “2”.

Now, if we drop the sticks orientations, it means that we can no longer discern between say “A 1 2 3” and “A 3 2 1”. As an expression which depends on the port “2”, we can go from “1” to “3” as easily as we go from “3” to “1”, so it looks invertible.

As a first try let’s see how does a non-oriented sticks and rings version of Lafont interaction combinators look like. We need only two colors, to discern between the and combinators. We shall not use the combinators with only one port.

**The IC-2.1 system**

The rewrite will be like a DIST rewrite from chemlambda, only unoriented.

Then, the looks like this

and finally the may be seen like this

As you see all rewrites are made conservative in the number of nodes, by the addition of supplementary 2-nodes sticks, call them “pairs” from now.

Now we have some problems:

- the RHS of the DIST rewrite contains the pattern from the LHS if we add another pair yellow-blue. That is bad because it means we can continue indefinitely the same rewrite if we have enough yellow-blue pairs at our disposal
- practically almost any sticks and rings graph is extremely reactive, because any combination of nodes colors which are neighbours on a stick or ring will trigger a rewrite. Question: which are the graphs which are fully reduced?
- if we look back to Lafont interaction combinators, then we see that our system has more rewrites than the original. Indeed, that is because the non-oriented sticks and rings image is ambiguous, not equivalent with the interaction combinators. This explains the abundance of patterns for reduction.

**The SH-2.1 system**

Let’s try another rewrite system, non-oriented sticks and rings and two colors. We’ll take the shuffle trick rewrite as basic, this time:

Then we add a “glue” rewrite

and a “remove” rewrite

Now we are in the realm of emergent algebras, with the yellow node as a generic dilation and the blue node as a fanout (more about this later). We can do lots of funny things with this small system, for example we can do a DIST:

There is a remarkable behaviour here. Look at the pair blue-blue, you have it at the left of the “simulated” DIST and at the right of it.

The pair blue-blue behaves like an enzyme!

[Continues with this post.]

## 4 thoughts on “Small graph rewrite systems (I)”