hotz.tex

\documentclass{article}
    % General document formatting
    \usepackage[margin=0.7in]{geometry}
    \usepackage[parfill]{parskip}
    \usepackage[utf8]{inputenc}

    \usepackage{graphicx}    
    % Related to math
    \usepackage{amsmath,amssymb,amsfonts,amsthm}

    \newtheorem{theorem}{Theorem}
    \newtheorem{lemma}{Lemma}
    \newtheorem*{definition}{Definition}

\begin{document}

\setcounter{section}{-1}

\title{Electronic information processing and cybernetics - An algebrasation of the synthesis problem for circuits}
\author{G\"{u}nter Hotz}
\date{March 1965}

\maketitle
\begin{abstract}
  The composition of switching circuits $A$, $B$, to new circuits can be reduced to two basic operations:
  \begin{enumerate}
    \item The sequential composition $A \circ B$ of $A$ and $B$, if the number of outputs of $B$ is equal to the number of inputs of $A$. 
    \item The composition of $A$ and $B$ to $A\times B$ analogue to the cartesian product. The number of inputs of $A\times B$ is equal the sum of the numbers of the inputs of $A$ and $B$. The same holds for the outputs.
  \end{enumerate}
  Between different compositions a equivalence is introduced which is compatible with "$\circ$" and "$\times$". When the compositions are carried over to the set of the equivalence classes, one gets a algebraical structure, that forms category respective to "$\circ$" and semi-group (monoid) respectice "$\times$". The compositions satisfy the relation
  \[ (A\times B) \circ (C \times D) = (A \circ C) \times (B \circ D) \]
  if $A\circ C$ and $B\circ D$ are defined. A category with this property is called a X-category.
  The X-categories $\mathcal{F}$ studied here can be characterized in the following way:
  \begin{enumerate}
  \item The set of units of $\mathcal{F}$ form a semi-group generated by one generator relative to "$\times$",
  \item $\mathcal{F}$ has a countable generator set or it holds
  \item $\mathcal{F}$ is a subcategory of a category satisfying 1 and 2.
  \end{enumerate}

    In the free X-category of "plane nets" a concept of the combinatorial topology related to the braids of ARTIN plays an important role. Each of the studied free X-categories $\mathcal{F}$ may be mapped on to a X-category of plane nets by a functor. Each theorem about $\mathcal{F}$ by the functor is carried over to a theorem about a category of nets. The theorem proved for the nets can easy be proved in most cases for $\mathcal{F}$; i.e. the theorems about $\mathcal{F}$ have an essential
    combinatorial character. This is the reason that the first chapter only deals about nets.

    The connection of the switching circuits represented by the elements of $\mathcal{F}$ their function gives a functor from $\mathcal{F}$ into the X-category $\mathcal{C}_S$ of maps of the type $f: S^n \rightarrow S^m$, where $S$ is a countable set containing at least two elements. The "$\times$"-product is in $\mathcal{C}_S$ the catesian product.
\end{abstract}

\section{Introduction}
The occasion for this work is a problem from automata theory: From a given set of building blocks an automaton, whose functionality is predetermined, shall be assembled. From the different, eventually existing  solutions the cheapest shall be selected. 

A building block $A \in \mathcal{U}$ is a physical, mostly electrical device with $Q(A)$ inputs and $Z(A)$ outputs. For each input a Set $S$ of input signals is permitted, on which the building block reacts with output signals. We assume the following simplifications with regard to the issue, the following holds:

\begin{enumerate}
\item For each input of the elements of $\mathcal{U}$ a set of signals $S$ is prescribed, and each element of $S^n$ is allowed as input signal for $A$ with $n = Q(A)$.
\item The set of output signals of $A \in \mathcal{U}$ lies in $S^m$ with $m = Z(A)$.
\item If at time $t$ the input signal $s \in S^n$ is applied to $A$, then the output signal at time $t$ is uniquely determined by $s$. (We therefore neglect the finite propagation speed of signals).
\end{enumerate}

Thus, the finite automaton is completely described by its function $\phi(A):S^n \rightarrow S^m$. It is presumed that inputs and outputs of $A$ are labeled with a fixed numbering from $1$ to $Q(A)$, and respectively from $1$ to $Z(A)$. The $i$-th input (output) is assigned to the $i$-th component of $S^n$ ($S^m$). 

An element of $\mathcal{U}$ is a circuit. If $A$ and $B$ are circuits with $Q(A)$, or $Q(B)$ inputs and $Z(A)$, or respectively $Z(B)$ outputs, then we build new circuits from $A$ and $B$ by integrating them to a new element $A\times B$ with $Q(A)+Q(B)$ inputs and $Z(A)+Z(B)$ outputs. We declare the $i$-th input of $A$ as the $i$-th input of $A\times B$ and the $i$-th input of $B$ as the $(Q(A) + i)$-th input of $A\times B$ (figure \ref{fig:figure1}).

\begin{figure}
\includegraphics[]{figure1.png}
  \centering
\caption{}
\label{fig:figure1}
\end{figure}

If $Z(A) = Q(B)$ we get from $A$ and $B$ a circuit $B\circ A$ by switching the $i$-th output of $A$ to the $i$-th input of $B$.

A circuit of elements of $\mathcal{U}$ is a device, which is described inductively by the preceding explanations.

If $\phi(A)$ ($\phi(B)$) is the function of circuit $A$ ($B$), then $\phi(A)\times \phi(B)$ is the function of $A\times B$, and $\phi(B)\circ \phi(A)$ for $Q(B) = Z(A)$  is the function of $B\circ A$.

The costs for the building blocks in $\mathcal{U}$ shall be defined by the function $L : \mathcal{U} \rightarrow N \cup \{0\}$. We define:

\[
\begin{array}{lcr}
L(A\times B) & = & L(A) + L(B), \\
L(B\circ A) & = & L(A) + L(B).
\end{array}
\]

Hereby a price is assigned to each circuit.

Now, the task is the following: Given $f : S^n \rightarrow S^m$, find a circuit $A$ with $\phi(A) = f$ and
\[
L(A) = \min_{B \in \phi^{-1}(f)} \{ L(B) \}.
\]

If $f$ does not fully map to $S^n$, but only to $R \subset S^n$, then the optimum shall be searched on $\cup_{g|R=f} \phi^{-1}(g)$. 

The task is generalized in an obvious way, if $Q(f) = Z(F) = S^n$ and $f$, as it is often the case with finite automata, is determined just by a transformation of $S^n$, 

In order to solve this problem it appears advantageous to know relations, which allow to generate from an element $A \in \phi^{-1}(f)$ all the elements from the class $\phi^{-1}(f)$.

In the first two sections of this work a theory of interconnection of automata will be developed, as already sketched out in the description of the task:

First, the topological notion of a \emph{planar} network is introduced. The binary operators "$\circ$" and "$\times$" will be explained for these networks. One obtains an algebraic structure $\mathcal{R}$, which is a category with respect to "$\circ$" and a semi-group with respect to "$\times$". $\mathcal{R}$ turns out to be a generalisation of the D-category (category with direct products), which we want to call \emph{$X$-Kategorie}.

$\mathcal{R}$ reflects the interconnection of automata, but does not reflect the possibility of different building blocks with the same number of inputs and outputs. This will be accommodated by assigning symbols of the alphabet $\mathcal{U}$ to inner points of the network, respecting the functions $Q : \mathcal{U} \rightarrow N \cup {0}$ and $Z : \mathcal{U} \rightarrow N \cup {0}$. One arrives at an $X$-Kategorie $\mathcal{F}(\mathcal{U})$, which possesses $\mathcal{U}$ as a free family of
generators. The elements of $\mathcal{F}(\mathcal{U})$ correspond to the set of circuits which may be yielded from $\mathcal{U}$. The mapping $\phi$, which assigns to each automaton its functions, becomes a functor $\phi:\mathcal{F}(\mathcal{U}) \rightarrow \mathcal{C}$, where $\mathcal{C}$ is the category of mappings of type $S^n \rightarrow S^m$. 

The introduction of the quotient category  $\mathcal{F}(\mathcal{U})/\mathcal{R}$ from $\mathcal{F}(\mathcal{U})$ to a relational system $\mathcal{R}$ forms the basis for the study of classes $\phi^{-1}(f)$. In section 3 $\phi^{-1}(f)$ will be studied for certain categories $\mathcal{F(U)}$ and distinguished functors $\phi$: We consider only families of generators $\mathcal{U}$ with $\{U, V, D\} \subset \subset \mathcal{U}$ and $Z(A) = 1$ for $A\in \mathcal{U} \setminus \{U, V, D\}$ and functors $\phi$, for which $\phi(U)$ is the mapping from $S$
to $S^{\circ}$, $\phi(V)$ the permutation of the components of $S^2$, and $\phi(D)$ the diagonalisation $S \rightarrow S^2$. Such functions are called \emph{normal}. A relational system $\mathcal{R}$ will be given with the following property: For each normal $\phi$ it holds that $\phi(F) = \phi(G)$ for $F, G \in \mathcal{F}(\mathcal{U})$, iff $F\equiv G(\mathcal{R})$. $\mathcal{F}(\mathcal{U})/\mathcal{R}$ is a $D$-category and $\mathcal{U} \setminus \{U, V, D\}$ a free family of generators of the
$D$-category.

Thus, the relational system allows to simplify the representations $F$ of a function $\phi(F)$, which are possible without the knowledge of the elements in $\mathcal{U} \setminus \{ U, V, D \}$. Figure \ref{fig:figure2} shows that there are proper simplifications in this system.

\begin{figure}
\includegraphics[]{figure2.png}
  \centering
\caption{}
\label{fig:figure2}
\end{figure}

In this work we allow an arbitrary countable set for $S$, such that these results can also be of interest for computer programming. If one wants to formally simplify programs which are constructed from sub-programs, then the number of possible sub-programs renders the specific consideration of the computed function infeasible, but the rules for the transformation of programs have to be applicable uniformly for all sub-programs. Thus, that means that the allowed relations have to be the system
$\mathcal{R}$ or an equivalent system.

For an orientation on the state of the art of the theory of circuit synthesis refer to \cite{circuit-synthesis}, in relation to Streckenkpomplexen to \cite{combinatory-topology} and category theory to \cite{categories-functors} and \cite{category-theory}.
For stimulating discussions and critical remarks I want to thank J. D\"{o}rr and D. Puppe. My thanks go to the Deutsche Forschungsgemeinschaft, who has supported this study with a grant of the FRITZ-THYSSEN-foundation.

\section{The category of planar networks }
\subsection{The category $\mathcal{R}$ of planar networks}
The following topological structure is understood as a network with $n$ inputs and $m$ outputs ($n, m = 0, 1, 2...$):
A rectangle with sides $g_1, g_2$ and $h_1, h_2$ is given in the euclidean plane, where both $g_i$ and $h_i$ lie face to face to each other. $A_1 \ldots A_n$ ($B_1 \ldots B_n$) are mutually distinct points on $g_1$ ($g_2$), where the numbering of points runs from $h_1$ to $h_2$; the $A_i$ ($B_i$) divide $g_1$ ($g_2$) into equidistant parts. 
Let $A_i$ be the starting points and $B_i$ be the endpoints of precisely one line segment of an oriented, finite, planar Streckenkomplex, which lies in the euclidean plane without crossings in the rectangle \footnote{In the euclidean sense it is a matter of piecewise linear curves. }. We further demand from the Streckenkomplex that each of its line segments simply lie above $h_i$ and that the orientation of the line segments points from $g_1$ to $g_2$. Thus the case in figure \ref{fig:figure3} is
excluded.
\begin{figure}
\includegraphics[]{figure3.png}
  \centering
\caption{}
\label{fig:figure3}
\end{figure}

We call $g_1, g_2, h_1, h_2$ the network frame, $A_1, \ldots, A_n$ ($B_1, \ldots, B_m$) the \emph{starting points} or inputs (\emph{end points} or outputs) of the network. The points which are neither inputs nor outputs are called \emph{inner points} of the network.

Two networks are called equal, if they can be - after overlaying their frames without self-penetration in the plane - deformed into one another, in such a way that all intermediate positions are networks. 

We understand a \emph{deformation} as an \emph{elementary deformation} or a deformation, which may be generated by a chain of elementary deformations; the elementary deformations are triangular deformations (figure \ref{fig:figure4}a) or generalised triangular deformations, as shown on figure \ref{fig:figure4}b and \ref{fig:figure4}c. Further the (trivial) deformations are allowed, which are stretches of the frame or euclidean motions of the network.
\begin{figure}
\includegraphics[]{figure4.png}
  \centering
\caption{}
\label{fig:figure4}
\end{figure}

One recognises that the given equivalence definition is reflexive, symmetric and transitive, i.e. a division of the network into equivalence classes. 

From now on we call this class a network and call networks in the conventional sense, when a distinction is important, \emph{representative} of a network.

Different representatives of a network have the same number of inputs and outputs, which we denote by $Q(N)$ and $Z(N)$.

Let $N_1$ and $N_2$ be networks with $Q(N_2)=Z(N_1)$, then we declare between $N_1$ and $N_2$ a composition over representatives $N_1^{\prime}$ and $N_2^{\prime}$ from $N_1$ and $N_2$: 

We deform the frame of $N_2^{\prime}$ (in a trivial manner), such that we can join $N_2^{\prime}$ onto $N_1{\prime}$; i.e. we bring $g_2$ and $g_1^{\prime}$ to the same size and set both frames along $g_2$ and $g_1^{\prime}$ against each other (figure \ref{fig:figure5}). We remove $g_2 = g_1^{\prime}$ and the points $A_i^{\prime} = B_i$ and get again a network representative, that we call $N_2 \circ N_1$. One sees that the definition is independent of the choice of representatives. 

\begin{figure}
\includegraphics[]{figure5.png}
  \centering
\caption{}
\label{fig:figure5}
\end{figure}

Further the following holds:

\[
\begin{array}{lcr}
Q(N_2 \circ N_1) & = & Q(N_1), \\
Z(N_2 \circ N_1) & = & Z(N_2).
\end{array}
\]

As is shown easily, the product is associative; i.e. it holds for networks $N_1, N_2, N_3$ with $Q(N_2) = Z(N_1)$ and $Q(N_3) = Z(N_2)$ that
\[ (N_3 \circ N_2) \circ N_1 = N_3 \circ (N_2 \circ N_1). \]

For each network with $Q(N) = n$ and $Z(N) = m$ there is exactly one network $E_n$ and $E_m$ with the property

\[
N\circ E_n = E_m \circ N = N;
\]

$E_n$ is a network with $n$ inputs, $n$ outputs and $n$ line segments (figure \ref{fig:figure6}). The set of networks therefore forms a category with respect to "$\circ$".

\begin{figure}
\includegraphics[]{figure6.png}
  \centering
\caption{}
\label{fig:figure6}
\end{figure}

We declare a further combination of networks, namely the \emph{X-product}. Let $N_1^{\prime}$ and $N_2^{\prime}$ be representatives of the networks $N_1$ and respectively $N_2$, then we deform the frame to the same length and set them along $h_{12}$ and $h_{21}$ together (figure \ref{fig:figure7}). Subsequently we delete $h_{21}=h_{12}$ and numbering the inputs from left to right. If we take care that the input- and output-points of the structure are again equidistant, then we have again a representative
of a network $N_3$. We call $N_3$ the direct product of $N_1$ and $N_2$ and write $N_3 = N1 \times N_2$. One sees that the direct product is independent of the choice of the representative, associative, and that $E_k = E_1 \times \ldots \times E_1$ ($k$-times), and $E_0 \times N = N \times N_0 = N$ for every network $N$.

We call the set of networks with these two connections with $\mathcal{R}$. We summarize the results into

\begin{theorem}
$\mathcal{R}$ forms a category with respect to "$\circ$" and a semi-group with respect to "$\times$".
\end{theorem}

\begin{figure}
\includegraphics[]{figure7.png}
  \centering
\caption{}
\label{fig:figure7}
\end{figure}

\subsection{The free family of generators of $\mathcal{R}$}

We now want to specify a family of generators for $\mathcal{R}$, i.e. the set $\mathcal{C}$ of networks, from which all networks of $\mathcal{R}$ can be obtained by application of the operations of $\mathcal{R}$.

It is possible to bring each representative of a network into a position in which at most one inner point lies on a parallel to $g_1$. Thus, $N$ may be obtained as a product of networks, which each possess one inner point, expect the case that $N$ does not possess an inner point, thus it is a unit (figure \ref{fig:figure8}).

\begin{figure}
\includegraphics[]{figure8.png}
  \centering
\caption{}
\label{fig:figure8}
\end{figure}

Each network $N$ with exactly one inner point can be factored into a direct product 
\[
N = E_k \times F \times E_m
\]

where $F$ contains the inner point and each line segment of $F$ possesses this point as start- and end-point (figure \ref{fig:figure9}). Potentially $k = 0$ or $m = 0$. $F$ is completely determined by the number of its inputs and outputs. If $F$ has $n$ inputs and $m$ outputs we write $\gamma_m^n$ for $F$.

\begin{figure}
\includegraphics[]{figure9.png}
  \centering
\caption{}
\label{fig:figure9}
\end{figure}

Thereby we have

\begin{theorem}
\label{eq:th2}
The set $\mathcal{C} = \{ \gamma_m^n | n, m = 0, 1, \ldots \}$ is a complete family of generators of $\mathcal{R}$
\end{theorem}

One recognizes further that the family of generators is minimal, since no generators can be expressed in termes of other generators. $\mathcal{C}$ is also the only minimal family of generators of $\mathcal{R}$, because no generator can be expressed through other elements of $\mathcal{R}$ other than through itself; the latter follows, because the number of inner points of a product are equal to the sum of inner points of the factors. Later (section \ref{basis-function-representation}) we will show that $\mathcal{C}$ is
a free family of generators.

We have shown above more than contained in theorem \ref{eq:th2}, namely:

\begin{theorem}
Each network $N \in \mathcal{R}$ with at least one inner point can be factored into one "$\circ$"-product of direct products of the form $E_k \times \gamma_m^n \times E_j$.
\end{theorem}

The presentation of a network $N$ in this form is called a \emph{sequential presentation} of $N$. The same sequential presentations naturally define the same network, but the same network allows different sequential presentations. The next section will provide information on the different presentations of a network.

\subsection{The relations of $\mathcal{R}$}
\label{the-relations-of-R}

It follows directly from the definition of the deformations that the following relations hold
\begin{equation}
\label{eq:R1}
\tag{R1}
(E_{n+k} \times \gamma_j^l) \circ (\gamma_n^m \times E_{k + l}) = (\gamma_n^m \times E_{k+j}) \circ (E_{m+k} \times \gamma_j^l) 
\end{equation}
for $k, m, n = 0, 1, 2, \ldots$ (see figure \ref{fig:figure10}).


\begin{figure}
\includegraphics[]{figure10.png}
  \centering
\caption{
  $(E_{3} \times \gamma_2^1) \circ (\gamma_2^2 \times E_{3}) = (\gamma_2^2 \times E_{2}) \circ (E_{3} \times \gamma_2^1)$ 
}
\label{fig:figure10}
\end{figure}

Further the following relations hold for $F, G, H \in \mathcal{R}$ with $m = Q(F), n = Z(F)$ and $Q(H)=Z(G)$
\begin{equation}
\label{eq:R2}
\tag{R2}
\left.
\begin{array}{c}
(H \circ G) \times F = (H \times F) \circ (G \times E_m) = (H \times E_n) \circ (G \times F), \\
F \times (H \circ G) = (F \times H) \circ (E_m \times G) = (E_n \times H) \circ (F \times G)
\end{array} 
\right\}
\end{equation}

