This is part of the Tutorial: Graphic lambda calculus.
Here are described the moves directly related to the gate.
- CO-COMM move. This is the local move depicted in the following figure
It means we may permute the outputs of a 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 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 is a graph in then we may replace the graph connected to an gate by two copies of .
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 and consider only graphs which have at most (nodes + arrows). The LOCAL FAN-OUT move is the same as the GLOBAL FAN-OUT move, only it applies only to such graphs .
LOCAL FAN-OUT does not imply CO-COMM.
Important remark: The gate 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”