SCIENTIFIC ABSTRACT KUZNETSOV, O. P. - KUZNETSOV, P. I.

• Document Type: CREST
• Collection: Scientific Abstracts
• Document Number (FOIA) /ESDN (CREST): CIA-RDP86-00513R000928130003-5
• Release Decision: RIF
• Original Classification: S
• Document Page Count: 100
• Document Creation Date: November 2, 2016
• Document Release Date: June 20, 2000
• Sequence Number: 3
• Publication Date: December 31, 1967
• Content Type: SCIENTIFIC ABSTRACT

XL=OVj T.Do, - ------------
List of foreign literature on relay devices and finite automata
for 1958. Avtom. I, telex. 21 no.9:1332-1338 S 160.
(MIRA 13:10)
(Bibliography-Automatic control)

33505
3/562/61/000/009/005/012
1/21/ /3%q, D201/D302
9;L
AUThOR: Kuznetsov, 0. P.
TITLE: Asynchronous logical nets
SOURCE: Akademiya nauk SSSR. laboratoriya sistem peredachi in-
formatsii. Problemy peredachi informatsii. No. 9, 19610
Elementy sistem avtomatiki, 103-115
TEXT: The author gives an analysis of a logical net in which the
delays are not equal and which he calls asrchronous nets. Two
types of binary elements are introduced: a Logic elements and b)
elements of delay which operate as follows: The inputs and the pro-
duction.of outputs are continuous. The value of the output of a lo-
gic element at instant t is represented by a certain logic function
of its inputs at instant t. The delay element has one input Y. 1)
The value of the delay output y(t) at instant t is given by 1)
W)0=0c(c = 1 or c = 0); 2) y changes at instant t + V from 0 to 1
1 t ) only if at the instant t Y has changed from 0 to I (or 1
to 0) and remained uncharged during the interval from t to t +T'.
Gard 1/2

33505
3/562/61/000/009/005/012
Asynchronous logical nets D201 D302
Vis called the delay time. The net obtained from elements of type
a) and b) by using the rules of forming "regular construction nets"
is called the asynchronous logical net (ALN). The sequence of in-
put signals is called the input sequence, if to every two adjacent
signals in the sequence there corresponds two last periods. The
state of the ALN at instant t is an orderly sequence y (07.90;
Yn(t) at instant t of outputs from the delays. The time interval
between two adjacent changes of state is called the period. The se_~
quence of n-dimensional vectors 0 or 13 is called the ALN state se-
quence, The ALN correspond to relay operated circuits with delays
of various duration and may find practical applications. There are
3 figures and 5 references: 3 Soviet-bloc and 2 non-Soviet-bloco
The reference to the English-language publication reads as follows:
A. W. Brooks and G. B. Wright, The theory of logical nets, Proc.
IRE9 1953, v. 41, 10.
Card 2/2

KAZAKOV, V.D.; 2TFTT~~
Idst of Russian works on the theory of switching circuits and finite
automata for 1959. Avtom. i telem. 22 no.2.-275-277 F 161.
(MIRA 14:4)
(Bibliogra~hy-Automatio control)
(Bibliography--Switching theory)

.-- ) -0 . 01
"On a certain class of regular events"
report submitted:br the Intl. Symposium on Relay Systems and Finite Automata Theory
(IFAC), Moscow, 24 Sep-2 Oct 1962.

_01-
,A '".-rIn-1959 at-the-Matbematical-_
Institute ImcnL V. A. Stekloy, AcadovW of
sciences Luaff- "The use of computer for
research in mechanical translation" (Invited
paper, Session 9)
of Automatics and
Inst"Afte
!E;-lPerEiwgc-hLmldLcnK,L$Acadejq of Sciences USSR LT90
position7. "on the anyrichronous logical circuits"
(Session 11 or 20)
HI
V. G., Read, Economic C~bernatie
6iijiifir Center, Academy of Sciences
k~tion,
Ukrainian 80, Kiev �196i poationj- "A method-,
of ouccessiYe analysis of variants for numerical
solution of the problem of optimal planning and
designing" (Session not indicated)
Institute of Mathematics and
Computation Center, Siberian Department, Academy
of Sciences USSR, Novosibirsk - "Investigation of
the vritten language of ancient Maya with the aid
of computers" (Session 38)
SPIRIN, A. A., Scientific Fesearch Institute of
i~~r ka;hine Building, moacovC19a positio_n7-
"Achnical means and orsudzation of centralized
system for data grocessing In Industry" (Session 25)
.7D4)FEM1",_AA fRecelyed Candidate's degree In 1961
from Moscow Higher Technical 64ool imeni N. E.
Baumanj. "Microprogramming control in digital
computers" (Session 42)
report to be submitted for the 2nd Intl. Congress for Infbrwtion Proceaaing,
Rmich, West Germany, 27 Aug 1 Sap JqQe
A,