(cf. figure \ref{fig:figure11}).

One sees that the relations (\ref{eq:R1}) are contained in (\ref{eq:R2}).


\begin{figure}
\includegraphics[]{figure11.png}
  \centering
\caption{}
\label{fig:figure11}
\end{figure}

\begin{theorem}
Two presentations $H_1$ and $H_2$ of the same network in the generator family $\mathcal{C}$ under the usage of connections of $\mathcal{R}$ can be transformed via (\ref{eq:R2}) into each other.
\end{theorem}
\begin{proof}
It is apparent that every presentation can be transformed into a sequential presentation with (\ref{eq:R2}). For each sequential presentation of a network a presentation of the network may be assigned, such that exactly these sequential presentations may be recovered by cutting through parallels to $g$.
\end{proof}

Following the previous results, we may suppose that $H_1$ and $H_2$ are sequential presentations of the same network. Let $N_1^{\prime}$ and $N_2^{\prime}$ be assigned to $H_1$ and $H_2$ in the previously described manner. After defining equality $N_1^{\prime}$ may be deformed into $N_2^{\prime}$. Each step of deformation may be divided into sub-deformations such that the order of at most two points of the network is changed, because no two points in $N_1$ by construction lie on a parallel to $g$. The sequential
presentation of the network stays the same, if the order of points is not changed. If it is changed we consider the two corresponding factors of the sequential product. These shall have the form
\[
(E_t \times \gamma_n^m \times E_s) \circ (E_r \times \gamma_j^l \times E_q).
\]
We can separate the common $E$-factors on both sides using (\ref{eq:R2}); Because of the exchangeability of order of the points the term can be transformed into the form
\[
  E_u \times ((\gamma_n^m \times E_{k+j}) \circ (E_{m+k} \times \gamma_j^l)) \times E_v,
\]

