In the paper, the machine learning method for synthesis regular pattern detectors proposed early by authors is studied. This method can be used in event processing systems. This paper, in contrast to the previous one, is focused on studying the mathematical properties of concepts related to the method. The main result of the paper is proofs of theorems grounding that the method leads to the required result sometimes. The estimation of a probability for success is not considered in the paper.
Introduction The widespread development of cloud computing and Internet of Things (IoT) leads to an increase in the share of cyber-physical systems of all the variety of software systems. The distribution, heterogeneity, and the variability of the composite of components and relationships between them are distinctive features for systems of this class. Thus, the architecture of these systems should provide mechanisms to plug and unplug components, recon guration of relationships, and synchronisation of component behaviours.
It is known that event-driven architecture is a good choice is known that event-driven architecture is a good choice for meeting the requirements mentioned above. In this context, the problem of controlling event streams is very important and may be considered even as the main one.
Thus, a stream of events is a very important concept for cyber-physical
systems and distributed software systems in whole. The validity of this statement
is caused by the practice of developing controlled asynchronously distributed
systems. This practice led to the reference architecture for event-driven systems
(see [
Creating an event processing subsystem for each component of a distributed software system lies in the focus of the system developers. Therefore, e cient tools for specifying the valid system component behaviour and recognising violations of the validity are needed.
We need to underline that there is a contradiction between the complexity to specify and check the behaviour requirements of the system components and the necessity to do fast these processes. An attempt to overcome this contradiction is discussed in the paper. 2
State of Art
The idea to use inductive methods for overcoming the mentioned above
contradiction was rstly formulated in [10]. This idea has arisen as a result of developing
the mathematical theory of some generalisation of automata called pre-automata
and their applications in software engineering [
In [11], the machine learning method for the synthesis of special class event detectors was proposed and experimentally studied. 2.1
Remind that we consider the class of machines, which we call regular pattern detectors. A member of this class is de ned as follows.
De nition 1. A regular pattern detector is a tuple R = h ; Q; q0; ; i where ! is a nite alphabet of input signals;
q0 2 Q is a xed state called initial;
is some nite alphabet whose elements mark the corresponding patterns; : Q + Q is called the decision function 1.
Below we consider non-empty words 2 over alphabet as events (more precisely, messages about event occurrences) and denote the set of events by +.
To de ne the -indexed family R+ = fRs+ j s 2 g of event sets being detected by the pattern detector R we extend the decision function up to the partial mapping 3 + : Q + 99K + Q de ned recursively as follows +(q; a) #= (q; a) for any q 2 Q and a 2 ;
+(q; ua) " if either +(q; u) #= s where s 2 +(q; ua) #= (q0; a) if +(q; u) #= q0 where q0 2 Q: or +(q; u) "; 1 The sign \+" denotes here and below the disjoint union of sets. 2 The necessary de nitions and notation are given in Appx. B. 3 The necessary de nitions and notation see in Appx. A.
De nition 2. We say that an event u 2 + is detected by a regular pattern detector R as a sample of the pattern s 2 (symbolically, u 2 Rs+) if +(q0; u) #= s.
In oTthheurs,wtohreds, R-ins+de=xefdu f2ami+ly jR++(q=0;fuR) s+#=j ssg2for gallofs s2ubse.ts of + is associated with any regular pattern detector R. Properties of this family are established by the next proposition.
Proposition 1. For any regular pattern detector R, the holds the following properties -indexed family R+
s2 Proof. For proving the rst item let us suppose that for some u 2 +, the statements u 2 Rs+1 and u 2 Rs+2 are true where s1; s2 2 and s1 6= s2. By de nition of the family R+, it means that +(q0; u) #= s1 and +(q0; u) #= s2 and, therefore (see Def. A1), s1 = s2. This contradiction proves the rst item. To prove the second item let us construct a nite acceptor As = hQs; q0; Fs; si that recognises exactly words from Rs+. We de ne Qs = Q + + f?g where ? is used to refer to the special trash-state; the initial state of the detector q0 is the initial state of the acceptor being constructed; the subset of acceptable states Fs Qs is the singleton fsg; the transition function s : Qs ! Qs acts on a pair (q; a) as follows s(q; a) = (q; a) for any q 2 Q and a 2 s(s0; a) = ? for any s0 2 and a 2 s(?; a) = ? for any a 2 : ; ; Now one can easily see that Rs+ coincides with the set of words being accepted by As.
To prove the third item let us assume u 2 S Rs+ and uv 2 S Rs+ for some s2 s2 v 2 +. The rst statement ensures that +(q0; u) #= s for some s 2 and, therefore, for any v 2 +, we have +(q0; uv) ". This contradiction gives the required proof. tu The inverse statement is also true. We will prove this fact later using the technique presented below. 2.2
The idea of the synthesis method consists of the follows
Rs+ for all s 2 we have some nite alphabet of signals and some nite alphabet of recognisable pattern ; we x a -indexed disjoint family fEs j x 2 g of nite subsets of + with the pre x-free union and a nite subset C + of event messages being considered as undetected, moreover, E T C = ? where E = S Es; s2 we search a regular pattern detector R = h ; Q; q0; ; i such that 1. Es ; 2.
T Rs+
T C = ?; s2 3. the number of elements of Q is less or equal of the number of states for any detector satisfying 1 and 2.
This idea led the authors of [11] to Algorithm1.
Algorithm 1: Synthesis Method
Data: a -indexed family E of nite sets of + with the pre x-free union and a nite set C of + disjointed with the union of E
Result: a regular event detector R The like-tree detector h ; Q; q0; ; i mentioned in item 1 of Algorithm 1 is de ned as follows
Q = u 2
j uv 2 q0 = ; (?; a) = ? for all a 2 (u; a) = ua if ua 2 Q; (u; a) = ? otherwise
; followed by minimisation of Hopcroft's Method.
S Es for some v 2 s2
Sf?g;
Parallel Joint of Regular Pattern Detectors In this section, we describe a construction that allows simplifying the problem being studied and restricting the studying by the simple detectors called acceptors.
Let us assume that we have n (n > 1) regular pattern detectors denoted by Ri = h ; Qi; q0;i; i; ii with the same alphabet of input signals for i = 1; : : : ; n.
In this case, we de ne the regular pattern detector R = h ; Q; q0; ; i as follows Q = f?g + Q1 : : : Qn; q0 = (q0;1; : : : ; q0;n);
= 1 [ : : : [ n; (?; a) = ? for all a 2 ; ((q1; : : : ; qn); a) = ( 1(q1; a); : : : ; n(qn; a)) if i(qi; a) 2 Qi
for all i = 1; : : : ; n; ((q1; : : : ; qn); a) = ? ((q1; : : : ; qn); a) = s if i(qi; a) 2= Qi implies i(qi; a) = s
for all i = 1; : : : ; n; otherwise: As above, the symbol ? is used to refer to a trash-state, which is not a member of any Qi.
It is easy to understand that R is really a regular pattern detector. This detector is below called the parallel joint of the detectors R1,. . . ,Rn (symbolically, n R = i.=/1 Ri).
Below we use this de nition to demonstrate that any -indexed family of subsets of + satisfying the conditions of Prop. 1 can be represented as R+ for a regular pattern detector R, which is a parallel joint of primitive, in some sense, regular pattern detectors called regular pattern acceptor.
De nition 3. A regular pattern detector A is called a regular pattern acceptor if the correspondence set of patterns is a singleton.
It is evident that Prop. 1 ensures the following properties of the set A+ formed by word accepted by A: this set is regular and pre x-free. The following theorem shows that the converse fact is also true.
Theorem 1. Any regular and pre x-free subset F regular pattern acceptor A. + is the set A+ for some Proof. Considering F is regular let us take the minimal nite-state acceptor M = h ; Q; q0; F; F i6 that recognises words belonging to F and only such words. The minimality of M ensures the existence exactly one state q? 2= F such that 1. F (q?; a) = q? for all a 2 ; 2. for any q 2 Q such that q 6= q? and u 2
F (q0; uu0) 2 F for some u0 2 .
Further, if q 2 F then taking into account that F is pre x-free one can conclude that F (q; a) = q? for all a 2 . Hence, the the minimality of M ensures that F = fqag for some qa 2 Q .
Let us now de ne Q0 = Q n fqag , = f g , and (q; a) =
F (q; a) if F (q; a) = qa otherwise Thus, A = f ; ; Q0; g is a regular pattern acceptor and one can easily conclude that A+ equals F . tu
Now we are ready to prove the statement converse to Prop. 1.
Theorem 2. Let and be any nite alphabets, F be a subsets of + and this family holds the conditions -indexed family of + ,
F (q0; u) = q implies that 1. F is a mutually disjoint family; 2. each member of F is a regular set; 3. the set S Fs is pre x-free
s2 then there exists a -indexed family A = fAs j s 2 g of regular pattern acceptors such that Rs+ = Fs for all s 2 where R = ./ As. s2 Proof. Since the union of all Fs is pre x-free, each Fs is pre x-free too. Moreover, each Fs is regular therefore Theorem 1 ensures for each s 2 , the existence of a regular pattern acceptor As such that As+ = Fs. The condition that F is a mutually disjoint family ensures immediately the equality Rs+ = Fs for all s 2 where R = s2./ As. tu
Combining Prop. 1 and Theorem 2 one can easily obtain the following. Corollary 1. For any nite alphabets and , a -indexed family F of subsets of + is the family associated with some regular pattern detectors if and only if the following conditions hold 1. F is a mutually disjoint family; 2. each member of F is a regular set; 3. union of all member of F is a pre x-free subset of +. 4
Speci cation of Regular Pre x-free Sets The results obtained above allow further us to restrict our consideration by the class of regular pattern acceptors. Therefore, the theorem is proven in this Algorithm 2: Synthesis Method for Acceptors
Data: a pre x-free nite set E of
Result: a regular event acceptor A section is the Main Theorem of the paper. It gives a method to specify any regular pre x-free set by two nite word subsets.
We begin with a specialised synthesis method, represented by Algorithm 1 for event pattern acceptors (see Algorithm 2 below).
The like-tree acceptor A0 = h ; Q; q0; i mentioned in item 1 of Algorithm 2 is de ned as follows
Q = fu 2 q0 = ; (?; a) = ? for all a 2 (u; a) = ua if ua 2 Q; (u; a) = ? otherwise
; j uv 2 E for some v 2 g Sf?g; followed by minimisation of Hopcroft's Method.
Further, we need some auxiliary notion. The de nition and proof of two important properties are presented here.
De nition 4. For any alphabet u 2 L is L-prime if for any u1; u3 2 implies u1u3 2= L.
and a subset L and u2 2
+, we say that a word +, the equation u = u1u2u3
containing exactly L-prime words is pre x-free. +, the subset Pm L
L Proof. Indeed, if word u = u0u00, where u0 2 Pm L and u00 2 + , belongs to Pm L then the representation u = u0u00 ensures that u0 = u0 2= L. The obtained contradiction proves the proposition. tu
and a regular subset L +, the subset Proof. According to the pumping lemma for regular languages [6, Lemma 8, p. 119] (see also, [5, Sect. 4.6, p. 166]) there exists an integer n > 1 depending only on L and such that any word u 2 L of length at least n can be represented as u1u2u3 , where u1; u3 2 , u2 2 + , lng u1u2 n , and u1u3 2 L. Consequently, all words longer than n are not L-prime. Obviously, there are a nite set of words with length less than n, accordingly set Pm L is also nite.
Now we are ready to formulate and obtain the main results of the paper. Theorem 3. Any regular pattern acceptor A = h ; Q; q0; i can be reached by using Synthesis Method speci ed by Algorithm 2 with set E equal to Pm A+ . Proof. Since Pm A+ is pre x-free and regular according to Propositions 2 and 3, it can be used as set E for Synthesis Method.
Taking into account that after each iteration of the loop 2{12 in Algorithm 2 1. the acceptor A has at most one ine cient state 2. the number of its states does not increases, tu tu one can use breadth- rst search method in the graph of the target acceptor for the sequential rede ning transition function of the like-tree acceptor built in accordance with item 1 of Algorithm 2. This process leads evidently to the target acceptor.
Note that in the proof of Theorem 3 we assigned C = ?. Therefore, we do not
have any guarantees that Algorithm 2 halts after reaching the target acceptor.
However, we prove that there exists some nite subset C + disjointed to
Pm A that provide the correct termination of the algorithm. We use methods of
general topology to choose C. All necessary de nitions and facts can be found
in any textbook (for example, in [
Theorem 4. For any regular event pattern acceptor A, a nite set C + that allows to exactly restore acceptor A with the set Pm A+ as E using Algorithm 2 exists.
Proof. Let us consider the set ! formed by in nite sequences of elements of . It is evident that the family fu ! ! j u 2 +g, where u ! is formed by sequences with pre x u, is a base of a topology. This topology is Tikhonov topology on ! considered as the countable power of in the assumption that the last is equipped with the discrete topology. Tikhonov Theorem guarantees that the space under consideration is compact. It is this fact that we need in the proof.
Further, let ? denotes the unique ine cient state for acceptor A. One can divide ! into two disjoint components ! = C1 S C2 as follows a sequence s 2 ! belongs to C1 if all and only if for some its pre x u 2 the equation +(q0; u) =? is ful lled; a sequence s 2 ! belongs to C2 if all and only if for any its pre x u 2 either +(q0; u) " or the equation +(q0; u) #= x implies x 6=?. + + It is evident that C1 =
S u u2A? 1. +(q0; u) #=? and 2. for any proper pre x u0 of u the equation ! where A? is formed by such u that +(q0; u0) #=? is not ful lled.
Further, one can easily conclude that C2 is open in Tikhonov topology. Indeed, if a sequence s 2 C2 then there exists some pre x u of s and u0 2 such that +(q0; uu0) #= . But in this case, any s0 2 uu0 ! belongs to C2 and, therefore uu0 ! C2.
Openness of C2 ensures closedness of C1. Moreover, the family fu ! j u 2 A?g is an open covering of C1. Thus, compactness of ! ensures the niteness of A? and, therefore, we can assign C = A? for Algorithm 2.
It is evident that this choice ensures reaching exactly A under using Algorithm 2. tu
Theorem 1, Theorem 2, Theorem 3, and Theorem 4 ensure the following fact. Main Theorem. For any regular pattern acceptor A, the nite pre x-free set Pm A+ and the nite set A? (see proof of the previous theorem) determine uniquely the language A+ by using Algorithm 2. 5
Conclusion The paper examines the method of machine learning proposed earlier by the authors, designed to synthesise regular pattern detectors based on training sets.
In the paper, the method for decomposing an arbitrary regular pattern detector into prime ones has been grounded. These prime regular pattern detectors have been called regular pattern acceptors and characterised as detectors with the single output. It has been established that any recognition problem for regular pattern detectors can be reduced to the recognition problems for the corresponding acceptors (Theorems 1 and 2).
The use of these facts allowed to prove the main result of the work, justifying to reach the required acceptor using the previously proposed Synthesis Method speci ed for the case of acceptors (Theorems 3 and 4).
Thus, we have proven that the Synthesis Method based on Machine Learning Technique proposed in [10,11] leads sometimes to the required result. The next step of studying is to estimate the probability of success of the synthesis process and understand whether a good probability for success gotten experimentally in [11] is grounded.
Appendix A
Partial Mappings This section contains the de nitions and notation that are relating to the concept of a partial mapping and used above.
De nition A1. A partial mapping f from a set X into a set Y (symbolically, f : X 99K Y ) is the triple hX; Y; f i where f X Y if this triple satis es the condition
for all x 2 X and y0; y00 2 Y; hx; y0i 2 f and hx; y00i 2 f imply y0 = y00: Notation A1. Let X and Y be sets, and f : X 99K Y then for any x 2 X, f (x) " f (x) # f (x) #= y means that hx; yi 2= f for any y 2 Y ; means that hx; yi 2 f for some y 2 Y ; means that hx; yi 2 f where y 2 Y .
We use the symbol to refer to any partial mapping of the form hX; Y; ?i. Appendix B
Alphabets and Words This section contains the de nitions, notation, and facts that are relating to the concept of a word and used above.
De nition B1. An alphabet is a nite set whose elements called tokens or symbols.
such that is a partial mapping u : N 99K there exists n 2 N such that u(n) "; for any m; n 2 N such that m n; u(n) # implies u(m) # : Notation B1. The set of words over an alphabet is denoted by set n f g is denoted by +.
If u 2 + and n 2 N such that u(n) # then u[n] is the token from the condition u(n) #= u[n].
De nition B3. The length of a word u 2 is de ned as follows , and the satisfying lng u = minfn 2 N j u(n) "g: De nition B4. For any alphabet follows and u; v 2 , the word uv is de ned as (uv)(n) #= u[n] (uv)(n) #= v[n (uv)(n) "
whenever 0 lng u] whenever lng u whenever n n < lng u;
n < lng u + lng v; lng u + lng v:
uv 2 L ensures v = for any u 2 L and v 2 . is called pre x-free if Appendix C
Finite-State Acceptors and Regular Sets of Words
nite-state acceptor is a pentacle M = h ; Q; q0; F; i where
Q q0 2 Q
F Q : Q is a nite input alphabet; is a nite set of states; is some xed state called initial; is some xed subset of states that are called acceptable; ! Q is a mapping called a transition function.
For a nite-state acceptor M = h ; Q; q0; F; i , one can de ne the following extension : Q ! Q of the mapping (q; ) = q for any q 2 Q ; (q; ua) = ( (q; u); a) for any q 2 Q ; u 2 ; and a 2 : De nition C2. A nite state acceptor M = h ; Q; q0; F; i recognises a word u 2 if (q0; u) 2 F .
De nition C3. For any alphabet , a subset L is called regular if there is a nite-state acceptor that recognises exactly words from L.
More detailed information about regular set and nite-state acceptors one can
nd in, for example, [