LGANOV, Ve-D.1 KMNETSOV, O.P.
ww~
List of foreign literature on the theory of switching devices
and finite automata for 1959-1960. Avtom. i telem. 24 no .5:
699-712 My 163. (MIn 16:6)
Bibliography-Switching theory)
Bibliograpby-Automatic control)
Bibliogrspby-Zlectric rows)
~

ACCESSION NR: AT4031764 5/0000/63/000/000/0074/0099
AIM,1011: Kuznotsov. O.P.
TITLE: Relay devices and finite automata
SOURCE: ANSSSR. Strukturnaya teorlya releyny*kh ustroystv (Structural theory of
relaydevices). Moscow, Izd-voANSSSR, 1963, 74-99
TOPIC TAGS: control system, automatic control, feedback, relay, automaton,
finite automaton, black box problem
ABSTRACT: The article deals with several fundamental results achieved in the theory 6f
automata and their interpretation in terms of relay devices. In the first section of the
paper, the author has analyzed different models of finite automata, the concept of the
event and the formulation of the problem of synth6sis. It is shown that the evolution of
the theory of such automata began with the investigation of abstract nerve nets (W.
McCulloch, W. Pitts. A logical calculus of ideas immanent in nervous activity. "Bull.
Math. Biophys. ", v. 4. S. 1943, p. 115-123; S. Kleene. Representation of events in
nerve nets and Infinite automata. Automata Studies Princeton, 1956). The concept of
the "finite automaton!' (a term Introduced for the first time by S. Kleene) Is examined.
Card 1/7 . . I

ACCESSION NR: - AT4031764
The Moore model (Moore sequential machine) is discussed and described (E. Moore.
Gedanken-experiments on sequential maphines. Automata Studies. Princeton, 1953) and
the Mealy model. is defined (G. Mealy. 4 metho(j, for synthesizing sequential circuits.
"Bell System Tech. J, 11 v. 34, no. 5, p.-. 1045-1079). The work of Yu. T. Mendeleyev
on events representable in finite automata is placed in proper perspective in terms of the
general discussion of the problem (Yu. T. Mende,leyev. 0 klass6 soby*tiy, dopuskayush-
chikh predstavlenlye v konechnom avtorr4te. Sb.~I"Avtomaty*", dobavleniye 2, 1956)
The application of the flow table, introduced by D. Huffman (D. Huffman. Synthesis ~f
sequential switching circuits. :J. Franklin Institute, v. 257, no. 3, p. 161-190; no. 4.
p. 275-303, 1954), to the investigation of sequential relay devices Is discussed and the
use of such tables is described. Various definition *s of an "event" are given. These
definitions are taken, for the most part, from the writings of Kleene and Mendeleyev.
In this connection, the importance of the concept of "regularity" (in terms of a regular
event) is shown to be determined by the following.two theorems: 1) For every regular
event there exists a finite automaton to represent it; 2) Every event representable in
some finite automaton is regular. Both theorems are proven and discussed. Further
theorems (again taken primarily from the work of S. Kleeno referenced above) are
analyzed in terms of the algorithmization of abstract automata synthesis according to a
given finite system of regular events; fori example,: For every definite event there
Card 2/7

