=Paper=
{{Paper
|id=None
|storemode=property
|title=Realisation of "Black Boxes" Using Machines
|pdfUrl=https://ceur-ws.org/Vol-1356/paper_32.pdf
|volume=Vol-1356
|dblpUrl=https://dblp.org/rec/conf/icteri/Zholtkevych15
}}
==Realisation of "Black Boxes" Using Machines==
https://ceur-ws.org/Vol-1356/paper_32.pdf
Realisation of “Black Boxes” Using Machines
Grygoriy Zholtkevych
Department of Theoretical and Applied Computer Science,
V.N. Karazin Kharkiv National University
4 Svobody Sqr, 61022, Kharkiv, Ukraine
g.zholtkevych@karazin.ua
Abstract. Modern engineering solutions attract attention of researchers
to well-known problems in the field 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.
Keywords: “black box”, deferred responses, sequential processing, pre-
machine, transfer function
Key Terms: Computation, Software Component, Specification Process,
Mathematical Model
1 Introduction
Let us suppose that two finite alphabets X and Y are given. The first of them
we identify as the alphabet of stimuli and the second one as the alphabet of
responses. Following to the general cybernetic concept [1, Chapter 6] we can
consider any mapping M : X ω → Y ∞ as the transfer function of some “black
box”, whose inputs belong to the set X ω of infinite sequences of stimuli and
outputs belong to the set Y ∞ of finite or infinite sequences of responses. The
realisation problem of such a mapping using a machine is the principal problem
that is solved by a system engineer. In other words a system engineer transforms
a “black” box into a “white box” or “glass box”.
The realisation problem had been studied in detail (see, for example, [6]) for
the mapping M : X ω → Y ω holding the following non-anticipation property1
if M (ux0 ) = y 0 , M (ux00 ) = y 00 for some finite sequence of stimuli
u = u1 u2 . . . un and x0 , x00 ∈ X ω then y 0 = vz 0 and y 00 = vz 00 for (1)
some finite sequence of responses v = v1 v2 . . . vn and z 0 , z 00 ∈ Y ω .
In this case there exists a Moore machine whose transfer function coincides with
the mapping M [4, 6].
1
This property informally means that a “black box” cannot use an information from
the future.
We should note the following: the previous formulation for the non-anticipa-
tion 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 sufficient amount of the information will be received. For example, complex
event processing systems (see [7]) have such a reaction type. Therefore processes
of the specification 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
satisfies the generalisation being defined below of the non-anticipation property.
2 Prerequisites and Notation
The aim of this section is to give brief survey of some matters and explain the
basic notation used below.
At the paper we use the denotation N for the natural series with 0 .
For a set X (it is usually finite) we use the notation:
X ∗ denotes the set of all finite sequences (words) whose elements belong
to X ;
ε denotes the empty word;
X + denotes the set X ∗ r {ε} ;
X ω denotes the set of all (infinite) sequences whose elements belong to
X;
X ∞ denotes the union of the sets X ∗ and X ω .
Further, we use the denotation |u| for the length of the word u ∈ X ∗ and
assume that |x| = +∞ for any infinite sequence x ∈ X ω .
To refer to the k-th member of a word u ∈ X ∗ (or a sequence x ∈ X ω ) the
denotation u[k] (or x[k] respectively) is used.
For a word u ∈ X ∗ whose length is equal or greater than n (or a sequence
x ∈ X ω ) by u[1 : n] (or x[1 : n] respectively) we denote the word u[1] . . . u[n]
(or x[1] . . . x[n]).
Similarly, for a word u ∈ X ∗ whose length is greater than or equal to n (or
a sequence x ∈ X ω ) by u[n : ] (or x[n : ] respectively) we denote the word
u[n] . . . u[|u|] (or the sequence x[n]x[n + 1] . . .).
3 Non-anticipation Property
In Sec. 1 we have given the definition 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
definition for the case when a “black box” is capable to decide whether the
accumulated information is sufficient 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 ∞ .
Further, we should specify that the identity of prefixes for streams of stimuli
guarantees the identity of prefixes for the corresponding streams of responses.
The sequential character of processing streams of stimuli by a “black box” re-
quires that there exists a correspondence between word of stimuli u (as prefix of
the corresponding streams) and length N (u) of the response word (see Fig. 1).
u = x[1]x[2] . . . x[n] y[1]y[2] . . . y[N (u)]
“Black box”
N (u) ≤ n
Fig. 1. A sequential “black box”
The following definition is our attempt to present these considerations as a
formal specification.
Definition 1. We shall say that the non-anticipation property holds for a map-
ping M : X ω → Y ∞ if the following is true:
there exists a funtion N : X ∗ → N such that
1. N (u) ≤ |u| for any u ∈ X ∗ ;
2. if u0 ∈ X ∗ and u00 = u0 x for some x ∈ X then
0 00 0
N (u ) ≤ N (u ) ≤ N (u ) + 1 ;
0 00 ω
3. if x , x ∈ u · X for some u ∈ X then ∗ (2)
(M x0 )[1 : N (u)] = (M x00 )[1 : N (u)] ;
∗ 0 00 ω
4. for any u ∈ X there exist x , x ∈ u · X such that
0 00
(M x )[1 : N (u) + 1] 6= (M x )[1 : N (u) + 1] .
Remark 1. Informally, jump points for the function N introduced in Def. 1 de-
termine response instants of the “black box”. Items 3) and 4) ensure this inter-
pretation.
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
N for the mapping M : X ω → Y ∞ implies the uniqueness of N .
Remark 4. One can easy see that if N (u) = |u| then Def. 1 and the non-
anticipation property given in Sec. 1 specify the same class of mappings.
Now let us consider the partial mapping µ : X + 99K Y that is defined as
follows
µ(u) ↑ iff N (u) = N (u[1 : |u| − 1])
µ(u) ↓= M (uz)[N (u)] iff N (u) > N (u[1 : |u| − 1]) .
Item 3) of Def. 1 ensures the uniqueness of determining µ(u) .
Remark 5. Returning to Fig. 1, we note that µ(u) = y[N (u)] .
To determine the significance of the mapping µ let us consider the following
algorithm and proposition.
Require: a sequence of stimuli x ∈ 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 ∞ that holds
the non-anticipation property
Proposition 1. For any x ∈ 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] . t
u
Definition 2. Let M : X ω → Y ∞ 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 define the mapping M : X ω → Y ∞ .
Proposition 2. Let µ : X + 99K Y be a partial mapping then the correspondence
x ∈ X ω 7→ y ∈ Y ∞ , when y is the sequence printed by Algorithm 1 under han-
dling x , determines the mapping M : X ω → Y ∞ 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 (u), if µ(x) ↑
N (ux) = .
N (u) + 1, if µ(x) ↓
Now, easy seen that the mapping M holds the non-anticipation property. t
u
4 Automata and Pre-automata
In this section we remind the definition of automata as the simplest discrete
systems that respond on external stimuli by changing their states. Automata are
actions of free finitely generated monoids on the state sets from the mathematical
standpoint. In [3] authors have introduced the notion of a pre-automaton using
a generalisation of the notion of an action known as a partial action. Taking
into account that these notions is used below and they are not widely used we
include this section to give the information necessary for understanding of the
further text.
4.1 Automata
We start our consideration reminding the definition of an automaton.
Definition 3. A triple A(X, SA , δA ) is called an automaton if X is a finite
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 ∗ on
the state set SA [2].
Proposition 3. Let A(X, SA , δA ) be an automaton then the defined recursively
∗
defined mapping δA : SA × X ∗ → SA
∗
δA (s, ε) = s for any s ∈ SA ; (3)
∗ ∗ ∗
δA (s, ux) = δA (δA (s, u), x) for s ∈ SA , u ∈ X , x ∈ X (4)
is a right action of monoid X ∗ on the set SA .
Proof. To prove the proposition it is sufficient to check the equality
∗
δA (s, u0 u00 ) = δA
∗ ∗
(δA (s, u0 ), u00 )
for any s ∈ SA , u0 , u00 ∈ X ∗ . Checking is a simple exercise in the application of
mathematical induction on the length of u00 . t
u
4.2 Pre-automata
The notion of a pre-automaton had been introduced in [3] by replacing the action
with the partial action in the definition.
∗
Definition 4. A triple P(X, SP , δP ) is called a pre-automaton if X is a finite
∗
alphabet of stimuli, SP is a set of states of the pre-automaton, δP is a right
partial action of the monoid X ∗ on the set SP , i.e. it is a partial mapping
∗
δP : SP × X 99K SP such that
∗
1. δP (s, ε) ↓= s for all s ∈ SP ;
∗
2. if δP (s, u0 ) ↓ and δP
∗ ∗
(δP (s, u0 ), u00 ) ↓ then
∗
δP (s, u0 u00 ) ↓= δP
∗ ∗
(δP (s, u0 ), u00 ) ;
(5)
∗
3. if δP (s, u0 ) ↓ and δP
∗
(s, u0 u00 ) ↓ then
∗ ∗
δP (δP (s, u0 ), u00 ) ↓= δP
∗
(s, u0 u00 ) .
4.3 Interrelations between Automata and Pre-automata
In this section we describe some method that allows us to construct a pre-
automaton using an automaton.
Suppose that we have taken some automaton A(X, SA , δA ) .
∗
Let us define the pre-automaton P(X, SP , δP ) in the following manner:
1. choose as SP an arbitrary subset of SA ;
∗ ∗
2. define the partial mapping δP : SP × X 99K SP as follows for
∗
s ∈ SP and u ∈ X let assign that (6)
∗ ∗
δP (s, u) ↑ if δA (s, u) ∈
/ SP and
∗ ∗ ∗
δP (s, u) ↓= δA (s, u) if δA (s, u) ∈ SP .
Proposition 4. The triple defined by construction (6) is a pre-automaton.
Proof. Indeed, item (3) ensures that item 1) of (5) is satisfied.
Further, Prop. 3 implies that items 2) and 3) of (5) are satisfied. t
u
The assertion just proved demonstrates that the method to obtain pre-
automata consists in hiding part of the states.
The converse assertion proved in [3] as Globalisation Theorem ensures that
the method considered above is the most general method to obtain pre-automata.
5 Moore Machines and Pre-machines
In this section we discuss the question about how a Moore machine or its gen-
eralisation, which we call a Moore pre-machine, can realise a “black box”.
5.1 Moore Machines
Usually, automata associate with “black boxes” in the following manner.
Firstly, the class of Moore machines is defined.
Definition 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 fixed state of
A called the initial state of the machine and λM : SA → Y is a mapping called
the output function of the machine.
Then for a Moore machine is determined its reaction function.
Definition 6. Let MA (X, SA , δA , s0M , λM ) be a Moore machine then its reac-
tion function µM : X ∗ → Y is determined by the formula
µM (u) = λM (δA (s0M , u)) . (7)
Finally, we define 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.
Firstly, the class of Moore pre-machines is defined.
∗
Definition 7. Let P(X, SP , δP ) be a pre-automaton then the corresponding Mo-
∗
ore pre-machine is a pentacle MP (X, SP , δP , s0M , λM ) where s0M is some fixed
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.
Then for a Moore pre-machine is determined its reaction function.
∗
Definition 8. Let MP (X, SP , δP , s0M , λM ) be a Moore pre-machine then its
+
reaction function µM : X 99K Y is determined in the following manner
∗
1. µM (u) ↑ if δM (s0M , u) ↑ and
∗ ∗ (8)
2. µM (u) ↓= λM (δP (s0M , u)) if δM (s0M , u) ↓ .
Finally, we define the transfer function MM : X ω → Y ∞ 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 consid-
ered as “glass boxes”. It is known that machines are “glass boxes” for a proper
subclass of the class of all “black boxes” [4, 6]. Therefore we pose the following
problem.
Problem 1 (Synthesis Problem). Suppose we have a mapping M : X ω → Y ∞
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 Synthesis Problem
Solving the problems posed at the end of the previous section is given in three
stages: firstly, some solution of the problem is constructed, secondly, this solution
is reduced, and, finally, 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.
6.1 Existence of Solution
Thus we assume that two alphabets (the input alphabet X and the output
alphabet Y ) and a partial mapping µ : X + 99K Y are given.
Let us choose
SF = X ∗ ;
(9)
δF (u, x) = ux for x ∈ X and u ∈ X ∗ .
Now consider the triple F(X, SF , δF ) .
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 (10)
for all u, v ∈ X ∗ .
Proof. Checking is reduced to a simple application of the mathematical induc-
tion. t
u
µ
Now let us choose SF ⊂ SF in the following manner:
µ
= {u ∈ X ∗ | µ(sequ) ↓} {ε} .
S
SF
µ
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
µ∗ 0
consider the Moore pre-machine MµF (X, SF
µ
, δF sF , λµF ) , where
s0F = ε ;
λµF (u) = µ(u) if µ(u) ↓ ;
λµF (ε) is defined arbitrary ,
then µMµF ∼
= µ.
Proof. Really, MµF is a Moore pre-machine.
Hence we need to prove that µMµF (u) ↓ if and only if µ(u) ↓ and the equality
µMµF (u) = µ(u) holds on the common domain. But this follows immediately
from Lemma 1 and the specification of the pre-machine MµF . t
u
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].
Definition 9. We shall say that u0 ∈ X ∗ can not be distinct from u00 ∈ X ∗ using
µ (this assertion is below written as u0 .µ u00 ) if µ(u0 w) ↓ implies µ(u00 w) ↓=
µ(u0 w) for any w ∈ X ∗ .
Proposition 5. The relation “ .µ ” is a quasi-order on X ∗ satisfying the fol-
lowing condition: if u0 .µ u00 and w ∈ X ∗ then u0 w .µ u00 w .
Proof. Reflexivity and transitivity of the relation is evident.
Now suppose that u0 ∈ X ∗ , u00 ∈ X ∗ , w ∈ X ∗ , and u0 .µ u00 .
If µ((u0 w)v) ↓ for some v ∈ X ∗ then u0 .µ u00 ensures µ(u00 (wv)) ↓= µ(u0 (wv))
and, therefore, µ((u00 w)v) ↓= µ((u0 w)v) . t
u
The following simple property of “ .µ ” is used below.
Proposition 6. The assertions u0 .µ u00 and µ(u0 ) ↓ imply µ(u00 ) ↓= µ(u0 ) .
Proof. To verify the validity of the proposition it is sufficient to put w = ε in
Def. 9. t
u
Definition 10. Let u0 , u00 ∈ 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 satisfies
the following property: if u0 , u00 ∈ 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. t
u
Let us define
µ
= X ∗ / ≡µ ;
SA
µ (11)
δA ([u]µ , x) = [ux]µ ,
where [·]µ denotes a class of the µ-congruence, u ∈ X ∗ , and x ∈ X . Note that
the property to be a right congruence for the equivalence “ ≡µ ” ensures the
µ
correctness of the definition of δA .
µ µ
Now consider the triple Aµ (X, SA , δA ).
Lemma 2. The triple Aµ is an automaton such that the right action associated
µ∗ µ µ
with it δA : SA × X ∗ → SA satisfies the equation
µ∗
δA ([u]µ , v) = [uv]µ (12)
for all u, v ∈ X ∗ .
Proof. The lemma is easy proved by induction on the length of v . t
u
Now we can note that Prop. 7 ensures one of the alternatives:
either [u]µ ⊂ {v ∈ X ∗ | µ(v) ↓} or [u]µ {v ∈ X ∗ | µ(v) ↓} = ∅ .
T
This remark allows us to choose SSµ ⊂ SA
µ
in the following manner:
SSµ = {[u]µ | u ∈ X ∗ and µ(u) ↓} {[ε]µ } .
S
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 pre-
machine MµS (X, SSµ , δSµ ∗ , s0S , λµS ) , where
s0S = [ε]µ ;
λµS ([u]µ ) = µ(u) if µ(u) ↓ ;
λµS ([ε]µ ) is defined arbitrary ,
then µMµS ∼
= µ.
Proof. Let us note that Prop. 7 ensures the correctness for the definition of the
mapping λµS . Further, Lemma 2 guarantees the validity of µMµS ∼ = µ. t
u
Remark 6. We shall call the Moore pre-machine built in the theorem the syn-
tactic 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 MµS in any sense.
First of all, we note that the pre-machine MµS 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.
Now let us formulate the main result.
Theorem 3 (about Minimality of Syntactic Pre-machine). For any reach-
∗
able 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 ∈ SP and u ∈ X ∗ the assertion δP
∗
(s, u) ↓ implies δSµ ∗ (ψ(s), u) ↓=
ψ(δP (s, u)) ;
2. ψ(s0M ) = s0S ;
3. µ ∼
= µS µ ◦ ψ .
Proof. The key item of the proof is the construction of the mapping ψ .
Let s ∈ SP and u0 , u00 ∈ X ∗ such that δP
∗
(s0M , u0 ) ↓= s and δP (s0M , u00 ) ↓= s
0 00
then we can show that u .µ u .
Indeed, suppose that µ(u0 w) ↓ for some w ∈ X ∗ . Taking into account that
µM ∼= µ we can write µ(u0 w) = λM (δM ∗
(s0M , u0 w)) .
∗
Note that the previous equality ensures δM (s0M , u0 w) ↓ and therefore (5) leads
∗ ∗ 0 0
to the conclusion that δP (δP (sM , u ), w)) ↓ .
∗
Using the supposition δP (s0M , u0 ) ↓= s and (5) we obtain
µ(u0 w) = λM (δP
∗ ∗
(δP (s0M , u0 ), w)) = λM (δP
∗
(s, w)) .
∗
This equation ensures δP (s, w) ↓ .
Hence the supposition δP (s0M , u00 ) ↓= s implies δP
∗ ∗ ∗
(δP (s0M , u00 ), w) ↓= δP
∗
(s, w) .
00 0 00 0
Thus µ(u w) ↓= µ(u w) and, therefore, u .µ u .
Similar reasoning gives u0 .µ u00 and, therefore, u0 ≡µ u00 .
Now we can define ψ in the following manner:
∗
ψ(s) = [us ]µ where s = δP (s0M , us ) .
Checking the validity of items 1)–3) for the constructed mapping ψ is a simple
exercise now. t
u
7 Conclusion
Thus, we can summarize that the paper gives the algebraic analysis for the prob-
lem 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.
References
1. Ashby, W.R.: An introduction to cybernetics. Chapman & Hall, London (1956)
2. Clifford, A.H., Preston, G.B.: The Algebraic Theory of Semigroups, Volume 1.
AMS (1961)
3. Dokuchaev, M., Novikiov, B., Zholtkevych, G.: Partial actions and automata. Alg.
and Discr. Math. 11, 51–63 (2011)
4. Glushkov, V.M.: Some problems in the synthesis of digital automata. USSR Com-
putational Mathematics and Mathematical Physics. 1(3), 399–446 (1962)
5. Harzheim, E.: Ordered Sets. Springer Science+Business Media Inc., New York
(2005)
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 Indus-
trial Applications. CCIS, vol. 469, pp. 100–116. Springer International Publishing
(2014)