Prediction of solutions on the basis of the mathematical model of cognitive digital automata

Abstract

An approach to the problem of solution prediction on the basis of the mathematical model of cognitive digital automata (CDA) is proposed. A particular advantage of the proposed mathematical model of CDA is that the training procedure can be performed on a limited (minimal) number of training sets. Prediction or generation of solutions, in its turn, is performed on the basis of the mathematical model of CDA obtained in the process of training. The mathematical model of CDA was tested on an example of modeling an $n$ -bit adder. As a result of training, the mathematical model of CDA was formed, which made it possible to reproduce the entire set of the truth table of the $n$ -bit parallel adder with a specified accuracy.

Keywords

Cognitive digital automata prediction Petri nets state equation mathematical modeling synthesis generation analysis logic

1. Introduction

An approach to the problem of solution prediction on the basis of the mathematical model of cognitive digital automata (CDA) [1] is proposed. A particular advantage of the proposed mathematical model of CDA is that the training procedure can be performed on a limited (minimal) number of training sets.

The formation of the configuration of the initial structure of an automaton is carried out as a result of the cluster analysis of training sets. Based on the results of the cluster analysis or classification of training sets can determine the number of inputs and outputs, the number of layers of initial structure, the number of components in each layer, the structure of connections between components . The regression analysis of the data of training sets is performed in the process of training or synthesis of the logic of the initial structure of automaton.

The initial structure of an automaton is represented as a universal matrix, where the connections between the components are built on the principle of “all with all”. Various multi-level configurations of the initial structure are also possible, where the connections between components are built on the principle of “all with all” only between different levels of the initial structure or according to the principle of convolutional neural networks.

The possibility of forming a formula (network algorithm) of CDA depends on the critical mass (quality) of training sets and training algorithms. Hence, the task of generating the minimum number of training sets for a given CDA function or experimentally determined function is of particular importance. Prediction or generation of solutions, in its turn, is performed on the basis of the mathematical model of CDA obtained in the process of training.

The mathematical model is constructed on the basis of the representation of CDA in the form of the state equation of PNs from the class of Murata equations (matrix equations) [2] or a system of linear algebraic equations (SLAE). The mathematical model of CDA was tested on an example of modeling an $n$ -bit parallel adder. As a result of training, the mathematical model of CDA was formed, which made it possible to reproduce the entire set of the truth table of the $n$ -bit parallel adder with a specified accuracy

With an increase in the capacity of the adder with an exponential growth in the total number of sets, almost the linear dependence of the growth of training sets is achieved. Accordingly, acceptable time of learning is achieved. At the same time, the digit capacity of the adder is limited only by the memory capacity and the speed of the computer.

2. Construction of the mathematical model of an n-digit adder

The initial structure of CDA is represented in the form of a marked graph (structure diagram) by interpreting the inputs and outputs of the structure and structural components by the positions of the marked graph, and the components themselves and the connection lines as composite and simple transitions, respectively. The set of inputs and outputs of the structure diagram is interpreted as a set of input and output positions of the network. The availability of information is interpreted as a token in the network position. At the logical presentation level, a token in a network position is interpreted as a logical unit, and its absence is interpreted as the logical zero. The movement of information is interpreted as the movement of tokens.

Figure 1 shows the marked graph of a two-digit adder. The formation of the structure diagram is made on the basis of the results of the cluster analysis (classification) of training sets or the truth table of a two-digit adder (see Table 1).

As the minimum set of training sets (highlighted in gray), those rows are selected from the truth table which give ‘1’ in only one output of the adder taking account of the transfer to the senior (third) class. Thus, for each output of the adder, the corresponding class of training sets is formed. Further, from the selected sets for each output class, only sets with one ‘1’ at the inputs of the adder, with two ‘1’, etc., were selected. According to this principle, the corresponding subclasses of training sets have been formed.

When forming the initial structure of the adder, sets of subclasses constitute the first layer of the structure diagram, where one component is given to each subclass. The set of classes constitutes the second layer of the structure diagram, where one component also corresponds to each class. As a result, the initial structure of the adder consists of two layers. The number of components of the first layer is equal to the number of subclasses. The number of components of the second layer is equal to the number of classes. In the case when a class consists of one subclass, only one component is formed in the first or second layer. The structure of connections between the inputs of the structure diagram and the inputs of the components of the first layer, the outputs of the components of the first layer and the inputs of the components of the second layer is formed according to the principle of “all with all”.

The representation of the CDA structure diagram in the form of a marked graph allows one to go from the description of the structure diagram to its mathematical representation in the form of the incidence matrix: $A=A^{=}+A^{-}$ .

The incidence matrix of the marked graph for a two-digit adder will take the form:

$\displaystyle\@setsize{\footnotesize}{10pt}{\ixpt}{\@ixpt}\mathbf{A}=% \bordermatrix{&t_{1}&t_{2}&t_{3}&t_{4}&T_{5}&T_{6}&T_{7}&T_{8}\cr b_{1}p_{1}&-% 1&0&0&0&0&0&0&0\cr a_{1}p_{2}&0&-1&0&0&0&0&0&0\cr b_{2}p_{3}&0&0&-1&0&0&0&0&0% \cr b_{2}p_{4}&0&0&0&-1&0&0&0&0\cr p_{5}&1&0&0&0&-1&0&0&0\cr p_{6}&0&1&0&0&-1&% 0&0&0\cr p_{7}&0&0&1&0&-1&0&0&0\cr p_{8}&0&0&0&1&-1&0&0&0\cr p_{9}&1&0&0&0&0&-% 1&0&0\cr p_{10}&0&1&0&0&0&-1&0&0\cr p_{11}&0&0&1&0&0&-1&0&0\cr p_{12}&0&0&0&1&% 0&-1&0&0\cr p_{13}&1&0&0&0&0&0&-1&0\cr p_{14}&0&1&0&0&0&0&-1&0\cr p_{15}&0&0&1% &0&0&0&-1&0\cr p_{16}&0&0&0&1&0&0&-1&0\cr p_{17}&0&0&0&0&0&1&0&-1\cr p_{18}&0&% 0&0&0&0&0&1&-1\cr f_{1}p_{19}&0&0&0&0&1&0&0&0\cr f_{2}p_{20}&0&0&0&0&0&0&0&1% \cr}.$

Constructing a complex mathematical model of CDA is done on the basis of the fundamental state equation of Petri nets from the class of Murata equations [2]:

$\displaystyle\Delta\bm{\mu}=\mathbf{A}\bullet\bm{\tau},$ (1)

where $\Delta\bm{\mu}=\bm{\mu}-\bm{\mu}_{0}$ , $\bm{\mu}_{0}$ – the initial network marking vector, $\bm{\mu}$ – the finite network marking vector, $\bm{\tau}$ – the network transition coverage vector, which determines only the composition and does not determine the sequence of transition firings. The vector $\Delta\bm{\mu}$ is set in a multitude of network positions $\mathbf{P}$ . The vector $\bm{\tau}$ is set in a multitude of network transitions $\mathbf{T}$ . A set of vectors $\Delta\bm{\mu}$ forms a set of $\Delta\mathbf{M}$ , where $\bm{\Delta}\bm{\mu}\in\Delta\mathbf{M}$ . A set of transition coverage vectors $\bm{\tau}$ forms network coverage $\mathbf{S}$ , where $\bm{\tau}\in\mathbf{S}$ .

The set $\Delta\mathbf{M}$ specified on the set of input and output positions of the network is interpreted as an initial truth table (Table) or a transition table (switching) of CDA states. As a set of training sets, all sets from the truth table can be used, or only the minimum number of sets.

On a set of training sets, the CDA network model can be represented as a system of matrix equations of Petri nets:

$\displaystyle\Delta\mathbf{M}=\mathbf{A}\bullet\mathbf{S}.$ (2)

For a two-digit adder shown in Fig. 1, the system of matrix Eq. (2) on the minimum set of training sets can be reduced to the form:

$\displaystyle\@setsize{\footnotesize}{10pt}{\ixpt}{\@ixpt}\bordermatrix{\bm{% \Delta}\bm{\mu}_{\mathbf{2}}&\bm{\Delta}\bm{\mu}_{\mathbf{3}}&\bm{\Delta}\bm{% \mu}_{\mathbf{4}}&\bm{\Delta}\bm{\mu}_{\mathbf{5}}&\bm{\Delta}\bm{\mu}_{% \mathbf{9}}\cr-1&0&-1&0&0\cr 0&-1&-1&0&0\cr 0&0&0&-1&0\cr 0&0&0&0&-1\cr x&x&x&% x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&% x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&% x&x\cr x&x&x&x&x\cr 1&1&0&0&0\cr 0&0&1&1&1\cr}=\bordermatrix{&t_{1}&t_{2}&t_{3% }&t_{4}&T_{5}&T_{6}&T_{7}&T_{8}\cr p_{1}&-1&0&0&0&0&0&0&0\cr p_{2}&0&-1&0&0&0&% 0&0&0\cr p_{3}&0&0&-1&0&0&0&0&0\cr p_{4}&0&0&0&-1&0&0&0&0\cr p_{5}&1&0&0&0&-1&% 0&0&0\cr p_{6}&0&1&0&0&-1&0&0&0\cr p_{7}&0&0&1&0&-1&0&0&0\cr p_{8}&0&0&0&1&-1&% 0&0&0\cr p_{9}&1&0&0&0&0&-1&0&0\cr p_{10}&0&1&0&0&0&-1&0&0\cr p_{11}&0&0&1&0&0% &-1&0&0\cr p_{12}&0&0&0&1&0&-1&0&0\cr p_{13}&1&0&0&0&0&0&-1&0\cr p_{14}&0&1&0&% 0&0&0&-1&0\cr p_{15}&0&0&1&0&0&0&-1&0\cr p_{16}&0&0&0&1&0&0&-1&0\cr p_{17}&0&0% &0&0&0&1&0&-1\cr p_{18}&0&0&0&0&0&0&1&-1\cr p_{19}&0&0&0&0&1&0&0&0\cr p_{20}&0% &0&0&0&0&0&0&1\cr}\cdot\bordermatrix{\bm{\tau}_{\mathbf{2}}&\bm{\tau}_{\mathbf% {3}}&\bm{\tau}_{\mathbf{4}}&\bm{\tau}_{\mathbf{5}}&\bm{\tau}_{\mathbf{9}}\cr x% &x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x% &x&x&x&x\cr x&x&x&x&x\cr}.$

The marking of the internal positions of the set $\Delta\mathbf{M}$ is not determined. The composition of the coverage transitions $\mathbf{S}$ is also not determined. Only the initial incidence matrix $\mathbf{A}$ is completely determined.

Figure 1.

The marked graph of a two-digit adder.

3. Logic synthesis of an n-digit adder

To solve the CDA logic synthesis problem, the methods of calculating the invariants of the state equation of the marked graph of the automaton structure diagram are used. Marked graph invariants are a powerful tool for studying the structural properties of networks and are solutions of homogeneous systems of equations.

As a result of calculating the invariants, the minimal system of matrix equations for a two-digit adder will take the form:

$\displaystyle\@setsize{\footnotesize}{10pt}{\ixpt}{\@ixpt}\bordermatrix{\bm{% \Delta}\bm{\mu}_{\mathbf{2}}&\bm{\Delta}\bm{\mu}_{\mathbf{3}}&\bm{\Delta}\bm{% \mu}_{\mathbf{4}}&\bm{\Delta}\bm{\mu}_{\mathbf{5}}&\bm{\Delta}\bm{\mu}_{% \mathbf{9}}\cr-1&0&-1&0&0\cr 0&-1&-1&0&0\cr 0&0&0&-1&0\cr 0&0&0&0&-1\cr 0&x&x&% x&x\cr x&0&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&0&x&x\cr x&x&0&x&x\cr x&x&x&% x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&x&x\cr x&x&x&0&x\cr x&x&x&x&0\cr x&x&0&% x&x\cr x&x&x&0&0\cr 1&1&0&0&0\cr 0&0&1&1&1\cr}=\bordermatrix{&t_{1}&t_{2}&t_{3% }&t_{4}&T_{5}&T_{6}&T_{7}&T_{8}\cr p_{1}&-1&0&0&0&0&0&0&0\cr p_{2}&0&-1&0&0&0&% 0&0&0\cr p_{3}&0&0&-1&0&0&0&0&0\cr p_{4}&0&0&0&-1&0&0&0&0\cr p_{5}&1&0&0&0&-1&% 0&0&0\cr p_{6}&0&1&0&0&-1&0&0&0\cr p_{7}&0&0&1&0&-1&0&0&0\cr p_{8}&0&0&0&1&-1&% 0&0&0\cr p_{9}&1&0&0&0&0&-1&0&0\cr p_{10}&0&1&0&0&0&-1&0&0\cr p_{11}&0&0&1&0&0% &-1&0&0\cr p_{12}&0&0&0&1&0&-1&0&0\cr p_{13}&1&0&0&0&0&0&-1&0\cr p_{14}&0&1&0&% 0&0&0&-1&0\cr p_{15}&0&0&1&0&0&0&-1&0\cr p_{16}&0&0&0&1&0&0&-1&0\cr p_{17}&0&0% &0&0&0&1&0&-1\cr p_{18}&0&0&0&0&0&0&1&-1\cr p_{19}&0&0&0&0&1&0&0&0\cr p_{20}&0% &0&0&0&0&0&0&1\cr}\cdot\bm{\tau}_{\mathbf{2}}\bm{\tau}_{\mathbf{3}}\bm{\tau}_{% \mathbf{4}}_5_9$ $\displaystyle 101$ $\displaystyle 011$ $\displaystyle 0001$ $\displaystyle 0001$ $\displaystyle 110$ $\displaystyle 001$ $\displaystyle 00011$ $\displaystyle 00111$

and

$\displaystyle\bordermatrix{t_{1}&-1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0\cr t% _{2}&0&-1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&0\cr t_{3}&0&0&-1&0&0&0&1&0&0&0&1&% 0&0&0&1&0&0&0&0&0\cr t_{4}&0&0&0&-1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0\cr T_{5}&0% &0&0&0&-1&-1&-1&-1&0&0&0&0&0&0&0&0&0&0&1&0\cr T_{6}&0&0&0&0&0&0&0&0&-1&-1&-1&-% 1&0&0&0&0&1&0&0&0\cr T_{7}&0&0&0&0&0&0&0&0&0&0&0&0&-1&-1&-1&-1&0&1&0&0\cr T_{8% }&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&-1&-1&0&1\cr}\cdot$ $\displaystyle\@setsize{\footnotesize}{10pt}{\ixpt}{\@ixpt}\bordermatrix{&% \mathbf{R}_{\mathbf{2}}&\mathbf{R}_{\mathbf{3}}&\mathbf{R}_{\mathbf{4}}&% \mathbf{R}_{\mathbf{5}}&\mathbf{R}_{\mathbf{9}}&\cr p_{1}&1&0&1&0&0&0\cr p_{2}% &0&1&0&1&0&0\cr p_{3}&0&0&0&0&1&0\cr p_{4}&0&0&0&0&0&1\cr p_{5}&1&0&0&0&0&0\cr p% _{6}&0&1&0&0&0&0\cr p_{7}&0&0&0&0&0&0\cr p_{8}&0&0&0&0&0&0\cr p_{9}&0&0&1&0&0&% 0\cr p_{10}&0&0&0&1&0&0\cr p_{11}&0&0&0&0&0&0\cr p_{12}&0&0&0&0&0&0\cr p_{13}&% 0&0&0&0&0&0\cr p_{14}&0&0&0&0&0&0\cr p_{15}&0&0&0&0&1&0\cr p_{16}&0&0&0&0&0&1% \cr p_{17}&0&0&1&1&0&0\cr p_{18}&0&0&0&0&1&1\cr p_{19}&1&1&0&0&0&0\cr p_{20}&0% &0&1&1&1&1\cr}=\bordermatrix{\mathbf{y}_{\mathbf{1}}&\mathbf{y}_{\mathbf{2}}&% \mathbf{y}_{\mathbf{3}}&\mathbf{y}_{\mathbf{4}}&\mathbf{y}_{\mathbf{5}}&% \mathbf{y}_{\mathbf{6}}\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&% 0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr}.$