or into the form which correspond to the other two points in question. Now we apply (\ref{eq:R1}) and obtain a presentation, which corresponds to the permutation of points after the deformation. Using (\ref{eq:R2}) we bring the presentation back to the sequential form. By deforming $N_1^{\prime}$ step by step into $N_2^{\prime}$ and each time applying the transformations of the sequential presentations just described, $H_1$ is transformed via (\ref{eq:R1}) and (\ref{eq:R2}) into $H_2$, q.e.d.

We will often use subsequently the following relations derived from (\ref{eq:R2}):
\begin{equation}
\label{eq:r2prime}
\tag{$R2^{\prime}$}
\left.
  \begin{array}{c}
  F \times G = (F \circ E_m) \times G = (F\times E_j) \circ (E_m \times G), \\
    (F \times G) = (E_n \circ F) \times G = (E_n \times G) \circ (F \times E_k)
\end{array}
\right\}
\end{equation}

with $k = Q(G), j = Z(G), m = Q(F), n = Z(F)$.

Subsequently we call a category $\mathcal{F}$, which forms a semi-group with respect to a further composition "$\times$", and whose elements meet the relation (\ref{eq:R2}) an \emph{$X$-Kategorie}. 

We want to revisit the transformation of a sequential presentation into another via (\ref{eq:R1}) and (\ref{eq:R2}).

