Noncommutative signal-flow graph

In automata theory and control theory, branches of mathematics, theoretical computer science and systems engineering, a noncommutative signal-flow graph is a tool for modeling interconnected systems and state machines by mapping the edges of a directed graph to a ring or semiring.
A single edge weight might represent an array of impulse responses of a complex system (see figure to the right), or a character from an alphabet picked off the input tape of a finite automaton, while the graph might represent the flow of information or state transitions.
As diverse as these applications are, they share much of the same underlying theory.
Definition.
Consider "n" equations involving "n"+1 variables {"x"0, "x"1...,"x"n}.
with "a"ij elements in a ring or semiring "R". The free variable "x"0 corresponds to a source vertex "v"0, thus having no defining equation. Each equation corresponds to a fragment of a directed graph "G"=("V","E") as show in the figure.
The edge weights define a function "f" from "E" to "R". Finally fix an output vertex "vm". A signal-flow graph is the collection of this data "S" = ("G"=("V","E"), "v0","vm" formula_2 "V", "f" : "E" → "R"). The equations may not have a solution, but when they do,
with "T" an element of "R" called the gain.
Return Loop Method.
There exist several noncommutative generalizations of Mason's rule. The most common is the return loop method (sometimes called the forward return loop method (FRL), having a dual backward return loop method (BRL)). The first rigorous proof is attributed to Riegle, so it is sometimes called Riegle's rule.
As with Mason's rule, these gain expressions combine terms in a graph-theoretic manner (loop-gains, path products, etc.). They are known to hold over an arbitrary noncommutative ring and over the semiring of regular expressions.
Formal Description.
The method starts by enumerating all paths from input to output, indexed by "j" formula_2 "J". We use the following definitions:
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:
so the total gain is
An Example.
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):
Multiplying its node factor and path weight, its gain contribution is
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 "Td", the alternating product of node factors and path weights, we obtain two gain expressions:
and
These values are easily seen to be the same using identities ("ab")−1 = "b"−1"a"−1 and "a"(1-"ba")−1=(1-"ab")−1"a".
Applications.
Matrix Signal-Flow Graphs.
Consider equations
and
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"1,"x"2)"t"
"y"=("y"1,"y"2)"t" and
"z"=("z"1,"z"2)"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
Finite Automata.
An important kind of noncommutative signal-flow graph is a finite state automaton over an alphabet formula_15.
Serial connections correspond to the concatenation of words, which can be extended to subsets of the free monoid formula_16. For "A", "B" formula_17
Parallel connections correspond to set union, which in this context is often written "A"+"B".
Finally, self-loops naturally correspond to the Kleene closure
where formula_20 is the empty word. The similarity to the infinite geometric series
is more than superficial, as expressions of this form serve as 'inversion' in this semiring.
In this way, the subsets of formula_16 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 formula_16 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:
Thus the language accepted by this automaton (the gain of its signal-flow graph) is the sum of these terms