Table 1
The truth table of a two-digit adder

No.	$a_{2}$	$b_{2}$	$a_{1}$	$b_{1}$	$f_{2}$	$f_{1}$	$c_{2}$
	$p_{4}$	$p_{3}$	$p_{2}$	$p_{1}$	$p_{20}$	$p_{19}$
1	0	0	0	0	0	0	0
2	0	0	0	1	0	1	0
3	0	0	1	0	0	1	0
4	0	0	1	1	1	0	0
5	0	1	0	0	1	0	0
6	0	1	0	1	1	1	0
7	0	1	1	0	1	1	0
8	0	1	1	1	0	0	1
9	1	0	0	0	1	0	0
10	1	0	0	1	1	1	0
11	1	0	1	0	1	1	0
12	1	0	1	1	0	0	1
13	1	1	0	0	0	0	1
14	1	1	0	1	0	1	1
15	1	1	1	0	0	1	1
16	1	1	1	1	1	0	1

The projection of implicitly defined input logic of composite transitions of components and output logic of simple transitions of connection lines to the initial structure diagram of an automaton is reduced to solving a system of homogeneous Eq. (2) with an undetermined incidence matrix. After the introduction of unknowns into the incidence matrix, the system of matrix equations for a two-digit adder can be represented as homogeneous on the set of internal network positions:

$\displaystyle\@setsize{\footnotesize}{10pt}{\ixpt}{\@ixpt}\bordermatrix{\bm{% \Delta}\bm{\mu}_{\mathbf{2}}&\bm{\Delta}\bm{\mu}_{\mathbf{3}}&\bm{\Delta}\bm{% \mu}_{\mathbf{4}}&\bm{\Delta}\bm{\mu}_{\mathbf{5}}&\bm{\Delta}\bm{\mu}_{% \mathbf{9}}\cr-1&0&-1&0&0\cr 0&-1&-1&0&0\cr 0&0&0&-1&0\cr 0&0&0&0&-1\cr 0&0&0&% 0&0\cr 0&0&0&0&0\cr 0&0&0&0&0\cr 0&0&0&0&0\cr 0&0&0&0&0\cr 0&0&0&0&0\cr 0&0&0&% 0&0\cr 0&0&0&0&0\cr 0&0&0&0&0\cr 0&0&0&0&0\cr 0&0&0&0&0\cr 0&0&0&0&0\cr 0&0&0&% 0&0\cr 0&0&0&0&0\cr 1&1&0&0&0\cr 0&0&1&1&1\cr}=\bordermatrix{&t_{1}&t_{2}&t_{3% }&t_{4}&T_{5}&T_{6}&T_{7}&T_{8}\cr p_{1}&-1&0&0&0&0&0&0&0\cr p_{2}&0&-1&0&0&0&% 0&0&0\cr p_{3}&0&0&-1&0&0&0&0&0\cr p_{4}&0&0&0&-1&0&0&0&0\cr p_{5}&\alpha_{1}&% 0&0&0&-\alpha_{1}&0&0&0\cr p_{6}&0&\alpha_{2}&0&0&-\alpha_{2}&0&0&0\cr p_{7}&0% &0&\alpha_{3}&0&-\alpha_{3}&0&0&0\cr p_{8}&0&0&0&\alpha_{4}&-\alpha_{4}&0&0&0% \cr p_{9}&\alpha_{5}&0&0&0&0&-\alpha_{5}&0&0\cr p_{10}&0&\alpha_{6}&0&0&0&-% \alpha_{6}&0&0\cr p_{11}&0&0&\alpha_{7}&0&0&-\alpha_{7}&0&0\cr p_{12}&0&0&0&% \alpha_{8}&0&-\alpha_{8}&0&0\cr p_{13}&\alpha_{9}&0&0&0&0&0&-\alpha_{9}&0\cr p% _{14}&0&\alpha_{10}&0&0&0&0&-\alpha_{10}&0\cr p_{15}&0&0&\alpha_{11}&0&0&0&-% \alpha_{11}&0\cr p_{16}&0&0&0&\alpha_{12}&0&0&-\alpha_{12}&0\cr p_{17}&0&0&0&0% &0&\alpha_{13}&0&-\alpha_{13}\cr p_{18}&0&0&0&0&0&0&\alpha_{14}&-\alpha_{14}% \cr p_{19}&0&0&0&0&1&0&0&0\cr p_{20}&0&0&0&0&0&0&0&1\cr}\cdot\bordermatrix{\bm% {\tau}_{\mathbf{2}}&\bm{\tau}_{\mathbf{3}}&\bm{\tau}_{\mathbf{4}}&\bm{\tau}_{% \mathbf{5}}&\bm{\tau}_{\mathbf{9}}\cr 1&0&1&0&0\cr 0&1&1&0&0\cr 0&0&0&1&0\cr 0% &0&0&0&1\cr 1&1&0&0&0\cr 0&0&1&0&0\cr 0&0&0&1&1\cr 0&0&1&1&1\cr}.$

The corresponding matrix $\mathbf{A}^{\bm{\tau}}$ is calculated for each vector $\bm{\tau}$ . The values of the unknowns for inhibitor arcs are defined implicitly and are equal to zero, which provides a solution to the problem of the matrix representation of inhibitory Petri nets. At the same time, for each compound transition that is a part of the vector $\bm{\tau}$ , the corresponding simple transition and its structural connections characteristic only for the given vector $\bm{\tau}$ are determined. As a result of the union of the matrices $\mathbf{A}^{\bm{\tau}}$ , the inhibitor incidence matrix is formed: $\mathbf{A}^{\mathbf{I}}=\cup\mathbf{A}^{\bm{\tau}}$ .

Practically, the projection of implicitly defined logic onto the initial structure diagram of the automaton is reduced to zeroing the rows of the original incidence matrix for each vector $\bm{\tau}$ on a set of network positions that are not part of the corresponding coverage $\mathbf{R}$ with the subsequent combination of the matrices for each $\mathbf{R}$ . Null rows in the incidence matrix $\mathbf{A}^{\mathbf{I}}$ are deleted.

For a two-digit adder, the incidence matrix $\mathbf{A}^{\mathbf{I}}$ will take the form:

$\displaystyle\@setsize{\footnotesize}{10pt}{\ixpt}{\@ixpt}\mathbf{A}^{\mathbf{% I}}=\bordermatrix{&t_{1}&t_{2}&t_{3}&t_{4}&t_{5.1}&t_{5.2}&t_{6}&t_{7.1}&t_{7.% 2}&t_{8.1}&t_{8.2}\cr p_{1}&-1&0&0&0&0&0&0&0&0&0&0\cr p_{2}&0&-1&0&0&0&0&0&0&0% &0&0\cr p_{3}&0&0&-1&0&0&0&0&0&0&0&0\cr p_{4}&0&0&0&-1&0&0&0&0&0&0&0\cr p_{5}&% 1&0&0&0&-1&0&0&0&0&0&0\cr p_{6}&0&1&0&0&0&-1&0&0&0&0&0\cr p_{9}&1&0&0&0&0&0&-1% &0&0&0&0\cr p_{10}&0&1&0&0&0&0&-1&0&0&0&0\cr p_{15}&0&0&1&0&0&0&0&-1&0&0&0\cr p% _{16}&0&0&0&1&0&0&0&0&-1&0&0\cr p_{17}&0&0&0&0&0&0&1&0&0&-1&0\cr p_{18}&0&0&0&% 0&0&0&0&1&1&0&-1\cr p_{19}&0&0&0&0&1&1&0&0&0&0&0\cr p_{20}&0&0&0&0&0&0&0&0&0&1% &1\cr}.$

Matrix $\mathbf{A}^{\mathbf{I}}$ , in its turn, can be presented in the form of PNs inhibitor graph (Fig. 2).

Figure 2.

Inhibitor graph of two-digit adder.

