Method of Yanov of the analysis of closed-loop processes

1. Background

    In 1958 the collection [1] of Academy of Sciences of the USSR published almost entirely (!) the master's thesis of Yanov of Yu.I - then the junior researcher of IPM (Moscow): it was the first successful attempt of formal determination of criterion of rather strict equivalence of the logical networks of algorithms (LNA). For this purpose the Yanov for each operator of LSA entered 'shifts' - a set of logic variables in binary logic which only the operator of LSA also can change. Criterion of equivalence of two LSA – coincidence of the functions of shifts calculated by recursive procedure for their same operators. Attempts numerous, conferences to find out a physical essence of functions of shifts were not crowned with success.
    The physical sense entered by Yanov of these concepts establishing for LSA is set by work [4]. Here instead of LSA more general logical network of computation process (LNCP) with classical model in the form of an abstract synchronous state machine [2] without an exit with the corresponding powerful and laconic mathematical apparatus was used. The concept 'input signal of such automatic machine' is adequate to a set of various values of the logic variables (LV) of LSA and, thus, LSA changed by the operator are not limited to two-digit logic and the LP list. In the LSVP model the concept 'shifts' ('distribution of shifts') is replaced with broader definition of 'restriction on an automatic machine input' (the generator in terminology of article [4]): for each of any subset of backgrounds of behavior of the automatic machine length of no more k enters a set of admissible signals, one of which at the next moment (clock pulse) of time can be (and only!) it is given on an automatic machine input provided that by this moment the automatic machine passed this background.

Retreat! When giving on an input of the automatic machine of the sequence x … y … z of signals the automatic machine passes a statuses … b … with. The sequence of x/a pairs, …, by y/b, …, z/c we will determine as history and any final segment of this sequence, for example, of y/b, …, z/c as background of behavior of the automatic machine. Automatic machine definition range - a set of the various stories of his behavior beginning with some of its initial fixed (initial) status of the automatic machine

For lack of such restriction (by default) this set is considered matching a set of various input signals of the automatic machine – their alphabet. Work [4] defines such LSVP model as the k/B-automatic machine. The main properties of such automatic machines (the section of work [4] of the same name) were received by repetition of a method [1] of Yanov one to one. At the same time the laconicism of language of the theory of abstract state machines [2] allowed to specify – to strengthen a formulation of basic provisions (lemma) of this method, without changing the scheme of their proofs. It is as a result entered concepts of a covering (see further item 4) automatic machine definition range, and then and its minimum covering defining physically number of steps of iteration for which functions evaluation of shifts of LSA and similar determination in LSVP is reached. This number of steps matches the maximum length (the number of x/a pairs) of history in the minimum covering.
    In 1975 Yanov was not successful in attempt to combine efforts of both schools - Moscow regarding a research of operator schemes of algorithms (academician Yershov) and Kiev in the analysis of discrete transformers. (academician Glushkov). - "Young man! You have 3 minutes to state the main point" - the director of IPM academician Yablonsky warned in advance, having put before me hours. Then I was not ready to it and, it seems, only the Yanov - the initiator of a meeting came to state of shock.

2. The Yanov method in the analysis of closed-loop processes

    Unfortunately, authors of work [4] (and your servant including) did not pay attention to that fact that the restrictions introduced by them on an input of the automatic machine are a peculiar and at the same time natural method of formal determination of a feedback. It especially could not notice Yanov as entered 'shifts' even not for background of length of 1 (k=1) of behavior of LSA, but only for the operator of LSA of this background executed by the last – a status of a submachine gun (LSVP) in terminology of work [4]. – And it is kind of a 'degenerate' case of a feedback.

    The applicability of a method of Yanov for the determined processes using k/B-automatic machine model is proved by works [4] and [5], repeating this method [1] practically without changes. In the same place the method of Yanov is interpreted for probabilistic 1/B-automatic machines (k=1). Let's consider applicability of a method to the analysis of probabilistic k/B-automatic machines at k> =1, avoiding bulky mathematical calculations of works [4] and [5] and having limited to concepts of their implementation (essence):

1) In each cell [i, j] junction arrays [2] automatic machines a set of the signals defining transition from Ai status to Aj according to [3.4] we replace with the list of values arranged alphabetically input signals conditional (on condition of achievement of a status of Ai) transition probabilities (from Ai in Aj) for each of them, including value 0 for otsustvuyushchy signals in a cell [i, j]. It is clear, that the amount of values of each of such lists is equal to 1.

