This is part of the Tutorial: Graphic lambda calculus.

Here are described the moves directly related to the \Upsilon gate.

  • CO-COMM move.  This is the local move depicted in the following figure


It means we may permute the outputs of a \Upsilon gate. The name means “co-commutativity”, because the diagram resembles to the one of the commutativity property, with the exception of the arrows orientations, which are in opposite directions (hence “co-“).

  • CO-ASSOC move. This is a local move, described by the next figure


It has the following effect: by using CO-ASSOC moves, we may move between any two binary trees formed only with \Upsilon gates, with the same number of output leaves. The name means “co-associativity” and the explanation is similar to the previous one, with “commutativity” replaced by “associativity”.

  •   GLOBAL FAN-OUT. This is a global move, because it involves a modification of an arbitrary number of nodes (gates) and arrows.

Precisely, the move acts like in the following picture: if A is a graph in GRAPH  then we may replace the graph A connected to an \Upsilon  gate by two copies of A.


GLOBAL FAN-OUT implies CO-COMM  (namely two GLOBAL FAN-OUT moves have the effect of one CO-COMM move).  The move CO-COMM is not useless though: we may choose to work in a sector of the graphic lambda calculus which uses CO-COMM but not GLOBAL FAN-OUT.

There is a variant of this move which is local.

  • LOCAL FAN-OUT. Fix a number N and consider only graphs A which have at most N (nodes + arrows). The N LOCAL FAN-OUT move is the same as the GLOBAL FAN-OUT move, only it applies only to such graphs A.

LOCAL FAN-OUT does not imply CO-COMM.

Important remark: The gate \Upsilon is really a fan-out gate only in the sense described by the FAN-OUT moves. In the absence of one of this moves, the gate cannot  be described as a “fan-out”. The “fan-out” is in the moves, not in the gate.



Return to Tutorial: Graphic lambda calculus


19 thoughts on “Fan-out moves: CO-COMM, CO-ASSOC, GLOBAL FAN-OUT, LOCAL FAN-OUT”

Leave a Reply

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

You are commenting using your 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