Small graph rewrite systems (I)

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 $\gamma$ and $\delta$ combinators. We shall not use the combinators with only one port.

The IC-2.1 system

The $\gamma \delta$  rewrite will be like a DIST rewrite from chemlambda, only unoriented.

Then, the $\gamma \gamma$ looks like this

and finally the $\delta \delta$ 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.]

Distributivity move as a transposition (curious crossings II)

It looks that there is a connection of the following with the research on DNA topology, but I shall comment on this in a future post, mainly because I am learning about this right now. (But another main reference is Louis Kauffman.)

Let’s see.

If I am using this encoding of chemlambda nodes with crossings

which is a variant of the encoding from Curious crossings   then, as in the mentioned post,   the beta move becomes a CLICK between “sticky ends” which are marked with dashed lines, followed by R2b move, and also the FAN-IN move becomes a CLICK between sticky ends, followed by a R2a move.

What about the DIST moves? Let’s take the DIST move which involves an application node and a fanout node. The move looks like this:

(Click on the picture to make it bigger.)

In the right column we see the DIST move with chemlambda drawing conventions. In the left column there is the translation with crossings and sticky ends.

What do we see? The strings 1-5 and 6-3 are transposed by the DIST move and a new string appears, which crosses them.

I can draw the same move like this:

In this figure, the left column is as before, but the right column has changed. I just kept the order, from left to right, of the strings 6-3 and 1-5, and I wiggled the string 2-4 for this.

This is starting to look interestingly alike some other pictures from  DNA topology.

___________________________________________