ACCESSION NR: AT4031764
wdsts a nerve net withotit loops: atul, for every given nerve not without loops and every
given internal neuron of this not, excitation of this neuron Is equivalent to the advent of
soma definite event. The work, in this area, of V. M. Glushkov (V. M. Glushkov. Ob
odnom algoritme sinteza abstraktny*kh avtomatov. Ukr. matem. zhurnal, no. 2, 190)
is considered, along with an analysis of the technical applications of the theory of abstract
nerve nets to the theory of logical circuits. Logical and delay elements are considered,
and it is shown that the physical realization of logical nets is found in devices with pulse
condition, in which the transmission of information is possible in one direction only. The
author notes that, after the problem of representability had been solved in principle (by
S. Kleene), two fundamental problems of automata synthesis have emerged: the search for
various languages in which to write the dvents and the construction of automata to porfo~m
assigned operating conditions with a minimal number of states. An analysis is given of
certain of the results achieved in this area by Yu. T. Mendeleyev, N. Ye. Kobrinskiy and
B. A. TraMten. brot (N. Ye. Kobrinskly, B. A. Trakhtenbrot. 0 postroyenil obshchey
teorii logicheskikh sotey. Bb. "Logicheskiye issledovaniya", 1959), A. Church in a num-
ber of articles. E. Berkley (E. Berkley. The algebra of states and events. "Amer. Math,
Monthly", v. 78, no. 4, 1954) and others. The author's view of this problem area may,
perhaps, be summarized as follows: In the synthesis of singlo-cycle devices, for the
Inscription of the operating conditions a standard language is employed - a Boolean func-
tion, assigned in the form of a formula or a table. The problem of synthesis thus is
Card 3/7

ACCESSION NR: AT4031764
reduced to one of minimization. For automata, i~ynthesis becomes more complex. While
for single cycle devices it Is always possible to assign a finite list of input symbols and
corresponding outputs, the list of possible symbol sequences (that is, an event) may be
infinite, and its structural or design assignment resolves itself to &.e problem of devising
(constructing) a language in which infinite lists are given by finite formulae. The second
source of complexity Is seen by the author in the fa6t that not all events are susceptible
of representation, In an automaton - whence the second requirement of the language: in it
it must be possible to distinguish representable events from those which cannot be repro-
sented. In the language of regular events, this problem Is solved in a simple fashion:
non-representable events are not described In it; that Is, the very fact that a formula
exists which corresponds to a certain event is evidence of the representability of that
event. However, the author notes, this Is not always the case. For example, In a
languagre in which it is possible to describe all events (such a language will contain recur-
sive definitions) the problem of recognizing the r6resentability of events cannot be solved
algorithmically. With respect to the advantages of the languages proposed by the various
authors and considered in this article by way of reylew, that Is, the possibilities of a
simple transition from a verbal formulation of tho!conditions of operation to an economical
base formula, it is, In the author's view, sensel6s to search for a universally simple
language, since problems will always be found which can be more simply described by
4/7
Card

ACCESSION NR: AT4031764
another language. The selection of one language over another will In all likelihood be
determined not by individual and separate problems, but by the possibility and ease with
which a large number of different working conditions can be classified by the terms of
the particular language. 7he second part of the article deals with the analysis and
minimization of finite automata. The so-called "black box" problam is considered, with
the author presenting the results, employed, as he claims, without strict proof, by
H uffman, in the formulation of G. Mealy... The author concludes that, according to the
theory of finite automata, a relay contact system is a particular form of finite automaton.
The circuitry of the automaton is derivedby assigning to each state a binary number repre-
senting an ordered set of intermediate eldment states. Since this attribution is arbitrary
(with the limitation that one number.canndt be'ascillbed in two states), corresponding to
an automaton, given by a flow table, ;,bill be an Infinite number of devices, different In
structure but equivalent In action. Ile particular attribution depends on our require-
ments of the structure of the device: do we wish completely to eliminate race conditions,
obtain a maximally simple logic part of the device, achieve protection against a given
number of faults on the part of the elements of the device, etc. It is, however, preferable
to minimize the number of states before the attribution. In this case, all methods of
finite automata minimization are applicable to relay-contact devices. On the other hand,
the methods of synthesis existing in the theory of automata cannot be unconditionally ap-
plied to such devices, since these methods effectively synthesize not the abstract finite
Card 6/7

ACCESSION NR: AT4031764
automaton,that ls,.'tho flow matrix (or table), but particular instance of the finite auto-
maton - the logical net; that Is, a synchronous automaton.' Asynchronous automata,
however, (particularly, relay-contact devices) differ from the synchronous in a number
of properties, cognooted with the fact thq, asynchronous automata operate not In pulse,
but in potential mode. In rum, the fundainental problems of the first. step in the synthesis
of relay-action devices (ending with the coding of the states) may, in the opinion of the
author, be formulated as iollows:. 1) Thp search for effective logico -mathematical
languages which will make it possible to write the operating conditions in terms of input
and output sequences and to obtain, from ihis method of writing, tables which will define
the automaton; -that is, a state table (flow table) and output table. 2) The minimization
of the flow table of the automaton, for which not all input sequences are permissible.
3) Optimal state coding by binary numbers in order to reduce the number of logical ele-
ments of the automaton (in the case of a relay-contact system - the minimization of the
contact part), and to secure the construction of reliable structures and the .)limination
of race conditions. Orig. art. has: 11 tables, 11 formulas and 12 figures.
ASSOCIATION: None
Card
6/7

