Intermezzo (small graph rewrite systems)

Between the last post on small graph rewrite systems and a new one to follow, here are some other, real world examples of such systems.

Where is this from? Answer: M. Khovanov,   New geometrical constructions in low-dimensional topology, preprint 1990, fig. 20


Where is this from? Answer: L.H. Kauffman, Knots and Physics, World Scientific 1991, p. 336.


How can we put this in order?

Small graph rewrite systems (3)

Previous posts on the same subject are (1) (2). Related is this post.

In this post I update the small rewrite system SH-2.1 to SH-2.2.  If you look at SH-2.1, it has 3 rewrites: SH, GL and RM.

None of these rewrites allow two “sticks” to merge or one stick to transform into a ring.

Compare with the interaction combinators inspired IC-2.1, with the rewrites DIST, RW1 and RW2. Is true, that system is too reactive, but it has one rewrite, namely RW2, which allows two sticks to merge.

A rewrite which has this property (sticks merge) is essential for computational purposes. The most famous of such rewrites is the BETA rewrite in lambda calculus, or the \gamma \gamma and the \delta \delta rewrites from interaction combinators:


(figure from Lafont article).

In the oriented sticks and rings version of chemlambda we have the rewrites BETA (or A-L) and FI-FOE, with the same property.



We shall modify therefore one of the rewrites from SH-2.1.

The SH-2.2 system

We keep the rewrites SH and GL from the SH-2.1 system:




and we replace the rewrite RM with the new rewrite R2:


The new rewrite R2 needs a ring!

Let’s show that SH-2.2 is better than SH-2.1. All we need is to be able to do the rewrite RM from SH-2.1 in SH-2.2. Here is it.


Mind that the ring from the upper right graph is not the same as the ring from the bottom graph. Indeed, in the rewrite R2 the ring from the bottom is consumed and  a new ring appears from the merging of the ends of the stick with two blue nodes which sits on the top of the other stick with two yellow ends from the bottom graph.

Compared with the original RM rewrite


we have an extra ring at the left and at the right of the rewrite RM, as it appears in SH-2.2. Otherwise said the ring plays the role of an enzyme.






Data, channels, contracts, rewrites and coins

We can think about all these in terms of dimension.

Data are  like points, 0 dimensional.

Channels (of communication) are 1-dimensional. They are the fundamental bricks of IT. They are not enough, though.

Contracts are 2-dimensional. A contract is an algorithm over channels.

As an example, here’s how we can turn a graph rewrite system in the  sticks and rings version  into a contract-like one.

For the (oriented) sticks and rings version of chemlambda see this. Two small rewrite systems involving non-oriented sticks are described here  and there.

The closest algorithm relevant for this post is the one from needs.  I shall mention in ths post names from there, like  “succ”, “ccus”, “gamma” and “ammag”.

We can descrine a sticks and rings graph with two invertible functions. Each node of a trivalent graph is decomposed as two half-nodes. Indees, cut a trivalent node  in half, you get a half-node with one half-edge  (this is type  I half-node) and another half-node with two half-edges (this is type II half-node).   Each stick has two ends which are type I half-nodes and it is a list which starts and ends with type I half-nodes and contains  otherwise only type II hald-nodes. A ring is a circular list made of type II half-nodes.

Succ and it’s inverse ccus is the function (permutation) which for any half-node from a  stick or ring gives the sucessor half-node, if any (or the predecessor half-node  in the case of ccus).

Gamma and it’s inverse  ammag is the function (permutation) which pairs each type I half-node with it’s type  II other half-node.

The new thing here is that we shall think about half-nodes as names of channels in an asynchronous pi-calculus.

In the needs algorithm the rewrites (which are  conservative in the number of half-nodes) are small permutations of half-nodes. The gamma-ammag function is passive, in the sense that it never changes.   The rewrites are  random.

In the version I   propose here   each half-node is a unidirectional channel which can be used to communicate other channels names and some data. In the case of the graph rewrite systems we discuss here the other data is the color of the (half-)node.

In the case of chemlambda strings we  need a bit for the half-node type and 2 bits for the colors. As a (half) tongue-in-cheek I used DNA or RNA like encoding, like in this screen casting, to turn a mol file into the sticks and rings version.


In the version proposed here we  change the algorithm of random application of a rewrite with an algorithm which involves only communication via the channels  associated with the half-nodes.

Here is  the description of a SH rewrite


Each  stick is the property of somebody (A, B, C, D, …), say an actor. A stick is a list of  channels names.  So the data (0-dim) are the channels names, organized in lists which are managed by actors.

Actors can send messages through channels and also they can edit their list.

A rewrite, here the SH,  is an contract, i.e. an algorithm which describes how to achieve the rewrite via communication and editing of list, such that each actor can locally  execute it’s part.

But how can we  read  such a contract? In many ways, because the formalism is so general. For example: B and D exchange C in the place A, witnessed by the notary node e1.

Then what can be the pairs  yellow-blue and blue-blue? Recall that originally the SH rewrite is


Well, coins? Or coin (yellow-blue) and gas (blue-blue)?  Or receipts? Imagination is the limit and all can be made  in practice. If you are interested to make it real contact me.


Small graph rewrite systems (2)

I continue from the last post on small graph rewrite systems. Let’s see some more details about the SH-2.1 system.

The last post ends with a realization of the DIST rewrite in SH-2.1. We can do better than that, by showing that the DIST rewrite is reversible:




As you see, the two pairs yellow-blue and blue-blue play the role  of enzymes.

Another two interesting reactions are the following:


So the “yellow ends” duplicate, with a pair blue-blue as an enzyme.



The supplementary “blue ends” prune themselves, in a sort  of duality  with the “yellow ends”. This time there is a yellow-blue pair enzyme.


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 port named “1”, a 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.]

9-quine string animation

I use the chemlambda strings version to show  how the 9-quine works. [What is a quine in chemlambda? See here.]





The 9-quine is the smallest quine in chemlambda which does not have a termination node.  There exist smaller quines if the termination node is admitted. For example  the chemlambda equivalent of a quine from Interaction Combinators  which appears in Lafont’ foundational article.

As you see this version is conservative and there are no enzymes.

I shall come back with a post which explains why and how the 9-quine dies. It is of course due to the conflicts in chemlambda, see the examples from the page on chemlambda v2.

What I do according to ADS search

ArXiv  links to the Astrophysics  Data System, which got a new fancy look. It may be a bit heavy, as a supporter of the wonderful arXiv I would rather applaud if they would allow me to put articles with animations inside, be them only animated gifs. But is nevertheless interesting.

So if I go to my arXiv articles, choose an article and then click on NASA ADS link on the right panel, then I get this page.  Funny that they don’t use the Journal Reference from the arXiv to decide which article is “refereed”, i.e. peer reviewed, even if peer review is less than validation.

I am very pleased though   about the visual representation of what I do, as seen from the arXiv articles.


This is the image which tells how many articles I have on certain keywords, as well as links between keywords which are proportional with the number of the articles which fit a pair of keywords.

TBH this is the first time a neutral bibliometric system  shows an accurate image of my work.

The darker blue sector, which has no words on it is related to variational methods in fracture, Mumford-Shah and convexity articles.

The same picture, but according to the downloads in the last 90 days, is this one.


This is also very satisfying because the hamiltonian/information/… has a big future. For the moment it looks unrelated to the other sectors, but wait for the kaleidos project 🙂

The em-convex rewrite system, where I guess I found the equivalent of the Church numbers for space, is in the dilatation structures/…/selfsimilar sector. In my opinion, important subject.