We now assume that we have two presentations of a network, which are deformable into each other by definition. Initially we can deform both networks such that no two points of the network lie on a parallel of the base of frames $g$. 
Now we transform each elementary deformation into sub-deformations, such that each step changes the order of at most two inner points. 
If the order of points stayed the same, then the sequential presentation stayed the same. 
Otherwise we can perform a transposition of the corresponding factors in the sequential presentation through the application of relations from (\ref{eq:R1}) and (\ref{eq:R2}). 
In order to simplify a later proof we want to describe the modifications of sequential presentations a bit more formally. 
These modifications of the sequential presentation are described uniquely by the declaration of the two factors, which concern the modifications of the order, if the point of the upper factor is a starting point or the point of the lower factor is an endpoint of at least one line segment. 
If the $i$-th factor of the presentation $H$ is transposed with the $(i + 1)$-th factor as described before and if the result of the sequential presentation is $H^{\prime}$, then we write $H^{\prime} = v_{i} H$.

In order to ensure the uniqueness condition of $v_i H$ we introduce the \emph{premise} \emph{for this section} that for the network under consideration each point is either starting point or each point is end point of at least one line segment. 
This is the precondition of the aspired theorem 5.

A sequence 
\[
  H_1, H_2 = v_i H_1, \ldots , H_j = v_{i_{j-1}} H_{j-1}.
\]

