5.3. Simplified signal flow graphs

5.3. Simplified signal flow graphs#

5.3.1 Rigs#

Example 5.37

The natural numbers are mentioned as a motivating example in Semiring, though they are more specifically a commutative semiring.

Example 5.38

See Boolean ring; the semiring is also mentioned on this page.

Example 5.40

See Matrix ring, which also mentions the semiring.

Exercise 5.41

For 1., the identity matrix \(I_n\).

For 2. pick n = 2 and consider the counter-example:

\[\begin{split} A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \\ B = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \\ AB = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} \neq BA = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \\ \end{split}\]

5.3.2 The iconography of signal flow graphs#

Exercise 5.43

\[\begin{split} \begin{align} a & = 16x + 4y \\ b & = x + 4y \end{align} \end{split}\]

5.3.3 The prop of matrices over a rig#

This example of a prop is discussed in PROP (category theory). See also Matrix addition / Direct sum.

Exercise 5.51

\[\begin{split} A + B = \begin{pmatrix} 3 & 3 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 5 & 6 & 1 \end{pmatrix} \\ \end{split}\]

Definition 5.50

See PROP (category theory) for a similar definition. Based on the paragraph above this one, the author is taking the objects to be the set of all vectors rather than just the plain natural numbers.

The author uses the notation of Matrix ring (which uses \(\textbf{Mat}_n(R)\)) but doesn’t provide a subscript \(n\), presumably to imply the matrices are not square.

The category \(\textbf{Mat}(R)\) is equivalent to FinRel (see that article).

5.3.4 Turning signal flow graphs into matrices#

The labeled matrix at the start of this section suggests Xarray.

In the proof of Proposition 5.54 the points (i) and (ii) are reversed relative to the two bullet points given at the start of the proof (unnecessarily, it seems).

Exercise 5.55

For 1. the relevant computation is:

\[\begin{split} \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{split}\]

For 2. the relevant computation is:

\[\begin{split} \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix} \end{split}\]

For 3., both represent the same matrix:

\[\begin{split} \begin{pmatrix} 1 & 1 & 1 \end{pmatrix} \\ \end{split}\]

5.3.5 The idea of functorial semantics#

See What is Applied Category Theory? - 1809.05923.pdf. The general idea is that a functor can provide semantic meaning (“functorial semantics”) (or an interpretation) to what is otherwise just plain syntax. For example, the functor \(S\) can make signal flow graphs into something detailed enough to be computable (matrices).

Not only that, what \(S\) means depends on the rig that backs it up. The functor can change (the meaning of the language can change) depending on your context.

The ambiguity of language - even mathematical language - is something that this book review runs into a lot. For example, what does \(ab = ba\) mean? Ideally we’d like computers to be able to make this decision by inspecting context rather than requiring us to do all the bookkeeping (e.g. through coherence conditions).

See also: