In the paper some machine-learning method for synthesis an on- y event acceptor is proposed. Such an acceptor has become necessary for the technique of the on- y event processing. This technique is increasingly being used in the design of information systems of economic destination. In the paper the synthesis problem for such an acceptor is considered in a rigorous mathematical formulation. The method for solution of the problem and the computer experiment to study the method are described. The directions for the further research are proposed.
Modern Information Communication Technology (ICT) causes intensive
changes in, practically, all areas of human activity. These changes, in
particular, impose non-traditional restrictions for decision processes in the
eld of economy. New approaches for modelling economic processes such
as \econophysics" [
- 470
message detectors for systems built on EDA has been de ned and
considered in [
Here we describe the model proposed in [
Below we use the following notation: f : X 99K Y f (x) " f (x) # f (x) #= y
X+ X X! X1 x j j x[0] x[1 : ] denotes that f is a partial mapping from X into Y ; denotes that f (x) is not de ned for the member x of X; denotes that f (x) is de ned for the member x of X; denotes that f (x) # and y = f (x) for the member y of Y ; denotes the empty (zero-length) sequence; denotes the set of all non-empty nite sequences composed of elements of X; denotes the set f g S X+; denotes the set of all in nite sequences composed of elements of X; denotes the set X S X!; denotes the length of the nite sequence x; denotes the rst element of a nite or in nite sequence x; denotes the sequence obtained by removing the rst element of the sequence x. De nition 1. For a nite set X a subset L of X is called a language and, in the context, X is called an alphabet, and its members are called symbols.
We interpret symbols as a prime messages informing that the
corresponding elementary event has happened. Some nite sequences of symbols
inform about complex events and below these sequences are called events.
Other nite sequences of symbols do not carry information about
complex events and below we call them words. Sets of complex events must
meet the certain conditions. The most important of these conditions is
that any stream of elementary events is uniquely subdivided into a series
of complex events by directed viewing the stream from left to right. This
condition leads to the requirement that L is pre x-free [
Let us brie y remind the principal tenets of the used model. Any component of a system based on EDA is modelled by using the concept of a CEP-machine.
De nition 2 (Structure of CEP-machine). Any CEP-machine is a quintuple M = (X; Y; H; h0; ) with the following constituents: { the alphabet of atomic messages X, which is a nite set; { the alphabet of machine responses Y , which is a nite set; { the set of handlers H, which is a nite set, whose each member is a partial mapping h : X+ 99K Y such that its domain is a pre x-free language; { the initial handler h0, which is some xed element of H; { the response function , which is a mapping with domain Y and codomain H.
The general behaviour of any CEP-machine is described in [
De nition 3 (Regular handler). A handler h : X+ 99K Y is called regular if there exist some nite set Z with the marked element z0 2 Z and some mapping : Z X ! Z S Y such that for any u 2 X+ and y 2 Y the condition h(u) #= y is ful lled i there exist z1; : : : ; z juj 1 2 Z such that zi+1 = (zi; u[i]) for 0 y = (z juj 1; u[juj 1]): i < juj 1 and In this case we say that the handler h is realized by the triple (Z; z0; ). Remark 1. It is evident that a handler is regular if there exist a nite state machine realising it.
ular if all its handlers are regular. 2.3
In practice we propose restrict our technique by methods of synthesis for regular CEP-machines. This restriction is caused by technical and theoretical di culties of more general technique. Further, it is evident that the synthesis problem for a regular CEP-machine is decomposed into series of synthesis problems for regular handlers each of which has only one possible response \accepted". In this case we use the term \a regular acceptor" instead the term \a regular handler". Thus, a machine-learning problem for synthesis process of a regular handler can be formulated in the following manner.
Problem. Let E = fu1; : : : ; uM g be a nite pre x-free set of nite sequences composed by elements of X and C = fv1; : : : ; vN g be a nite set of nite sequences composed by elements of X such that E T C = ? then we interpret elements of set E as examples and elements of set C as counterexamples; we need to nd a regular acceptor h : X+ 99K facceptedg such that 1. h(ui) #= accepted for all 0 i < M ; 2. h(vi) " for all 0 i < N ; and 3. the corresponding set Z has the least number of elements among all possible. 3
Here we present a method to build a regular acceptor and describe a computer experiment that instills con dence in the existence of a mathematical justi cation for this method. We premise our presentation with a few simple theoretical results. The techniques used to prove these results are quite common in automata theory therefore we omit the corresponding proofs for simplicity of the presentation. First of all, let us return to Remark 1 and discuss more detail the interrelation between regular acceptors and nite state machines. Namely, if we consider for any regular acceptor h : X+ 99K Y that realized by the triple (Z; z0; ) the machine (Q = Z S Y Sfqtrapg; X; : Q X ! Q; q0 = z0; Qaccept = Y ) where qtrap 2= Z S Y and (y; x) = qtrap; (qtrap; x) = qtrap for any x 2 X and y 2 Y then the regular language accepted by this machine coincides with the set of events accepted by the regular acceptor. After this brief theoretical review, we can return to our problem. The general view of the method to nd an acceptor is presented by Alg. 1. This method consists of the series of redirections for acceptor transitions leading into the trap starting with the minimal acceptor for the set of examples. Two functions used by the algorithm init and modify are speci ed separately.
To complete the speci cation of the proposed method we need to describe algorithms for the function init (see item 3 of the Alg. 1) and for the function modify (see item 7 of the Alg. 1).
Function init. To build the minimal acceptor the following ideas are used: 1. states of the acceptor are de ned recursively as special sets of words; 2. we choose the set E as z0 and add it to Z; 3. we choose the empty set as trap; 4. if for x 2 X in E there is not a word with the rst symbol x then assign (z0; x) = trap else the set fu 2 X j xu 2 Eg add to Z; 5. repeat recursively this consideration for all member of Z until Z is stabilized; 6. denote the set f g by accepted.
The acceptor obtained in this manner is assigned as a result of the function init.
Algorithm 1. Speci cation of the proposed method 1 def learning method(E; C):
Require : the nite pre x-free set of events E
the nite set of words that are not events C
Ensure : the required acceptor 2 do that: 3 initiate the learning process by applying function init to the set E and denoting the result by acceptor # initialize the set of transitions that cannot be redirected 4 frozen transitions = set() 5 while halting condition is not fulfilled: 6 do that: 7 modify acceptor by redirecting a transition leading into the trap and minimize the resulting acceptor wherein the redirected transition cannot belong to frozen transitions 8 do that: 9 check that acceptor is admissible in the sense that it does not accept any word from C if the checking is successful: continue else: do that: roll-back the modi cation and add the redirected transition
into frozen transitions
Function modify. To select a transition for redirection we use the
following simple remark: the minimal regular acceptor has at most one state
that is an attractor, i.e. any transition that goes out from this state has
this state as a target. Moreover, if this acceptor accepts a nite language
then the existence of the attractor is guaranteed. Further, to minimize
the new acceptor we use standard Hopcroft's algorithm [
Thus, we assume that the described above method gives a solution of our problem. To check reasonability of this assumption we designed the computer experiment for searching counterexamples to the assumption. The Alg. 2 speci es the schema of the experiment. 3.4
To implement the mentioned experimental schema we have used language
Python with libraries \scipy" and \numpy" [
The presented paper cannot be considered as a complete research. The obtained results are preliminary, but they are very important because they demonstrate a chance to substitute the complete logical analysis of situation by the learning on the examples and counterexamples during software development of the on- y processing systems. Also these results make the need for further research in the following directions: future experimental study of the proposed method in order to clarify the boundaries of its applicability; nding rigorous formulations of the method convergence conditions; mathematical justi cation of the method; evaluation of the e ectiveness of the method.
Acknowledgement. The authors thank Prof. Gregoriy Zholtkevych for the idea proposed to them: to use machine learning methods for the synthesis of the logical structure of the on- y event processing mechanism.