Noncommutative signal-flow graph

Last updated
A multi-input, multi-output system represented as a noncommutative matrix signal-flow graph. Matrix Signal-Flow Graph.png
A multi-input, multi-output system represented as a noncommutative matrix 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.

Contents

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.

As diverse as these applications are, they share much of the same underlying theory. [4] [5]

Definition

Signal-flow graph fragment. Signal-Flow Graph Fragment.png
Signal-flow graph fragment.

Consider n equations involving n+1 variables {x0, x1,...,xn}.

with aij elements in a ring or semiring R. The free variable x0 corresponds to a source vertex v0, 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,vmV, f : ER). 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 [2] noncommutative generalizations of Mason's rule.[ clarification needed ] 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[ clarification needed ] is attributed to Riegle, [2] so it is sometimes called Riegle's rule. [6]

As with Mason's rule, these[ clarification needed ] 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. [5]

Formal Description

The method[ clarification needed ] starts by enumerating all paths from input to output,[ clarification needed ] indexed by jJ. We use the following definitions:

[ clarification needed ]

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

A noncommutative signal-flow graph from x to z FRL BRL Example.png
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):

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.

Return Loop Split Table.png

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.

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=(x1,x2)ty=(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.

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

Representation of a finite automaton as a (noncommutative) signal flow graph over a semiring. Automaton as Signal-Flow Graph.png
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 . [3] [4]

Serial connections correspond to the concatenation of words, which can be extended to subsets of the free monoid . For A, 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

where 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. [7]

In this way, the subsets of 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 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

See also

Notes

  1. Lorens 1964.
  2. 1 2 3 Riegle & Lin 1972.
  3. 1 2 Brzozowski & McCluskey 1963.
  4. 1 2 Book et al. 1971.
  5. 1 2 Pliam & Lee 1995.
  6. Andaloussi, Chalh & Sueur 2006, pp. 2962.
  7. Kuich & Salomaa 1985.

Related Research Articles

<span class="mw-page-title-main">Shortest path problem</span> Computational problem of graph theory

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects are represented by abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

In mathematics, especially representation theory, a quiver is another name for a multidigraph; that is, a directed graph where loops and multiple arrows between two vertices are allowed. Quivers are commonly used in representation theory: a representation V of a quiver assigns a vector space V(x) to each vertex x of the quiver and a linear map V(a) to each arrow a.

<span class="mw-page-title-main">Cayley graph</span> Graph defined from a mathematical group

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing expander graphs.

<span class="mw-page-title-main">Maximum flow problem</span> Computational problem in graph theory

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA. An FSA defines a formal language by defining a set of accepted strings, while an FST defines a relation between sets of strings.

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.

<span class="mw-page-title-main">Bethe lattice</span>

In statistical mechanics and mathematics, the Bethe lattice is an infinite connected cycle-free graph where all vertices have the same number of neighbors. The Bethe lattice was introduced into the physics literature by Hans Bethe in 1935. In such a graph, each node is connected to z neighbors; the number z is called either the coordination number or the degree, depending on the field.

In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method.

<span class="mw-page-title-main">Centrality</span> Degree of connectedness within a graph

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

Mason's gain formula (MGF) is a method for finding the transfer function of a linear signal-flow graph (SFG). The formula was derived by Samuel Jefferson Mason, for whom it is named. MGF is an alternate method to finding the transfer function algebraically by labeling each signal, writing down the equation for how that signal depends on other signals, and then solving the multiple equations for the output signal in terms of the input signal. MGF provides a step by step method to obtain the transfer function from a SFG. Often, MGF can be determined by inspection of the SFG. The method can easily handle SFGs with many variables and loops including loops with inner loops. MGF comes up often in the context of control systems, microwave circuits and digital filters because these are often represented by SFGs.

A signal-flow graph or signal-flowgraph (SFG), invented by Claude Shannon, but often called a Mason graph after Samuel Jefferson Mason who coined the term, is a specialized flow graph, a directed graph in which nodes represent system variables, and branches represent functional connections between pairs of nodes. Thus, signal-flow graph theory builds on that of directed graphs, which includes as well that of oriented graphs. This mathematical theory of digraphs exists, of course, quite apart from its applications.

Bass–Serre theory is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees. The theory relates group actions on trees with decomposing groups as iterated applications of the operations of free product with amalgamation and HNN extension, via the notion of the fundamental group of a graph of groups. Bass–Serre theory can be regarded as one-dimensional version of the orbifold theory.

In the mathematical subject of group theory, the Grushko theorem or the Grushko–Neumann theorem is a theorem stating that the rank of a free product of two groups is equal to the sum of the ranks of the two free factors. The theorem was first obtained in a 1940 article of Grushko and then, independently, in a 1943 article of Neumann.

<span class="mw-page-title-main">Directed graph</span> Graph with oriented edges

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by directed edges, often called arcs.

<span class="mw-page-title-main">Reeb graph</span>

A Reeb graph is a mathematical object reflecting the evolution of the level sets of a real-valued function on a manifold. According to a similar concept was introduced by G.M. Adelson-Velskii and A.S. Kronrod and applied to analysis of Hilbert's thirteenth problem. Proposed by G. Reeb as a tool in Morse theory, Reeb graphs are the natural tool to study multivalued functional relationships between 2D scalar fields , , and arising from the conditions and , because these relationships are single-valued when restricted to a region associated with an individual edge of the Reeb graph. This general principle was first used to study neutral surfaces in oceanography.

In mathematics, calculus on finite weighted graphs is a discrete calculus for functions whose domain is the vertex set of a graph with a finite number of vertices and weights associated to the edges. This involves formulating discrete operators on graphs which are analogous to differential operators in calculus, such as graph Laplacians as discrete versions of the Laplacian, and using these operators to formulate differential equations, difference equations, or variational models on graphs which can be interpreted as discrete versions of partial differential equations or continuum variational models. Such equations and models are important tools to mathematically model, analyze, and process discrete information in many different research fields, e.g., image processing, machine learning, and network analysis.

In mathematics, the graph Fourier transform is a mathematical transform which eigendecomposes the Laplacian matrix of a graph into eigenvalues and eigenvectors. Analogously to the classical Fourier transform, the eigenvalues represent frequencies and eigenvectors form what is known as a graph Fourier basis.

References