Span(Graph) I
Next Span(Graph) post.
I have decided to write a series of tutorial posts about Span(Graph) since I think this work has been unfairly neglected. I am simultaneously introducing a little TeX into the blog, at the encouragement of Keith Harbaugh.
We begin with a simpler category as an algebra of straight line circuits which we will use as motivation for then in a later post introducing ${\bf Span}({\bf Graph})$.
Straight-line Boolean circuits.
Straightline Boolean circuits are constructed from components $and$, $or$, and $not$, connected by wires but without feedback. An example:
There is an algebra in which such a circuit may be described as an expression. The algebra is a category with extra operations.
The objects of the category are sets of the form $B^n=\{0,1\}^n$, the arrows of the category are all the functions between these sets, composition is composition of functions. We may represent an arrow in the category $B^m\to B^n$ as a box with $m$ input wires and $n$ output wires.
Already in the picture above I have represented the basic components $and$, $or$ and $not$ as (special shaped) boxes with input and output wires.
Now composition in the algebra corresponds to joining all the output wires of one component to all the input wires of the next. The algebra has another important operation and some constants.
The product of arrows: Given $f:B^m\to B^n$ and $g:B^k\to B^l$ the product of $f$ and $g$, denoted $f\times g$ is an arrow from $B^{m+k}$ to $B^{n+l}$ which applied to an $m+k$ tuple $(x_1,x_2,\cdots,x_m,y_1,\cdots,y_k)$ gives $(f(x_1,x_2,\cdots,x_m),g(y_1,\cdots,y_k)) $. The picture of $f\times g$ is that of $f$ and $g$ side by side. In the case $m=2$, $n=3 $, $k=3 $, $l=1 $ we have $5$ inputs and $3$ outputs:
The extra constants are operations on wires that allow the circuit to be built up. They are $1_B:B\to B$ (a single wire), $twist:B^2\to B^2$ (a twist of wires), $\Delta:B\to B^2$ (splitting of a wire) and the unique function $B\to B^0=1$ (the cutting of a wire). As functions the are defined by $1_B(x)=x$, $twist(x,y)=(y,x)$, $\Delta(x)=(x,x)$.
They are pictured as:
Now consider dividing up of the circuit above as indicated in the picture below. The circuit is a composite of the parts between the dotted lines, each of which parts may be expressed using product in terms of the basic components and the constants.
The algebraic expression for the circuit is the composition of first $\Delta\times 1_B\times 1_B$, then $\neg\times twist \times1_B $, then $\vee\times \& $ and finally $\&$, that is (composing from the left)
$(\Delta\times 1_B\times 1_B)(\neg\times twist \times 1_B )(\vee\times \&)(\&)$.
The evaluation of this expression in the category yields a function $B^3\to B$ which is the input/output behaviour of the circuit. In fact the input/output function of this circuit is $f(x,y,z)=x\& (y\& z)$ and so the circuit is equal to a simpler circuit with two $and$ gates.
There are various other things that could be said at this point but I will mention only briefly that (i) every arrow in this category is the input/output behaviour of a circuit, (ii) the extra operations and constants are exactly those of a category with products, (iii) the equations between expressions are exactly those which are valid in a category with products, plus the Boolean algebra equations satisfied by the basic components.
The category we have described does not allow components with internal state, delay, feedback. It is to introduce these elements that we will introduce in the next post ${\bf Span}({\bf Graph})$.
I have decided to write a series of tutorial posts about Span(Graph) since I think this work has been unfairly neglected. I am simultaneously introducing a little TeX into the blog, at the encouragement of Keith Harbaugh.
We begin with a simpler category as an algebra of straight line circuits which we will use as motivation for then in a later post introducing ${\bf Span}({\bf Graph})$.
Straight-line Boolean circuits.
Straightline Boolean circuits are constructed from components $and$, $or$, and $not$, connected by wires but without feedback. An example:
There is an algebra in which such a circuit may be described as an expression. The algebra is a category with extra operations.
The objects of the category are sets of the form $B^n=\{0,1\}^n$, the arrows of the category are all the functions between these sets, composition is composition of functions. We may represent an arrow in the category $B^m\to B^n$ as a box with $m$ input wires and $n$ output wires.
Already in the picture above I have represented the basic components $and$, $or$ and $not$ as (special shaped) boxes with input and output wires.
Now composition in the algebra corresponds to joining all the output wires of one component to all the input wires of the next. The algebra has another important operation and some constants.
The product of arrows: Given $f:B^m\to B^n$ and $g:B^k\to B^l$ the product of $f$ and $g$, denoted $f\times g$ is an arrow from $B^{m+k}$ to $B^{n+l}$ which applied to an $m+k$ tuple $(x_1,x_2,\cdots,x_m,y_1,\cdots,y_k)$ gives $(f(x_1,x_2,\cdots,x_m),g(y_1,\cdots,y_k)) $. The picture of $f\times g$ is that of $f$ and $g$ side by side. In the case $m=2$, $n=3 $, $k=3 $, $l=1 $ we have $5$ inputs and $3$ outputs:
The extra constants are operations on wires that allow the circuit to be built up. They are $1_B:B\to B$ (a single wire), $twist:B^2\to B^2$ (a twist of wires), $\Delta:B\to B^2$ (splitting of a wire) and the unique function $B\to B^0=1$ (the cutting of a wire). As functions the are defined by $1_B(x)=x$, $twist(x,y)=(y,x)$, $\Delta(x)=(x,x)$.
They are pictured as:
Now consider dividing up of the circuit above as indicated in the picture below. The circuit is a composite of the parts between the dotted lines, each of which parts may be expressed using product in terms of the basic components and the constants.
The algebraic expression for the circuit is the composition of first $\Delta\times 1_B\times 1_B$, then $\neg\times twist \times1_B $, then $\vee\times \& $ and finally $\&$, that is (composing from the left)
$(\Delta\times 1_B\times 1_B)(\neg\times twist \times 1_B )(\vee\times \&)(\&)$.
The evaluation of this expression in the category yields a function $B^3\to B$ which is the input/output behaviour of the circuit. In fact the input/output function of this circuit is $f(x,y,z)=x\& (y\& z)$ and so the circuit is equal to a simpler circuit with two $and$ gates.
There are various other things that could be said at this point but I will mention only briefly that (i) every arrow in this category is the input/output behaviour of a circuit, (ii) the extra operations and constants are exactly those of a category with products, (iii) the equations between expressions are exactly those which are valid in a category with products, plus the Boolean algebra equations satisfied by the basic components.
The category we have described does not allow components with internal state, delay, feedback. It is to introduce these elements that we will introduce in the next post ${\bf Span}({\bf Graph})$.
Labels: computing
posted by Unknown at 2:35 AM
4 Comments:
Very interesting, and with TeX it looks very nice. I'm looking for next posts
Interesting post; thanks!
Could you please elaborate a bit more on:
"(iii) the equations between expressions are exactly those which are valid in a category with products, plus the Boolean algebra equations satisfied by the basic components."?
Is there an easy way to see that [I] the basic components and constants generate all functions between sets of the form $B^n$, and that [II] if two circuits are equivalent they are equivalent by the equations of categories with products and Boolean algebras?
My vague understanding of logic circuits makes me believe this, but I'm wondering if there is a slick argument showing this is true, and if this categorical/diagrammatic perspective has anything to contribute.
The proof of [I] is straightforward. Functions from $B^n$ to $B$ can be given by Boolean expressions and Boolean expressions can be converted into expressions in the categorical algebra (see for example my book Categories and Computer Science, Cambridge UP). Assertion [II] is the fact that the Lawvere theory of Boolean algebras is the category I described. I would have to think about a slick proof. Regarding the advantages of the categorical algebra: it certainly makes
explicit the relation of the algebra and the geometry of circuits, and it is that which I want to exploit with the more general algebra of finite state processes (automata) $Span(Graph)$. On the other hand for straight line Boolean circuits traditional Boolean algebra is quite adequate.
Thanks for the reference and extra context. Looking forward to the rest of this series.
Post a Comment
<< Home