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[1] 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),[2] or a character from an alphabet picked off the input tape of a finite automaton,[3] while the graph might represent the flow of information or state transitions.

with aij elements in a ring or semiring R. The free variable x0 corresponds to a source vertex v0, thus having no defining equation.

[6] As with Mason's rule, these[clarification needed] gain expressions combine terms in a graph-theoretic manner (loop-gains, path products, etc.).

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−1a−1 and a(1-ba)−1=(1-ab)−1a.

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=(x1,x2)t y=(y1,y2)t and z=(z1,z2)t. This results in much simpler matrix signal-flow graph as shown in the figure at the top of the article.

Thus as a matrix, this system has a very compact representation of its input-output map: An important kind of noncommutative signal-flow graph is a finite state automaton over an alphabet

can be identified with finite automata, though generally that theory starts with singleton sets as in the figure.

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