The logic of the components (compound transitions) of the initial CDA structure diagram in the synthesis process (training) of each learning step may vary, i.e. truth tables of network components do not have a fixed size and, accordingly, a fixed logic function. The process of forming the logic of components is limited only by the number of component inputs or the exhaustive search through possible combinations of signals at the inputs of each component. When there is a sufficiently large number of inputs of each component, the process of forming the logic of components and the network as a whole is almost endless.

To develop the formula (network algorithm) of the original function defined on basis of training sets, operations of relational algebra and more complex relational calculus over sets $\mathbf{A}^{\bm{\tau}}$ can be used. In the end, the set of obtained matrices $\mathbf{A}^{\bm{\tau}}$ make up the combined matrix of non-uniform inhibitory Petri net or a network algorithm (logical circuit model) of CDA (Fig. 2). Further, the obtained network algorithm in the form of then incidence matrix $\mathbf{A}^{\mathbf{I}}$ is used as the initial information to solve the problems of the reachability analysis and generation of reachable stable states of CDA.

4. Solution generation of an n-digit adder

The mathematical model of CDA makes it possible to reproduce both the set of solutions specified in the training process and the set of solutions that were not set in the training process. The task of generating solutions of the mathematical model of CDA is reduced to solving the problem of reachability of inhibitory Petri nets.

The analysis of reachability of inhibitory Petri nets, in its turn, is reduced to solving a system of Eq. (2) with the incidence matrix $\mathbf{A}^{\mathbf{I}}$ :

$\displaystyle\Delta\mathbf{M}=\mathbf{A}^{\mathbf{I}}\bullet\mathbf{S}.$ (3)

If each vector $\Delta\bm{\mu}\in\bm{\Delta}\mathbf{M}$ is fully defined on the set of input and output positions of the network, the analysis of reachability of stable states of automaton is performed (verification of the structural diagram of automaton). The system of Eq. (3) can have only one solution for each vector $\Delta\bm{\mu}$ .

The generation of reachable steady states of CDA is performed in the case, if each vector $\Delta\bm{\mu}$ is undefined totally on a set of input and output positions of the network. In case of an uncertainty or incomplete definition of the vector $\Delta\bm{\mu}$ , the system of Eq. (3) has a set of solutions for each vector $\Delta\bm{\mu}\in\bm{\Delta}\mathbf{M}$ . The entire set of solutions can be obtained even in the case of complete uncertainty of the set $\bm{\Delta}\mathbf{M}$ . The number of solutions corresponds to the number of possible switchings of the automaton or the number of sets of the truth table (switching table).

All the set of possible solutions for a two-digit adder are given below:

$\displaystyle\@setsize{\footnotesize}{10pt}{\ixpt}{\@ixpt}\mathbf{S}=% \bordermatrix{&\bm{\tau}_{\mathbf{1}}&\bm{\tau}_{\mathbf{2}}&\bm{\tau}_{% \mathbf{3}}&\bm{\tau}_{\mathbf{4}}&\bm{\tau}_{\mathbf{5}}&\bm{\tau}_{\mathbf{6% }}&\bm{\tau}_{\mathbf{7}}&\bm{\tau}_{\mathbf{8}}&\bm{\tau}_{\mathbf{9}}&\bm{% \tau}_{\mathbf{10}}&\bm{\tau}_{\mathbf{11}}&\bm{\tau}_{\mathbf{12}}&\bm{\tau}_% {\mathbf{13}}&\bm{\tau}_{\mathbf{14}}&\bm{\tau}_{\mathbf{15}}&\bm{\tau}_{% \mathbf{16}}\cr t_{1}&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1\cr t_{2}&0&0&1&1&0&0&1&1% &0&0&1&1&0&0&1&1\cr t_{3}&0&0&0&0&1&1&1&1&0&0&0&0&1&1&1&1\cr t_{4}&0&0&0&0&0&0% &0&0&1&1&1&1&1&1&1&1\cr t_{5.1}&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0\cr t_{5.2}&0&0% &1&0&0&0&1&0&0&0&1&0&0&0&1&0\cr t_{6}&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1\cr t_{7.% 1}&0&0&0&0&1&1&1&1&0&0&0&0&0&0&0&0\cr t_{7.2}&0&0&0&0&0&0&0&0&1&1&1&1&0&0&0&0% \cr t_{8.1}&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1\cr t_{8.2}&0&0&0&0&1&1&1&0&1&1&1&0% &0&0&0&0\cr}$