ACCESSION NR: AT4031765 S/0000/63/000/000/0100/0109
AUTHOR: Kuzaetsov, 0." P.
TITLE's'One class of regular events
SOURCE: AN SSSR. Struktumaya*taoriya releyny*kh ustroystv (Structural th6ory of relay
devices). Moscow, Izd7y~o AN SSSR, 1963, 10D-109
TOPIC TAGS: control obtem, automatic control, relay,' regular event, nerve net, finite
automaton
ABSTRACT: The concept of the regular event was introduced by S. ICeene (Representation
of events in nerve hets and finite automata. Princeton, 1956), who demonstrated that the
clasq of regular events coincides with the class of events which may be represented i~ a
fWtd automaton. This Iresult was later refined CV. M. Glushkov. 0b odnom, algoritine
sinteza abstraktay*kh avtomatov. Ukr. matem. zhurnal, no. 2, 1960) and it was shown that
for any system of regular events, containing N letters of thelaput alphabet, an automaton
can be constructed to rp-resent this system, with a num];er of states.,< 211N + 1. While It
1/3
Card ;,

ACCESSION NR: AVOJ~765
can e6:rsily be demonsttit1d that the nurAber of states car] be ieduced by a facto'r of four, its
exact yalue is as yet un~ipar. Noting t~e In;'erest in detdrm4iing the subclass4le of regular
events with a simpler eiftmation of the umber of statos*,of the corresponding siutoniatio
devic6's, the author hag:Jiven such an e timite in the 'present article for a class of ddiaite
(in the' sense of Meen%,~eqe reference a. ove) occurrencep; that is, occurrences of the type
A, where J Is a uiil6n of all the lettors -of the alphaUt~t. $ad A Is a formula which con-
tains no iterations. The approach to the problem rests on the assumption that the automaton
is represented by a trafisition diagram (flow table), that Is, by an oriented graph, the apices
of whi6h correspond to the states, and the ribs - to the transitions from one state to the
other '; Corresponding tq-.each such graph the author postulates a matrix C of unions and a
matrix C* of paths (0. P. K117-netsov. Releyny*ys ustroystva I konecWye avtomaty* (this
collecdon)), Element 43i, of matrix C 19 the union of thei-weights of all the rlbs~'Ieading -
from state si to state sp tlement a * Is the union of all the paths leading from a to aIt
Is evident that a -a c In the m~4ix of the automaton for any 1, J, and k we ~:)e c1 C
J:F--_ ik-
This iatio exp~jiseV iho condition of Unambigulty of the trapsitions in the automaton, The
following thsorezn~,is advanced in the articlot Let there be given a systm of U ocaurences
(I)Anp .(5)
Card

ACCESSIC.- AT4031765,
where A A. are formulas containing no iterations; Is a met of all the words fil the
input al;labet, Then the minimum number of states of an automaton representing s~stezn
(5) by outputs 1... q- , respectively, will not exceed N + 1. where N Is the total number of
letterp in the divergen of the formula..
The'idea of t~e' afjo~rlthm *fEr ~o`nstruq`t_in_g*this' auitoma't6n Is6ontainedl in the following evident
leImma: Let there be even an event ~, and--an automaton, in which there is separated an
Initial state s and a subset of states F, such that- 1) for any state a of the automaton every!
word PA(- A lits the device from state s to sF(- F; 2) every word which shifts the device
from s 0 to sF can be represented In the form P 1PA, w~ercL P 3~