of sequential presentations is called a chain of deformations. We also write $H_j = v H$ with $v = [v_{i_1}, \ldots v_{i_{j-1}}]$. 

From the proof of theorem 4 follows:

\begin{lemma}
\label{eq:l1}
If $H$ and $H^{\prime}$ are sequential presentations of the same network, then there is a chain of deformations $v$ with $H^{\prime} = v H$; in doing so we permit the empty word $e$ and define $eH = H$.
\end{lemma}

One regognizes: If $H^{\prime} = v_i H$, then $v_i H^{\prime}$ is also explained, and $H = v_i H^{\prime} == [v_i, v_i] H$.

\begin{definition}
A chain of deformations is called \emph{reduced} if no pair $[v_i, v_i]$ does occur on $v$. We say that $v^{\prime}$ arises by reduction, if $v^{\prime}$ is obtainable through cancellation of pairs $[v_i, v_i]$ from $v$.
\end{definition}

It immediatly follows 

\begin{lemma}
 $v$ describes a chain of deformation of $H$ and $v^{\prime}$ is derived from $v$ by reduction. If $H^{\prime} = vH$, then also $H^{\prime} = v^{\prime}H$.
\end{lemma}

We now observe the "path" the first factor of a sequential presentation (the rightmost factor, or the uppermost point of the corresponding presentation) travels during a deformation.

We let
\[
  \begin{array}{rcl}
    h(0) =  1 & = & \mbox{Place of the first factor before the first deformation; }\\
    h(l) (0 \leq l \le j) & = & \mbox{Place of the first factor after the $l$-th deformation.}
  \end{array}
\]

And find:
\[
  h(l+1)= \begin{cases}
           h(l),     & \mbox{ if $i_{l+1} \neq h(l), h(l) - 1$;} \\
           h(l) + 1, & \mbox{ if $i_{l+1} = h(l)$;} \\
           h(l) -1,  & \mbox{ if $i_{l+1} = h(l) - 1$;}
          \end{cases}
\]

where $v = [v_i, \ldots, v_j]$ describes the considered chain of deformation. 

\begin{lemma}
  If $h(l) \neq h(l + 1)$ for $l = 0, \ldots, k - 1$ ($\geq 0$) and if $h(0) = h(k)$ is the chain of deformation $v$ of $H$, then $v$ is not reduced. 
\end{lemma}