and

$\displaystyle\@setsize{\footnotesize}{10pt}{\ixpt}{\@ixpt}\bm{\Delta}\mathbf{M% }=\bordermatrix{&\bm{\Delta}\bm{\mu}_{\mathbf{1}}&\bm{\Delta}\bm{\mu}_{\mathbf% {2}}&\bm{\Delta}\bm{\mu}_{\mathbf{3}}&\bm{\Delta}\bm{\mu}_{\mathbf{4}}&\bm{% \Delta}\bm{\mu}_{\mathbf{5}}&\bm{\Delta}\bm{\mu}_{\mathbf{6}}&\bm{\Delta}\bm{% \mu}_{\mathbf{7}}&\bm{\Delta}\bm{\mu}_{\mathbf{8}}&\bm{\Delta}\bm{\mu}_{% \mathbf{9}}&\bm{\Delta}\bm{\mu}_{\mathbf{10}}&\bm{\Delta}\bm{\mu}_{\mathbf{11}% }&\bm{\Delta}\bm{\mu}_{\mathbf{12}}&\bm{\Delta}\bm{\mu}_{\mathbf{13}}&\bm{% \Delta}\bm{\mu}_{\mathbf{14}}&\bm{\Delta}\bm{\mu}_{\mathbf{15}}&\bm{\Delta}\bm% {\mu}_{\mathbf{16}}\cr p_{1}&0&-1&0&-1&0&-1&0&-1&0&-1&0&-1&0&-1&0&-1\cr p_{2}&% 0&0&-1&-1&0&0&-1&-1&0&0&-1&-1&0&0&-1&-1\cr p_{3}&0&0&0&0&-1&-1&-1&-1&0&0&0&0&-% 1&-1&-1&-1\cr p_{4}&0&0&0&0&0&0&0&0&-1&-1&-1&-1&-1&-1&-1&-1\cr p_{5}&0&0&0&1&0% &0&0&1&0&0&0&1&0&0&0&1\cr p_{6}&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1\cr p_{9}&0&1&0% &0&0&1&0&0&0&1&0&0&0&1&0&0\cr p_{10}&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0\cr p_{15}% &0&0&0&0&0&0&0&0&0&0&0&0&1&1&1&1\cr p_{16}&0&0&0&0&0&0&0&0&0&0&0&0&1&1&1&1\cr p% _{17}&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0\cr p_{18}&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&% 0\cr p_{19}&0&1&1&0&0&1&1&0&0&1&1&0&0&1&1&0\cr p_{20}&0&0&0&1&1&1&1&0&1&1&1&0&% 0&0&0&1\cr}.$

5. Conclusion

To solve the problem of constructing a mathematical model of CDA, namely the synthesis of logic and the generation of solutions, standard methods and means of solving matrix equations or SLAE can be used. Modeling an $n$ -bit parallel adder was performed in the TensorFlow environment. TensorFlow presents computations in the form of dataflow graphs and allows one to transfer the implementation of resource-intensive computing tasks from a single CPU (Central Processing Unit) environment to a heterogeneous fast environment with several GPUs (Graphics Processing Unit) which is essential to achieve an acceptable computation time. The possibility of modeling based on TPU (Tensor Processing Unit) seems to be promising. Taking account of the capabilities of the CDA mathematical model, Tensor Flow is designed to provide massive parallelism and high scalability of machine training and solution generation. The possibility of implementing a mathematical model based on FPGA (Field-Programmable Gate Array) also can not be ignored.

Footnotes

Acknowledgments

The work was supported by the Ministry of Science and Higher Education of the Russian Federation, project RFMEFI57417X0173.

References

Kozhevnikov

V.V.

, The concept of mathematical modeling of cognitive digital automata, Scientific Notes of Ulyanovsk State University, Series: Mathematics and Information Technology 1(7) (2015), 48–53. (in Russian).

Murata

, Petri nets. Properties, analysis and applications, Proceedings of the IEEE 77(4) (1989), 541–580.