Noncommutative signal-flow graph

The method starts by enumerating all paths from input to output, indexed by j ${\displaystyle \in }$ J. We use the following definitions:

• The j-th path product is (by abuse of notation) a tuple of k_j edge weights along it:

${\displaystyle p_{j}=(w_{k_{j}}^{(j)},\ldots ,w_{2}^{(j)},w_{1}^{(j)}).}$

• To split a vertex v is to replace it with a source and sink respecting the original incidence and weights (this is the inverse of the graph morphism taking source and sink to v).
• The loop gain of a vertex v w.r.t. a subgraph H is the gain from source to sink of the signal-flow graph split at v after removing all vertices not in H.
• Each path defines an ordering of vertices along it. The along path j, the i-th FRL (BRL) node factor is (1-S_i^(j))⁻¹ where S_i^(j) is the loop gain of the i-th vertex along the j-th w.r.t. the subgraph obtained by removing v₀ and all vertices ahead of (behind) it.

The contribution of the j-th path to the gain is the product along the path, alternating between the path product weights and the node factors:

${\displaystyle T_{j}=\prod _{i=k_{j}}^{1}(1-S_{i}^{(j)})^{-1}w_{i}^{(j)},}$

so the total gain is

${\displaystyle T=\sum _{j\in J}T_{j}.}$

A noncommutative signal-flow graph from x to z

Consider the signal-flow graph shown. From x to z, there are two path products: (d) and (e,a). Along (d), the FRL and BRL contributions coincide as both share same loop gain (whose split reappears in the upper right of the table below):

${\displaystyle f+e(1-b)^{-1}c,}$

Multiplying its node factor and path weight, its gain contribution is

${\displaystyle T_{d}=\left[1-f-e(1-b)^{-1}c\right]^{-1}d.}$

Along path (e,a), FRL and BRL differ slightly, each having distinct splits of vertices y and z as shown in the following table.

Adding to T_d, the alternating product of node factors and path weights, we obtain two gain expressions:

${\displaystyle T^{(FRL)}=\left[1-f-e(1-b)^{-1}c\right]^{-1}d+\left[1-f-e(1-b)^{-1}c\right]^{-1}e(1-b)^{-1}a,}$

and

${\displaystyle T^{(BRL)}=\left[1-f-e(1-b)^{-1}c\right]^{-1}d+(1-f)^{-1}e\left[1-b-c(1-f)^{e}\right]^{-1}a,}$

These values are easily seen to be the same using identities (ab)⁻¹ = b⁻¹a⁻¹ and a(1-ba)⁻¹=(1-ab)⁻¹a.

Consider equations

${\displaystyle y_{i}=\sum _{j=1}^{2}a_{ij}x_{j}+\sum _{j=1}^{2}b_{ij}y_{j}}$

and

${\displaystyle z_{i}=\sum _{j=1}^{2}c_{ij}y_{j},}$

This system could be modeled as scalar signal-flow graph with multiple inputs and outputs. But, the variables naturally fall into layers, which can be collected into vectors x=(x₁,x₂)^t y=(y₁,y₂)^t and z=(z₁,z₂)^t. This results in much simpler matrix signal-flow graph as shown in the figure at the top of the article.

Applying the forward return loop method is trivial as there's a single path product (C,A) with a single loop-gain B at y. Thus as a matrix, this system has a very compact representation of its input-output map

${\displaystyle T=C(1-B)^{-1}A.}$

Representation of a finite automaton as a (noncommutative) signal flow graph over a semiring.

An important kind of noncommutative signal-flow graph is a finite state automaton over an alphabet ${\displaystyle \Sigma }$.[3][4]

Serial connections correspond to the concatenation of words, which can be extended to subsets of the free monoid ${\displaystyle \Sigma ^{*}}$. For A, B ${\displaystyle \subseteq \Sigma ^{*}}$

${\displaystyle A\cdot B=\{ab\mid a\in A,b\in B\}.}$

Parallel connections correspond to set union, which in this context is often written A+B.

Finally, self-loops naturally correspond to the Kleene closure

${\displaystyle A^{*}=\{\lambda \}+A+AA+AAA+\cdots ,}$

where ${\displaystyle \lambda }$ is the empty word. The similarity to the infinite geometric series

${\displaystyle (1-x)^{-1}=1+x+x^{2}+x^{3}\cdots ,}$

is more than superficial, as expressions of this form serve as 'inversion' in this semiring.[7]

In this way, the subsets of ${\displaystyle \Sigma ^{*}}$ built of from finitely many of these three operations can be identified with the semiring of regular expressions. Similarly, finite graphs whose edges are weighted by subsets of ${\displaystyle \Sigma ^{*}}$ can be identified with finite automata, though generally that theory starts with singleton sets as in the figure.

This automaton is deterministic so we can unambiguously enumerate paths via words. Using the return loop method, path contributions are:

• path ab, has node factors (c^*, ${\displaystyle \lambda }$), yielding gain contribution

${\displaystyle ac^{*}b,}$

• path ada, has node factors (c^*, c^*, ${\displaystyle \lambda }$), yielding gain contribution

${\displaystyle ac^{*}dc^{*}a,}$

• path ba, has node factors (c^*, ${\displaystyle \lambda }$), yielding gain contribution

${\displaystyle bc^{*}a.}$

Thus the language accepted by this automaton (the gain of its signal-flow graph) is the sum of these terms

${\displaystyle L=ac^{*}b+ac^{*}dc^{*}a+bc^{*}a.}$