Zipper logic (VI) latest version, detailed

Zipper logic is a graph rewrite system. It consists in a class of graphs, called zipper graphs and a collection of moves (graph rewrites) acting on zipper graphs.

Let’s start by defining the zipper graphs. Such a graph is made by the basic ingredients described in the next two figures.

First there are two types of half-zippers and one type of zipper.  For any natural number n there is a (-n) half-zipper (first row), a (+n) half-zipper and a  (n) zipper.

define_nodes_1

At the right you see that these are just nodes with oriented arrows. At the left you see a more intuitive notation, which will be used further.

The numbering of the arrows indicate that there is an order on those arrows.

Besides the half-zippers and zippers, there are the already familiar nodes (a) fanout, (b) fanin  from chemlambda. To them, we add (c) arrows, termination nodes and loops.

4_chem

A zipper graph is formed by a finite number of those ingredients, which are connected according to the arrow orientations. Note that there might be arrows with one, or both ends free, and that a zipper graph does not have to be connected.

The zipper moves, now.  There are the TOWER moves, which serve to stack half-zippers on top of others.

zipper_not_2

There is the CLICK move, described in the next figure for a particular case. In general, the CLICK moves creates a zipper from two opposed half-zippers, possibly also with a rest, which is a half zipper. It is very intuitive.

click

You shall see later that CLICK is a very funny move, one which formalizes the identification of a pattern.

The ZIP move is the one which gives the name to zipper logic. It looks like the action of zipping or unzipping a zipper.

zip

The composite CLICK + ZIP plays the role of the graphic beta move, but here is a more subtle thing: CLICK is like identifying the good pattern for the graphic beta move and ZIP is like actually applying the graphic beta move.

Then you have the DIST moves, like in chemlambda, but for half-zippers:

zip_dist

And then there are the LOCAL PRUNING moves, some for half-zippers and other just like those in chemlambda.

convention_4

Finally,  there are some moves (among them the very important FAN-IN move) which involve only the familiar nodes from chemlambda.

convention_3

That’s it!

It looks very much like chemlambda, right? That is true, with the subtlety of CLICK added, which is exploited when we find models of the zipper logic outside chemlambda.

________________________________________

About these ads

4 thoughts on “Zipper logic (VI) latest version, detailed”

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s