2) Restriction for each of various backgrounds of behavior of the automatic machine is considered as the generator of the next input signal with the probability determined similarly (1) now. Also 1 amount of values of the list of probabilities is here too equal

3) When giving on an input of a deterministic automaton of the sequence of V= { x1, x2, …, xN } xI signals (I=1, …, N) the automatic machine passes the only S= corresponding to the sequence of statuses { a1, a2, …, aN } and this process we will define as the display V-> S. Now (the probabilistic automatic machine) this display is not one-to-one and it is about calculation of probability  of P(V-> S)  the display V-> S which is executed on the basis of (1), (2) and elementary data of probability theory

4) In case of a deterministic automaton and LSVP [4] the analog of function of shifts for sostoyaniya'a' the automatic machine is a set of signals ‘x’ (a set of LP values in terminology of LSA) for which exists (an event!) the history of behavior of the automatic machine which is coming to the end 'x/a'. In case of probabilistic automatic machines the set of such signals is defined as the probabilities of the specified events for them issued in the list identically (1) and (2). At the same time receiving such 'functions of shifts' happens all according to the same scheme offered by Yanov, including home positions - lemmas 1 and 2 works [1]

3. Convergence of calculations by the Yanov method

    The convergence of functions evaluations of shifts (the analysis of LSA and LSVP) for the determined processes (LSA, LSVP, etc.) was actually set by Yanov. The convergence of similar calculations (method) for probabilistic 1/B-automatic machines (k=1) is considered by works [4.5]. Here we will try to prove convergence for the processes modelled by probabilistic k/B-automatic machines for k> 1, avoiding, as well as above, bulky mathematical calculations, having limited to concepts of their implementation. For this purpose it is enough to transform the probabilistic k/B-automatic machine to a simple Markov (ergodic) process, equivalent on action, [6]:

a) Let's determine various backgrounds by length, smaller or equal k, and for each of them list (2) of item 2. probabilities. In the absence of such list (by default) this list for the alphabet (a set of various) of input signals consists of identical values for the signals formed by division 1 on their quantity (alphabet power). For the purpose of preserving of equality of 1 amount of values of this list on an error of such distribution of value 1 by alphabet elements as appropriate we adjust any element of the list

b) We create a matrix of statuses of a Markov process [6], marking these statuses (lines and columns of a matrix) with backgrounds (a) – in an identical order of a line and columns

c) In a cell of a matrix (b) on transition from a status of A (line) of a Markov process to a status of B (column) it is calculated (we put down) transition probability only in the following cases:

• length of La of background of A is less than k (La<k) и предыстория B является продолжением /предыстории A на один шаг, т.е. длина Lb=La+1, где Lb - длина предыстории B
• La=k, Lb=k and initial segment length of k-1 of background of B matches final segment of background A same lengths of k-1

It is clear, that in both cases of A has an appearance‘ …, y/b’ and B -’ …, y/b, z/d’

According to (1) - (4) item 2 the transition probability from A in B is defined as the work of probability from the list (a) of background of A for a signal of z of the last element of background of B on probability from the list (1) of transition of the k/B-automatic machine from b status (the last element of background A) in d status on z signal on an input of initial <k/B>- the automatic machine. We place the calculated transition probability from A in B in a cell of a matrix (b) on intersection of line A and column B

d) We place 0 (zero) in the cells blank by calculations (c)

(1) and (2) items 2 agree, (c) and (d) the amount of values of cells of every line of the received matrix is equal to 1. Therefore, this matrix generally with a huge number of statuses describes ergodic process

4. Practical application of a method in the analysis of LSVP

Work [4] formally enters a k/B-automatic machine definition range covering as a compact regular form of record of various stories of his behavior. Externally (flowgraph) such structure is hierarchical, it is convenient in the basis (skeleton) displaying a tree of simple ways – behavior stories from not repeating x/a pairs. The covering allows to avoid need to build the k/B-automatic machine in accuracy answering to the stated above its determination and specific LSVP analyzed using the computer. It is enough to develop uniform convenient (user) language of the description of LSVP, the processing of this description allowing the computer to receive the minimum covering of definition range of the k/B-automatic machine corresponding to this LSVP. Avoiding parts [4] we will note the next highlights (essence):