\begin{proof}
  Let $v = [v_{i_1}, \ldots , v_{i_k}]$. Since $k \geq 1$ and $h(l) \neq h(l + 1)$ there exists a $j$ with $h(j) \geq 1$ and $h(j)$ is maximal. Then $h(j) = j(j + 1) + 1$ and $v_{i_j} = v_{i_{j+1}}$ and so $v$ is not reduced.
\end{proof}

\begin{lemma}
  \label{eq:lemma4}
  \begin{enumerate}
    \item If $v = [v_i, v_k]$ with $i \neq k \pm 1$ is a chain of deformation of $H$, then $v^{\prime} = v_k, v_i]$ is a also a chain of deformation for $H$, and $vH =v^{\prime}H$.
    \item If $v = [v_i, v_{i+1}, v_i]$ and $v^{\prime}=[v_{i+1}, v_i, v_{i+1}]$, then $v$ is defined for $H$ iff $v^{\prime}$ is defined for $H$ and $vH = v^{\prime}H$ holds.
    \item Let $v^{\prime}$ be a subsequence of $v$ and let $v^{''}$ be defined for a sequential presentation $H_1$, iff this holds for $v^{\prime}$, and let $v^{\prime}H_1 = v^{''} H_1$. 
          Let $v^{+}$ be obtained by replacing $v^{\prime}$ with $v^{\prime \prime}$, then $v$ and $v^{+}$ are declared for the exact same sequential presentation, and it holds, 
          if $v$ is defined for $H$, $v H = v ^{+} H$.
  \end{enumerate}
\end{lemma}

\begin{proof}
  (1) and (2) are evident by geometry. (3) follows from figure \ref{fig:figure12}, where $[v_1, v^{\prime}, v_2] = v$ and $v_1, v^{\prime}, v_2$ are subsequences of $v$.
\end{proof}

\begin{figure}
\includegraphics[]{figure12.png}
  \centering
\caption{}
\label{fig:figure12}
\end{figure}

\subsection{The uniqueness of the solution of the equation $N\circ X= N^{\prime}$}

\begin{theorem}
  \label{eq:th5}
  Let $F, G, G^{\prime} \in \mathcal{R}$ and $G^{\prime} \circ F$ and each inner point of $G \circ F$ is an endpoint of at least one line segment. Then it is true that:
  \begin{equation} G \circ F = G^{\prime} \circ F \implies G = G^{\prime}. \label{eq:th51} \end{equation}
  The symmetric proposition is also true: If $F \circ G$ and $F \circ G^{\prime}$ are declared and for every inner point is the starting point of at least one line segment, then it follows:
  \begin{equation} F \circ G = F \circ G^{\prime} \implies G = G^{\prime}. \label{eq:th52} \end{equation}
  If the preconditions (\ref{eq:th51}) or the preconditions of (\ref{eq:th52}) are met, then it follows that:
  \begin{equation} F \times G = F \times G^{\prime} \implies G = G^{\prime}, \label{eq:th53} \end{equation}
  \begin{equation} G \times F = G^{\prime} \times F \implies G = G^{\prime}. \label{eq:th54} \end{equation}
\end{theorem}

As can be seen from the example on figure \ref{fig:figure13}, the claims (\ref{eq:th51}) and (\ref{eq:th52}) of the theorem are not correct without the constraint on the inner points. The example shows:
\begin{figure}
  \includegraphics[]{figure13.png}
  \centering
  \caption{}
  \label{fig:figure13}
\end{figure}

  \begin{equation*} (E \times \gamma_1^0) \circ \gamma_1^0 = (\gamma_1^0 \times E) \circ \gamma_1^0, \end{equation*}
  \begin{equation*} E \times \gamma_1^0 \neq \gamma_1^0 \times E.  \end{equation*}

For propositions (\ref{eq:th53}) and (\ref{eq:th54}) the preconditions are superfluous, but they facilitate the proof. Since we get along subsequently with (\ref{eq:th53}) and (\ref{eq:th54}) with precondition, we settle for theorem \ref{eq:th5}.

We first proof (\ref{eq:th53}) and (\ref{eq:th54}) under the precondition of (\ref{eq:th51}) and (\ref{eq:th52}).

Proof for (\ref{eq:th53}) and (\ref{eq:th54}). Given that precondition (\ref{eq:th51}) is met. We apply (\ref{eq:r2prime}) and obtain

\begin{equation*} G \times F = (G \times E_n) \circ (E_m \times F), \end{equation*}
\begin{equation*} G^{\prime} \times F = (G^{\prime} \times E_n) \circ (E_k \times F). \end{equation*}

Since $G \times F = G^{\prime} \times F$ we get $Q(G) = Q(G^{\prime})$ and also $k = m$. We apply the precondition to (\ref{eq:th54}) and proposition (\ref{eq:th51}) and get

\[ G \times E_n = G^{\prime} \times E_n. \]

Now we select the sequential presentations $H$ of $G$ and $H^{\prime}$ of $G^{\prime}$. 
Herefrom we obtain a sequential presentation of $G \times E_n$ resp. $G^{\prime} \times E_n$, 
by multiplying every factor from the right "directly" with $E_n$; let the thus obtained sequential presentations be $H_1$ resp. 
$H^{\prime}_1$. From lemma \ref{eq:l1} it follows that there exists a chain of deformation $v$ with $H^{\prime}_1=vH_1$.
Now we see that $v$ also describes a chain of deformation of $H$ and that $H^{\prime}=vH$ holds, from which $G = G^{\prime}$ follows.

