Modern engineering solutions attract attention of researchers to well-known problems in the eld of system theory and cybernetics in general. The realisation problem of a \black box" is one among these problems. In this paper the non-anticipation property for a \black box" is generalised to the case of \black boxes", whose behaviour admits deferred decisions. Furthermore, for such \black boxes" it is shown that they can be realised as pre-machines, which have been introduced by author jointly with his co-authors in series of earlier papers.
(1)
In this case there exists a Moore machine whose transfer function coincides with
the mapping M [
We should note the following: the previous formulation for the non-anticipation property implicitly implies that the \black box" responds immediately on each stimulus. However there are systems having another reaction type. It is quite possible such a system behaviour that requires to defer a response for as long as the su cient amount of the information will be received. For example, complex event processing systems (see [7]) have such a reaction type. Therefore processes of the speci cation and analysis for such systems require another models or at least models, which generalise already existing ones. This paper is an attempt to solve the realisation problem for \black boxes" with transfer function that satis es the generalisation being de ned below of the non-anticipation property. 2
The aim of this section is to give brief survey of some matters and explain the basic notation used below.
X ;
Further, we use the denotation juj for the length of the word u 2 X and assume that jxj = +1 for any in nite sequence x 2 X! .
To refer to the k-th member of a word u 2 X (or a sequence x 2 X!) the denotation u[k] (or x[k] respectively) is used.
For a word u 2 X whose length is equal or greater than n (or a sequence
x 2 X!) by u[1 : n] (or x[1 : n] respectively) we denote the word u[
Similarly, for a word u 2 X whose length is greater than or equal to n (or a sequence x 2 X!) by u[n : ] (or x[n : ] respectively) we denote the word u[n] : : : u[juj] (or the sequence x[n]x[n + 1] : : :). 3
In Sec. 1 we have given the de nition of the non-anticipation property for a transfer function from X! into Y ! under condition that the corresponding \black box" reacts on each stimulus. Our nearest goal is to generalise the previous de nition for the case when a \black box" is capable to decide whether the accumulated information is su cient for the correct response and generates the response if the decision positive otherwise postpones the response generation.
Firstly, it is needed to say that in this case the class of studied transfer functions are being extended up to the class of mappings from X! into Y 1 .
Further, we should specify that the identity of pre xes for streams of stimuli
guarantees the identity of pre xes for the corresponding streams of responses.
The sequential character of processing streams of stimuli by a \black box"
requires that there exists a correspondence between word of stimuli u (as pre x of
the corresponding streams) and length N (u) of the response word (see Fig. 1).
u = x[
N (u) ≤ n
The following de nition is our attempt to present these considerations as a formal speci cation.
De nition 1. We shall say that the non-anticipation property holds for a mapping M : X! ! Y 1 if the following is true: there exists a funtion N : X
! N such that 1. N (u) juj for any u 2 X ; 2. if u0 2 X and u00 = u0x for some x 2 X then 3. if x0; x00 2 u X! for some u 2 X then
N (u0)
N (u00)
N (u0) + 1 ; (M x0)[1 : N (u)] = (M x00)[1 : N (u)] ; 4. for any u 2 X there exist x0; x00 2 u X! such that
(M x0)[1 : N (u) + 1] 6= (M x00)[1 : N (u) + 1] : Remark 1. Informally, jump points for the function N introduced in Def. 1 determine response instants of the \black box". Items 3) and 4) ensure this interpretation.
Remark 2. Item 2) ensures that the \black box" corresponding to a mapping that holds the non-anticipation property generates at most one response at a stimulus.
Remark 3. Item 3) and 4) of Def. 1 guarantee also that the existence of function
Remark 4. One can easy see that if N (u) = juj then Def. 1 and the nonanticipation property given in Sec. 1 specify the same class of mappings. 9 > > > > > > > > > > > > > > > > > > > =
Now let us consider the partial mapping : X+ 99K Y that is de ned as follows (u) " i
N (u) = N (u[1 : juj (u) #= M (uz)[N (u)] i
N (u) > N (u[1 : juj
Require: a sequence of stimuli x 2 X! Ensure: to print the corresponding sequence of responses n = 1 while True : while (x[1 : n]) " : n + = 1 print( (x[1 : n])) n + = 1 Algorithm 1: \Black box" algorithm for a mapping M : X! ! Y 1 that holds the non-anticipation property Proposition 1. For any x 2 X! Algorithm 1 prints the sequence M x . Proof. Taking into account (2) one can easy see that new response is printed only if N (x[1 : n 1]) 6= N (x[1 : n]) . In this case the printed symbol is (M x)[n] . tu De nition 2. Let M : X! ! Y 1 be a mapping that holds the non-anticipation property then the corresponding partial mapping : X+ 99K Y we shall call its reaction function.
Conversely, we can consider a partial mapping : X+ 99K Y and use Algorithm 1 to de ne the mapping M : X! ! Y 1 .
Proposition 2. Let : X+ 99K Y be a partial mapping then the correspondence x 2 X! 7! y 2 Y 1 , when y is the sequence printed by Algorithm 1 under handling x , determines the mapping M : X! ! Y 1 that holds the non-anticipation property.
Proof. The key idea of the proof consists in the following recursive construction of the function N : X ! N : base of recursion: N (") = 0 ; step of recursion:
N (ux) =
N (u); if (x) " :
N (u) + 1; if (x) #
In this section we remind the de nition of automata as the simplest discrete
systems that respond on external stimuli by changing their states. Automata are
actions of free nitely generated monoids on the state sets from the mathematical
standpoint. In [
Automata
De nition 3. A triple A(X; SA; A) is called an automaton if X is a nite
alphabet of stimuli, SA is a set of states of the automaton, A : SA X ! SA
is a mapping, which is called the transition function of the automaton.
An automaton behaviour is determined by a right action of the monoid X
the state set SA [
A(s; ") = s for any s 2 SA ;
A(s; ux) = A( A(s; u); x) for s 2 SA; u 2 X ; x 2 X is a right action of monoid X
on the set SA .
A(s; u0u00) =
A( A(s; u0); u00) for any s 2 SA , u0; u00 2 X . Checking is a simple exercise in the application of mathematical induction on the length of u00 . (3) (4) tu 4.2
Pre-automata
The notion of a pre-automaton had been introduced in [
De nition 4. A triple P(X; SP ; P ) is called a pre-automaton if X is a nite alphabet of stimuli, SP is a set of states of the pre-automaton, P is a right partial action of the monoid X P : SP X 99K SP such that
on the set SP , i.e. it is a partial mapping 1. choose as SP an arbitrary subset of SA ;
s 2 SP and u 2 X let assign that
P (s; u) " if A(s; u) 2= SP and P (s; u) #= A(s; u) if A(s; u) 2 SP .
9 99K SP as follows for >>> = > > > ; (5) (6) tu Proposition 4. The triple de ned by construction (6) is a pre-automaton.
The assertion just proved demonstrates that the method to obtain preautomata consists in hiding part of the states.
The converse assertion proved in [
In this section we discuss the question about how a Moore machine or its generalisation, which we call a Moore pre-machine, can realise a \black box". 5.1
Moore Machines
De nition 5. Let A(X; SA; A) be an automaton then the corresponding Moore machine is a pentacle MA(X; SA; A; s0M; M) where s0M is some xed state of A called the initial state of the machine and M : SA ! Y is a mapping called the output function of the machine.
De nition 6. Let MA(X; SA; A; s0M; M) be a Moore machine then its reaction function M : X ! Y is determined by the formula
M(u) = M( A(s0M; u)) : (7)
Finally, we de ne the transfer function MM : X! ! Y ! for the machine MA using its reaction function M and Algorithm 1. 5.2
Moore Pre-machine Here we repeat all constructions from the previous subsection substituting a pre-automaton for an automaton.
De nition 7. Let P(X; SP ; P ) be a pre-automaton then the corresponding Moore pre-machine is a pentacle MP (X; SP ; P ; s0M; M) where s0M is some xed state of P called the initial state of the pre-machine and M : SP ! Y is a mapping called the output function of the pre-machine.
De nition 8. Let MM: PX(X+;9S9PK;Y Pi;ssd0et;ermined in the following manner
M M) be a Moore pre-machine then its reaction function
21.. MM((uu)) "#=if MM( (Ps(0Ms0M;u;)u"))anidf M(s0M; u) # . (8) Finally, we de ne the transfer function MM : X! ! Y 1 for the pre-machine MP using its reaction function M and Algorithm 1. 5.3
Posing of Synthesis Problem
The preceding arguments show that machines and pre-machines can be
considered as \glass boxes". It is known that machines are \glass boxes" for a proper
subclass of the class of all \black boxes" [
Problem 1 (Synthesis Problem). Suppose we have a mapping M : X! ! Y 1 that holds the non-anticipation property.
It is required to describe the properties of the mapping that ensure the existence of a pre-machine MP such that MM = M . 6
Solving the problems posed at the end of the previous section is given in three stages: rstly, some solution of the problem is constructed, secondly, this solution is reduced, and, nally, the minimality of this reduced solution is proved.
Taking into account the fact that the hypothesis of the problem includes the non-anticipation property for the mapping M we can consider the reaction function of the \black box" instead its transfer function.
Lemma 1. The triple F (X; SF ; F ) is an automaton such that the right action F : SF X ! SF associated with it satisfy the equation
F (u; v) = uv SF = X ; F (u; x) = ux for x 2 X and u 2 X . (9) (10) tu for all u; v 2 X .
Proof. Checking is reduced to a simple application of the mathematical induction.
F
SF in the following manner:
SF = fu 2 X j (sequ) #g S f"g : Now applying construction (6) and we obtain the pre-automaton F (X; SF ; F ) . Theorem 1 (Existence of Solutions for the Synthesis Problem). Let us consider the Moore pre-machine MF (X; SF ; F s0F ; F ) , where s0F = " ;
F (u) = (u) if
(u) # ;
F (") is de ned arbitrary ; then
MF
= .
Hence we need to prove that (u) # if and only if (u) # and the equality
MF (u) = (u) holds on the cMomFmon domain. But this follows immediately from Lemma 1 and the speci cation of the pre-machine MF . tu 6.2 Indistinguishability and Syntactic Pre-Machine The solution that is given in the previous subsection for the Synthesis Problem is too redundant because the state set of the corresponding pre-machine contains too many indistinguishable states. In this subsection we demonstrate the method to eliminate the lack of the construction.
Our consideration refers to some concepts of the theory of ordered sets. The necessary information can be found in [5, Chapter 1].
De nition 9. We shall say that u0 2 X can not be distinct from u00 2 X using (this assertion is below written as u0 . u00) if (u0w) # implies (u00w) #= (u0w) for any w 2 X .
Proposition 5. The relation \ . " is a quasi-order on X satisfying the following condition: if u0 . u00 and w 2 X then u0w . u00w .
Now suppose that u0 2 X , u00 2 X , w 2 X , and u0 . u00 .
If ((u0w)v) # for some v 2 X then u0 . u00 ensures (u00(wv)) #= (u0(wv)) and, therefore, ((u00w)v) #= ((u0w)v) . tu
Proposition 6. The assertions u0 .
u00 and (u0) # imply (u00) #= (u0) .
Proof. To verify the validity of the proposition it is su cient to put w = " in Def. 9.
De nition 10. Let u0; u00 2 X then we say that u0 and u00 are -congruent (this assertion is below written as u u00) if both u0 . u00 and u00 . u0 are true.
Proposition 7. The relation \ " is a right congruence on X that satis es the following property: if u0; u00 2 X and u0 u00 then (u0) # if and only if (u00) # and in this case (u0) = (u00) .
Proof. The fact that \ " is an equivalence relation follows from the properties of a quasi-order [5, Sec. 1.3]. Its stability relative to the right multiplication follows immediately from the similar property for the relation \ . ". Finally, the last assertion of the proposition follows from Prop. 6.
Let us de ne
A SA = X = ;
([u] ; x) = [ux] , Lemma 2. The triple A with it A : SA X ! SA where [ ] denotes a class of the -congruence, u 2 X , and x 2 X . Note that the property to be a right congruence for the equivalence \ " ensures the correctness of the de nition of A .
is an automaton such that the right action associated satis es the equation
A ([u] ; v) = [uv] for all u; v 2 X .
tu tu (11) (12)
fv 2 X j (v) #g or [u] T fv 2 X j (v) #g = ? :
S
SS = f[u] j u 2 X and (u) #g S f["] g : Hence we can again apply construction (6) and obtain the pre-automaton S (X; SS ; S ) .
Theorem 2 (about Syntactic Pre-machine). Let us consider the Moore premachine MS (X; SS ; S ; s0S ; S ) , where s0S = ["] ;
S S ([u] ) = (u) if (u) # ; (["] ) is de ned arbitrary ; then
MS = .
S Proof. Let us note that Prop. 7 ensures the correctness for the de nition of the mapping . Further, Lemma 2 guarantees the validity of = . MS tu Remark 6. We shall call the Moore pre-machine built in the theorem the syntactic pre-machine. 6.3
Syntactic Pre-machine as Minimal Solution of Synthesis Problem To complete the program indicated above, we need to establish the minimality of the pre-machine MS in any sense.
First of all, we note that the pre-machine MS holds evidently the following property called the reachability: one can obtain any state of the pre-machine applying its partial action to the initial state.
Theorem 3 (about Minimality of Syntactic Pre-machine). For any reachable Moore pre-machine MP (X; SP ; P ; s0M; M) such that M = there exists a mapping : SP ! SS satisfying the following conditions 1. for any s 2 SP and u 2 X the assertion P (s; u) # implies S ( (s); u) #= ( P (s; u)) ; 2. (s0M) = s0 ;
S 3. = S .
Let s 2 SP and u0; u00 2 X such that P (s0M; u0) #= s and P (s0M; u00) #= s then we can show that u0 . u00 .
Indeed, suppose that (u0w) # for some w 2 X . Taking into account that
M = we can write (u0w) = M( M(s0M; u0w)) : Note that the previous equality ensures M(s0M; u0w) # and therefore (5) leads to the conclusion that P ( P (s0M; u0); w)) # .
Using the supposition P (s0M; u0) #= s and (5) we obtain
THhenucse t(hue00swup)p#o=siti(oun0wP)(sa0Mnd;,ut0h0)er#e=fosrei,mup0l0ie.s Pu(0 .P (s0M; u00); w) #=
P (s; w) . (s) = [us] where s = P (s0 ; us) : M
tu 7
Thus, we can summarize that the paper gives the algebraic analysis for the problem of realisation \black boxes" by machines. The main results of the analysis are { the generalisation of the non-anticipation property for \black boxes" that accumulate information for decision; { the complete solution of the synthesis problem for such \black boxes".
The machines that realise the corresponding transfer functions are based on pre-automata. The class of such algebraic structures had been introduced by author jointly with Prof. M. Dokuchaev and Prof. B. Novikov in earlier papers.
It should be emphasized that issues dealing with computational properties of pre-machines has not considered in the paper. The coverage of these issues requires a separate study. 6. Trakhtenbrot, B.A., Barzdin, J.M.: Finite automata: behaviour and synthesis.
North-Holland Publishing Company, US (1973) 7. Zholtkevych, G., Novikov, B., Dorozhinsky, V.: Pre-automata and Complex Event Processing. In: Ermolayev, V. et al (eds) ICT in Education, Research, and Industrial Applications. CCIS, vol. 469, pp. 100{116. Springer International Publishing (2014)