1) In each pair 'x/a' of history of behavior of the automatic machine under ‘x’ a set of their current values arranged by identifiers LP is understood. The status of 'a' of the automatic machine is associated with the operational block (OB) of LSVP in which on an input the set 'x' of LP values is defined

2) The Logic Block (LB) has several exits marked by disjunctive conditions in the form of DNF and also values of time delays on switching on an exit. These conditions refer to the LP current values and only! In effect LB define switchings between OB (instead of an automatic machine junction array)

3) ABOUT contains afterbirths
atelnost of transactions (difference from [4]), each of which turns on:

• transaction accomplishment condition
• transaction of the specification (assignment of value) of one or several LP
• conditional probability of transaction
• a time delay - time for transaction

4) Prior to the beginning of the analysis the set of original values of LP and the operational block started by the first is defined

5) Initial (4) form L=0 level of the created covering of the only pair 'x/a' - the beginning of all stories of behavior of the modeling LSVP of the automatic machine

6) The following L+1 level forms serial generation of various continuations of 'y/b' (in behavior stories) from each pair 'x/a' of current level L on one step from excellent from 0 probability. However y/b pair joins in new L+1 level only if it is absent in a covering – the created new L+1 or already created levels. Anyway the initial pair 'x/a' contacts the separate link its continuation – the new or found y/b pair. The link is marked with the probability and runtime of transaction – generation of 'y' the block 'b'. This time (delay) is filled up with a delay on switching (LB) from OB 'a' to ‘b’

7) Unlike exits of LB and developments [4.5] (!) the condition in OB 'a' uses not only the LP current values, but also LP values on an input of OB, previous ‘a’ in background length of no more k – the parameter of the k/B-automatic machine defined at start of process of formation of a covering. For this purpose communications between pair 'x/a' also it agrees (6) generated by it 'x/b' in a covering are entered bidirectional. Such LP are preceded (prefix) in a condition by a name of this OB previous in background. Moreover, such condition may contain only the requirement of existence of the necessary OB in background (without the instruction LP). Such accounting (back references from 'y/b' to 'x/a' and further) coming to the end x/a pair backgrounds long no more k in already created part of a covering allows to reduce the number of LP and much more to reduce a set of various sets of their values and, therefore, the covering size

8) Process of formation of a covering comes to an end at an empty next layer of the created covering. Owing to (6) in the created covering of pair 'x/a' do not repeat

    Analysis results are:

a) removal not active (absent in a covering) blocks (OB and LB), exits of LB and transactions ABOUT

b) simplification of conditions at the exits of LB and in transactions ABOUT only accounting of not used LP and OB values in a covering

c) calculation of probability and time of achievement of different OB and return to them (cycle)

In strict accordance with [4] calculation are made over the tree of simple ways (TSW) – behavior stories without the repeating pairs 'x/a' in a hierarchical structure of a covering. At the same time numerical marks of links (6) DPP, selected and obkhodimy on a circuit are used by the known classical methods [7].

    High-speed performance of calculations actually is defined by strata on formation of a covering and mainly at a stage (6) transaction of search of the created next y/b pair in already created part of a covering. This problem is removed use of an associative memory of a covering which can be implemented both physically, and programmatically in the multipurpose computer. Such memory (associations) can effectively use an inner pattern ‘x’ (a set of LP values) pairs 'x/a' of a covering, the effective codes 'a' (OB) and, at last, distribution of pairs 'x/a' by coat layers

Literature

1. Yu.I. Yanov, About logical networks of algorithms, On Saturday. Cybernetics problems, Fizmatgiz, Moscow, 1958, issue 1
2. Gill A. Introduction to the theory of finite state machines: The lane with engl. - M: Science, 1966.
3. Bukharayev R.G. Probabilistic automatic machines. The Kazan state. university, 1970.
4. Dodonov A.G., member correspondent of AN of USSR, Patrikeev V.L., Method of computerized analysis of posledovatelnostny computation processes. – zh.: Electronic modeling. – Kiev, 1986, No. 3
5. Patrikeev V.L., Abstract of the thesis 'Method and organization of computing structure for the analysis of computation processes and systems', UDC 681.34:519.673, Kiev, 1986
6. Dynkin E.B., Markov processes, Fizmatgiz, M., 1953
7. Svami M., Tkhulasiraman K., Graphs, networks and algortma, M. Mir, 1984.
8. Baytser B. Mikroanaliz of the capacity of computing systems: The lane with engl. – M.: radio and communication, 1984.