The proof runs analogously, when the precondition of (\ref{eq:th52}) is met; 
we then bring $G \times F$ to the form, which is appropriate for the application of (\ref{eq:th52}). 
Thereby (\ref{eq:th54}) is proven. (\ref{eq:th53}) is proven accordingly. 
Now, it suffices to prove (\ref{eq:th51}), since the proof is symmetrical to (\ref{eq:th52}). 
For the time being we prove some lemmas.

\begin{lemma}
Let $H_2 \circ H_1$ and $H^{\prime}_2 \circ H_1$ be sequential presentations of the same network. Let $H_1$ consists of a single factor. 
If the precondition of (\ref{eq:th51}) is met, and if $v = [v_{i_1}, \ldots, v_{i_k}]$ a chain of deformations for $H_2 \times H_1$ with $H^{\prime}_2 \circ H_1 = v(H_2 \circ H_1)$,
then $h(0)=h(k)$, where $h$ is the function defined in \ref{the-relations-of-R}.
\end{lemma}

\begin{proof}
We will carry out the proof geometrically, by switching to representative of the networks, which corresponds to the two sequential presentations.
$h(k)$ specifies to which position in the order of inner points the in $H_2 \circ H_1$ most upper points by the corresponding deformation to $v$ is brought.
Due to the precondition (\ref{eq:th51}) we know that the in $H_2 \circ H_1$ and $H^{\prime}_2 \circ H_1$ respectively most upper point 
is connected with at least one starting point of the network.
Since in both sequential presentations the two most upper factors are equal and from a starting point at most one line segment starts, 
but the incidence relations of the line segments are not changed, 
if follows that the point at the $(h(k))$-th position in $H^{\prime}_2 \circ H_1$ is identical to the point which stands on the first position, i.e. $h(k) = 1 = h(0)$.
\end{proof}

\begin{lemma}
Let $H_2 \circ H_1 \xrightarrow{v_{i_1}} H_2^{\prime} \circ H_1 \xrightarrow{v} H^{+}_2 \circ H_1$ a chain of deformations,
and $H_1$ consists of only one factor, then $H^{\prime}_2=v_{i_1 - 1} H_2$, i.e. $H^{+}_2 \circ H_1 = v ((v_{i_1-1} H_2) \circ H_1)$.  
\end{lemma}

\begin{proof}
Since $i_1 > 1$, $v_{i_1}$ does not concern the first factor, but only factors in $H_2$. 
But their place has measured in $H_2$ a position number which is smaller by $1$ than in $H_2 \circ H_1$, from which the claim follows.
\end{proof}

If $v=[v_{i_1}, \ldots, v_{i_k}]$ describes a chain of deformations for $H$, then we define
\[
\begin{array}{rc} 
   A(v) = & \mbox{Number of positions $i$ with $h(i) = h(i + 1)$} \\
          & \mbox{for $i = 0 , \ldots, k - 1$}
\end{array}
\]

\begin{lemma}
Let $v = [v_{i_1} , \ldots, v_{i_k}]$ be a reduced chain of deformations for $H$, 
and let $h(0) = h(k)$. If $A(v) > 0$, then there exists a chain of deformations $v^{\prime} = [ v_{l_1}, \ldots, v_{i_k}]$ with $l_1 > 1$ and $v^{\prime} H = v H$, 
$A(v) = A(v^{\prime})$ and $h(0)=h^{\prime}(k)$.
\end{lemma}
\begin{proof}
Since $A(v) > 0$, there exists a $j$ with $h(j) = h(j - i)$;
let $j$ be the smallest number with this property. If $j = 1$, then $v_{i_1} \neq v_1$, and there is nothing to show.
\end{proof}

Thus, let $j > 1$. Since $v$ is reduced and $j$ is minimal with $h(j) = h(j - 1)$, 
it follows that $i_1 = 1, i_2 = 2, \ldots, i_{j-1} = j - 1, h(j-1) = j$ and $i_j \neq j - 1, j$. If $i_j > j$, 
then we can exchange $v_{ij}$ according to lemma \ref{eq:lemma4} with $[v_i, \ldots, v_{j-1}]$ and thereby obtain desired the chain of deformation $v^{\prime}$.
If $i_j < j - 1$, then we can exchange as long as we arrive at a $v_l$ with $l = i_j + 1$. 
Then we apply the substitution considered in lemma \ref{eq:lemma4} of $[v_{l-1}, v_1, v_{l -1}]$ with $[v_l, v_{l-1}, v_l]$,
such that the resulting chain of deformation has the form $[v_1, \ldots v_{l-2}, v_l, v_{l-1}, v_l, \ldots]$.
Now, we can exchange $v_l$ with $[v_1, \ldots, v_{l-2}]$ and have thereby obtained a chain of deformation $v^{\prime}$ of the same length as $v$, 
which begins with $v_l \neq v_1$ and for which $v^{\prime}H = vH$ holds (according to lemma \ref{eq:lemma4}). It is apparent that: 
$A(v^{\prime})=A(v)$ and $h(k) = h^{\prime}(k)$, i.e. $h(k)=1$.

\begin{lemma}
  Let $H_1$ be a network with exactly one inner point, $H_2 \circ H_1$ and $H^{\prime}_2 \circ H_1$ are defined fulfil the requirements (1) (theorem \ref{eq:th5}). 
  $v = [v_{i_1}, \ldots, v_{i_{k-1}}]$ defines a chain of deformation for $H_2 \circ H_1$ with $H^{\prime}_2 \circ H_1 = v (H_2 \circ H_1)$. 
  Then it follows: $H_2$ and $H^{\prime}_2$ define the same network.
