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.

 

int-combs-dist

Then, the \gamma \gamma looks like this

int-combs-rw1

and finally the \delta \delta may be seen like this

int-combs-rw2

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:

2cols-sh

Then we add a “glue” rewrite

2cols-gl

and a “remove” rewrite

 

2cols-rm

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:

 

2cols-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.]

3 thoughts on “Small graph rewrite systems (I)”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s