Noncommutative signal-flow graph

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

A noncommutative signal-flow graph is a directed graph used to model interconnected systems and state machines. Each edge carries a weight from a ring or semiring, which can represent things like impulse responses or symbols from an input alphabet. A source vertex v0 provides the input, and an output vertex vm is chosen to read the result. The data of the graph is S = (G = (V, E), v0, vm, f) where f assigns a weight in the ring/semiring to every edge. The associated equations may or may not have a solution; when they do, the system has a gain, an element of the ring.

Generalized gain calculation
- There are several noncommutative extensions of Mason’s rule. The most common are the forward return loop (FRL) method and its dual backward return loop (BRL) method (sometimes called Riegle’s rule).
- These methods compute the gain by combining contributions from graph paths and loops, in a way that works over noncommutative rings and over the semiring of regular expressions.
- The basic idea is to enumerate all paths from the input to the output and, for each path, form a contribution by multiplying along the path and mixing in node factors. The total gain is the sum of all path contributions, with loop gains properly incorporated. In many examples FRL and BRL give the same result.

A simple illustration
- If a graph has multiple path products from input to output, each path contributes a term to the gain. The same gain can be obtained by different but equivalent decompositions that rely on loop gains and the order of multiplications.
- Although the details can be technical, the key point is that the graph-theoretic structure (paths, loops) determines the gain.

From signals to matrices
- When variables naturally group into layers, they can be packed into vectors, turning the scalar graph into a matrix signal-flow graph. This often simplifies the representation and makes the input–output map easy to read.
- In the matrix form, a single path and a single loop can give a compact description of the whole system's behavior.

Finite-state automata and regular expressions
- A fundamental kind of noncommutative signal-flow graph is a finite-state automaton over an alphabet Σ.
- Serial connections correspond to concatenation of words; parallel connections correspond to union (A + B); self-loops correspond to the Kleene star (repetition).
- These constructions mirror the semiring of regular expressions, where combining a finite set of words builds up the language accepted by the automaton.
- A deterministic automaton uses the return-loop method to accumulate contributions from all paths (words). The gain of the graph in this case is the sum of these path contributions, i.e., the language recognized by the automaton.