\end{lemma}

\begin{proof}
  (proof by induction over the length $k$ of the chain of deformation). 
  \begin{enumerate}
    \item Base case. For $k = 0$, i.e. v = e it follows that $H_2 = H^{\prime}_2$.
    \item The proposition is true for $0 \leq n \leq k - 1$. If $v$ is not reduced, then the proposition follows from lemma 2. Thus, let $v$ be reduced. 
      Then $A(v) > 0$ following lemma 3. Following lemma 5 $h(0) = h(k)$. Thereby the requirements for lemma 7 are met. 
      There exists a \[v^{\prime} = [v_{l_1}, \ldots, v_{l_{k - 1}} \mbox{with} v_{l_1} \neq v_1 \mbox{and} v^{\prime}(H_2 \circ H_1) = H^{\prime}_2 \circ H_1. \]
      We apply lemma 6 and obtain a $H^{\prime \prime}$ with
      \[ H_2 \circ H_1 \xrightarrow{v_{l_1}} H^{\prime \prime}_2 \circ H_1 \xrightarrow{[v_{l_2}, \ldots, v_{l_k}]} H^{\prime}_2 \circ H_1 \]
      and
      \[ H^{\prime \prime} = v_{i_1 - 1} H_2 \mbox{.} \]
      Using the base case we can induce that $H^{\prime \prime}_2$ and $H^{\prime}_2$ define the same network, 
      from which this also follows for $H_2$ and $H_2^{\prime}$, q.e.d.
    \end{enumerate}

\end{proof}

Now we can finally proof theorem 5.

Let $G \circ F = G^{\prime} \circ F$. 
Then we choose a sequential presentation of $G, G^{\prime}$ and $F$, which we compose into sequential presentations $G \circ F$ and $G^{\prime} \circ F$. 
If $F$ contains an inner point, then it follows directly from lemma 8 the proposition $G = G^{\prime}$. 
We prove the theorem in its generality by induction over the number of inner points in $F$, 
i.e. over the number of factors in the sequential presentation of $F$. Let $F_2 \circ F_1 = F$, 
and $F_1$ contain exactly one inner point, then $(G \circ F_2) \circ F_1 = (G^{\prime} \circ F_2) \circ F_1$ holds, 
from which according to the previous arguments follows that $G \circ F_2 = G^{\prime \prime} \circ F_2$. 
After applying the base case to this we obtain $G = G^{\prime}$, which proves theorem 5.

The results of theorem 5 permit us the specify a simple procedure for the decision of equality of networks,
which fulfil the preconditions of the theorem.

A necessary condition for $N_1 = N_2$ is that $Q(N_1) = Z(N_2)$ and $Z(N_1) = Z(N_2)$ and that $N_1$ and $N_2$ have the same number of inner points.

If $m = 1$, then the decision is trivial.

Let $m > 1$. In this case there is a network $N^{\prime}_1$ with $m - 1$ inner points,
such that $N_1 = N^{\prime} \circ H_1$ holds. Now examine if it is possible to separate factor $H_1$ from $N_2$. 
This can be done by checking if there is an inner point from $N_2$ with the same number of inputs and outputs as the inner point $H_1$,
and if this point is connected in the corresponding fashion with the starting points of $N_2$,
as it applies to the inner point of $H_1$.
If such a point exists, then it follows that $N_2 = N^{\prime}_2 \circ H_1$ and because of theorem 5 it follows that $N_2 = N_1$ iff we can write $N^{\prime}_2 = N^{\prime}_1$.
$N^{\prime}_2$ and $N^{\prime}_1$ have only $m - 1$ inner points. 
Thus we have a procedure with delivers the sought-after decision not later than $m$ steps.

\section{Definition of categories by a direct product through generators and defining relations}
\subsection{Representation of functions with basis functions}
\label{basis-function-representation}
\subsection{The uniqueness of the solution $F \circ X = G$}
\subsection{Creation of the factor category of $\mathcal{F}(U)$ according to a relational system}
\subsection{Representation of functions with basis functions}

\begin{thebibliography}{9}
\bibitem{zoepfe}
Artin, E., Theorie der Zöpfe. Abh. des Math. Seminars der Hamburgerischen Universit\"{a}t Bd. IV (1926).

\bibitem{circuit-synthesis}
Curtis, H. A., A New Approach to the Design of Switching Circuits. D. van Norstrand Com., Princeton 1962

\bibitem{computability}
Hermes, H., Aufz\"{a}hlbarkeit, Entscheidbarkeit, Berechenbarkeit. Springer-Verlag, Berlin-G\"{o}ttingen-Heidelberg 1961

\bibitem{categories-functors}
Puppe, D., Kategorien und Funktoren. Ausarbeitung einer Vorlesung an der Universit\"{a}t Saarbr\"{u}cken im Sommersemester 1963

\bibitem{combinatory-topology} 
Reidemeister, K., Einf\"{u}rung in die kombinatorische Topologie. Vieweg-Verlag, Braunschweig 1951

\bibitem{category-theory}
Kurosch, A. G. u. a., Zur Theorie der Kategorien. Mathematische Forschungsberichte XV. Deutscher Verlag der Wissenschaften, Berlin 1963
\end{thebibliography}

\end{document}