The new class of recognisers is introduced and studied in the paper. The models are based on the notion of partial action of a free nite generated monoid. Authors called such models by preautomata. Some properties of preautomata were established and proved in the paper. These properties allow to consider the pre-automata as mathematical models of recognizers of event ows in processes of the interaction of software systems.
The experience of software development demonstrates that we have no the means
for forecasting of progress of software projects (see [
Modern applications development tools for EDA are based on using standard methodologies such as "Event Dispatcher - Event Listener". This methodology assumes that, each generated event can be listened by a number of handlers However, in case of an interaction of many systems the dispatchers have to listen ows of events, not only single events. The ow of events forms sensible messages, and in this case, there are no standardized software components even at the level of mathematical models, namely, events listeners are oriented on a recognition of event ows. This work describes one mathematical model of a machine for the event ows recognition. In this mathematical model each event is modelled by the symbol of some alphabet, and messages are modelled by certain words in this alphabet. The pre-automata notion has been introduced. This notion provides a possibility to analyze the event ows to highlight from them reasonable messages that are carried by these ows.
The aim of this paper is to study recognisers which are similar to automatabased recognisers. But we will suggest that a reconiser responses to nite sequences of events. This modi cation leads to study of partial actions of nite generated free monoids on a set as a recogniser's model.
The notion of a partial action was introduced for groups in [
This paper is organised as follows.
In section 1, de nitions of the terms are given and basic notation is introduced. Then the key example is considered therein.
In section 2, the relationship between preautomata and automata is studied. The Theorem about Universal Globalisation contains the main result of the section. It substantiates using of pre-automata as models for behaviour of systems in the case of restricted observability of system's states.
In section 3, a class of a languages, which are recognised by a preautomaton, is introduced. We call this class as a class of P-recognisable languages. Then we specify such languages in the terms of right congruences on a free monoid generated by a preautomaton's alphabet.
In section 4, the Eilenberg's Structural Theorem [2, see p. 83] is proved for P-recognisable languages.
In section 5, a capability of preautomata as recognizers is clari ed by comparison of the class of P-recognisable languages with other known classes of languages.
In conclusion, the set of problems, which solution gives an answer to question of adequacy using preautomata for modelling behaviour of systems, is formulated. 1
The notion of a partial action is adopted from [
De nition 1. Suppose X is an arbitrary set, M is a monoid with unit 1, and X M 99K X : (x; m) 7! x m is a partial map. The triple (X; M; ) is called a partial M -action on X i the following conditions are held
x 1 = x for all x 2 X; if x m1 and (x m1) m2 are de ned then x (m1m2) is de ned and (x m1) m2 = x (m1m2); (1) if x m1 and x (m1m2) are de ned then (x m1) m2 is de ned and x (m1m2) = (x m1) m2: (3) We write x m 6= ; if x m is de ned, and x m = ; if x m is unde ned.
The case of a nite generated free monoid M will be considered in the article only. Therefore we need to reformulate De nition 1.
De nition 2. Let Q be a set of states, be a nite alphabet, and suppose a partial -action on Q is de ned then the triple (Q; ; ) is called a preautomaton.
As usial for free monoid
we denote its unit by .
Example 1. Some class of examples of preautomata can be built in the following way.
Let X be a set, Q be a subset of X, be a nite alphabet, and suppose a -action on X is de ned. We can build a partial -action on Q with respect to the next formula x w = (;; i x w 2= Q
x w; i x w 2 Q when x 2 Q and w 2 .
It is easy to prove that conditions 1, 2, and 3 of De nition 1 are held. Hence, P = (Q; ; ) is a preautomaton.
We can consider the preautomaton P as a restriction of a deterministic
automaton [
Example 1 describes a general case. It will be demonstrated in the next section.
The following de nition makes it possible to consider the class of all preautomata as a category.
De nition 3. Suppose P1 = (Q1; ; ) and P2 = (Q2; ; ) are preautomata, : Q1 ! Q2 is a map. The map is called an equivariant map if for each x 2 Q1 and w 2 such that x w 6= ; the following condition is held: (x) w 6= ; and (x w) = (x) w:
The class of all -preautomata with equivariant maps as morphisms is a
category [
PA(P1; P2) we denote a set of morphisms from P1 to P2 when P1 and P2 are preautomata.
As usual [
The class of all nite egory of the category
-preautomata with equivariant maps form a subcat
PA. We denote this subcategory by FPA.
The aim of this section is to prove that each preautomaton is a restriction of some automaton with same alphabet.
De nition 5. An automaton A = (X; ; ) is called a globalization of a preautomaton P = (Q; ; ) if there is a monomorphism 2 PA(P; A).
At rst, for each preautomaton P = (Q; ; ) we build a set Qgl and an injection : Q ! Qgl.
Put Q = Q .
For any q1; q2 2 Q and w1; w2 2 we shall write (q1; w1) ` (q2; w2) i for some u 2 is held the following condition: w1 = uw2 and ; 6= q1 u = q2. Denote by ' the least equivalence on Q such that the condition (q1; w1) ` (q2; w2) ) (q1; w1) ' (q2; w2) is satis ed.
Now, by de nition put Qgl = Q= ' .
Denote by [q; w] the '-class of the (q; w) 2 Q.
Lemma 1. The triple Pgl = (Qgl; ; ) is an automaton, where the action is de ned by the formula [q; w] a = [q; wa], when q 2 Q, w 2 , and a 2 .
Then, express explicitly the condition (q1; w1) ' (q2; w2), where q1; q2 2 Q, w1; w2 2 .
De nition 6. Suppose q 2 Q and w 2 , we shall say that they form a canonical piar i for each u; v 2 such that uv = w the following condition is held q u 6= ; ) u = .
We shall use the notation q
w if q and w form a canonical piar.
Lemma 2. Suppose q1; q2 2 Q and w1; w2 2 then (q1; w1) ' (q2; w2) i there exist u1, u2, and s in such that w1 = u1s, w2 = u2s, q1 u1 6= ;, q2 u2 6= ;, q1 u1 = q2 u2, and for q0 = q1 u1 = q2 u2 the condition q0 s is held.
Proof. Evidently, the conclusion of the Lemma de nes some equivalence, which we denote by . The assertion (q1; w1) ` (q2; w2) ) (q1; w1) (q2; w2) follows from the de nition of . Now, one can use the de nition of ' and check that the condition (q1; w1) (q2; w2) ) (q1; w1) ' (q2; w2) is satis ed. From this assertion and the de nition of ' it follows that equals '. tu Corollary 1. In each '-class there exists an unique canonical pair (q; w) 2 Q.
By de nition, put (q) = [q; ]. Then from the Corallary 1 it follows that the map : Q ! Qgl is injective. Theorem 1 (about Universal Globalisation). The map : Q ! Qgl denes a globalisation : P for any globalisation : P such that the diagram ! Pgl. It satis es the following condition: ! A there is a unique morphism 2
PA(Pgl; A) P
Pgl globalisation. when q 2 Q and w 2
. Using Lemma 2, we get Proof. First let us prove that is an equivariant map. In fact, suppose q w 6= ; (q w) = [q w; ] = [q; w] = [q; ] w = (q) w: is an injective morphism, i.e. a monomorphism, and : P ! Pgl is a Let [q; w] be an element of Qgl. Without loss of generality, we can assume that q w. By de nition, put
([q; w]) = (q) w: By construction, if q and w as above and u 2 then ([q; w] u) = ([q; wu]) =
([q wu1; u2]) = (q wu1) u2 = (q) (wu1u2) = (( (q) w) u) = ([q; w]) u when u = u1u2 and q
(wu1).
Thus, 2
PA(Pgl; A).
Finally, let q be an element of Q then we have ( )(q) = ( (q)) = ([q; ]) = (q) = (q) Evidently,
is unique. This completes the proof.
Theorem 1 gives us the positive answer to the question "Is any preautomaton a restriction of some automaton?". and su cient existance conditions of a Problem 1. Let P = (Q; ; ) be a nte preatomaton. Determine the necessary nite globalisation of P.
tu 3
Parsing of texts is the important class of tasks in computer science. Methods
for solving these tasks aregrounded on the automata theory. The main concept
in the context is the concept of a recognisable set [
We begin with some notation. De nition 7. Let P = (Q; ; ) be a nite preautomaton. Suppose some element qin 2 Q (the initial state) and some subset T Q (the terminal subset) is marked out then a triple (P; qin; T ) is called a preacceptor.
We shall denote the preacceptor (P; qin; T ) by P(qin; T ).
By de nition, put
L[P(qin; T )] = fw 2 j ; 6= qin w 2 T g; (4) where P(qin; T ) is a preacceptor.
De nition 8. Let P(qin; T ) be a preacceptor then we shall say that the language L[P(qin; T )] is recognised by P(qin; T ).
Now we can de ne the class of P-recognisable languages.
De nition 9. Let L be a language over an alphabet . We shall say that the language L is P-recognisable if there exists some preacceptor such that L is recognised by it.
Our immediate aim is to nd necessary and su cient conditions for a language be a P-recognisable language. To achieve this aim, we need several de nitions.
Recall [
Theorem 2. Let L be a language over an alphabet . It is P-recognisable i there exists a right congruence on the monoid such that L is equal to some nite union of its classes.
Proof. Suppose, that P(qin; T ) is a preacceptor that it recognises the language L. Denote by P = (Q; ; ) the preautomaton such that P(qin; T ) = (P; qin; T ). Let : P ! Pgl be the universal globalisation of P, Qgl be a set such that Pgl = (Qgl; ; ). By de nition, put Tgl = f[q; ] 2 Qgl j q 2 T g and denote, by Pgl([qin; ]; Tgl) the acceptor (Pgl; [qin; ]; Tgl).
Put u v i [qin; u] = [qin; v].
The binary relation on is a right congruence. It follows from Lemma 1. From Corollary 1 it follows that the acceptor Pgl([qin; ]; Tgl) recognises the same language as the preacceptor P(qin; T ). Moreover, [w] = fw 2 j w = us; ; 6= qin u s; (qin; w) 2 [qin u; s]g: Hence, ; 6= qin w 2 T i (qin; w) 2 [q; ] for some q 2 T .
Summing the reasoning, we get L = S fw 2 j (qin; w) 2 [q; ]g, i.e. L is q2T w1; : : : ; wn 2 .
By de nition, put Q = equal to a nite union of -classes.
n Conversely, suppose L = S [wi] , where i=1 = , [u] w = [uw] .
is some right congruence on Evidently, A = ( ; ; ) is an automaton. Therefore, we can de ne a preautomaton P = (Q; ; ) as the restriction A on the set Q.
Now, consider the preacceptor P([ ] ; T ), where T = f[w1] ; : : : ; [wn] g. If w 2 L then w wi for some 1 i n by assumption, therefore ; 6= [ ] w = [wi] 2 T and w is recognised by P([ ] ; T ).
If w is recognised by P([ ] ; T ) then ; 6= [ ] w 2 T , i.e. [w] = [wi] for some 1 i n. Hence, w 2 L.
This completes the proof. tu Corollary 2. Let L1 and L2 be P-recognasible languages over the same alphabet then L1 T L2 is a P-recognisable language too.
Corollary 3. The class of P-recognisable languges over a single-letter alphabet equals to the class of recognisable languages over the same alphabet. 4
In this section we shall prove that the structure of P-recognisable languages is
similar to the structure of recognisable languages [
n;
each Li is recognised by a preacceptor that its terminal subset
is an unit set.
(5)
(6)
Proof. Let P(qin; T ) be a preacceptor that recognises the language L. Suppose
T = fq1; : : : ; qng then denote by Li the language recognised by P(qin; fqig),
where 1 i 6= j n. By construction, properties (5) and (6) are satis ed. tu
Let us remember [
uw 2 Lg; 2. a language L 3. a language L it follows v = .
, and u be a word over then u 1L = fw 2 j is unitary if for any u1; u2 2 L it is held u 1 1 L = u2 1L; is a pre x code i for any u; v 2 such that u; uv 2 L Note, if L is a pre x code then from
2 L it follows L = f g.
Lemma 4. Let L be a language over an alphabet then L is unitary i
recognised by a preacceptor such that its terminal subset is a unit set.
L is
Proof. Let L be a unitary language then there exists an acceptor A(qin; fqacceptg)
which recognises the language L [
Conversely, suppose L is recognised by some preacceptor P(qin; fqacceptg), and Pgl([qin; ]; f[qaccept; ]g) is its universal globalisation.
The acceptor Pgl([qin; ]; f[qaccept; ]g) recognises the language L. Using results of [2, Prop. 1.1], one can get that L is an unitary language. Problem 2. Describe the class of languages with structure as in Theorem 3 which are P-recognisable. 5
In this section we compare the class of P-recognisable language with other classes
of languages [
At rst, compare the class of P-recognisable language with the class of recognisable languages.
Proposition 1. Any recognisable language is P-recognisable.
Proof. It is trivial.
Others cases of a comparison are more complicated.
Example 2. As known [
We need to improve Theorem 2.
De nition 10. Let L be a language over an alphabet , u; v be words over . We shall use notation u L v i for any w 2 it is satis ed uw 2 L , vw 2 L. In this case, we shall call L a right syntactic congruence induced by L. It is evident that L is a right congruence on .
Proposition 2. Let L be a language over an alphabet . It is P-recognisable i
L is a nite union of L-classes.
tu
tu
Proof. It follows from Theorem 2 and properties of right syntactic congruences
[8, p. 27].
tu
Example 3. Let L1 be a language that is formed by all palindromes over the
alphabet fa; bg. Note, that L1 is a context free language [
Example 4. Let E2 be a language over the alphabet fa; b; cg. Suppose E2 =
fanbncn j n > 0g. It is evident, that E2 is a pre x code, therefore it is
Precognisable. But well known [
In contrast to recognisable languages, there exist a P-recognisable language which is not a recursively enumerable language. Unfortunally, our proof is not constructive.
Proposition 3. There exists a P-recognisable language which is not recursively enumerable.
Proof. The class of a recursively enumerable languages over some nite alphabet is countable. The cardinality of the class of all pre x codes over some nite alphabet equals to the cardinality of continuum. This completes the proof. tu
Next proposition establishes that the class of P-recognisable languages is not closed under operations of a Kleene algebra.
Proposition 4. Let be a nite alphabet such that its power greater than 1, and PR be the class of P-recognisable languages over then there exist L1; L2 2 there exist L1; L2 2
PR such that L1 [ L2 2= PR such that L1 L2 2=
PR PR there exists L 2
PR such that L = 2
PR (7) (8) (9) Proof. To prove (7) put L1 = fan j n > 0g, L2 = fanbn j n > 0g, and L = L1 [ L2. Evidently, L1; L2 2 PR and for any n > 0 it is satis ed [an] L L. But it is not satis ed am L an for m 6= n. From Proposition 2 it follows that L 2= PR.
To prove (8) put L = L1 L2. Suppose that 1 < m < n then it is not satis ed am+1b L an+1b.
Indeed, (am+1b) bm = am+1bm+1 2= L (an+1b) bm = an+1bm+1 = an mam+1bm+1 2 L As above, it is easy to see L 2= PR.
To prove (9) put L = fanbn j n > 0g [ fag. It is easy to see [ab] L = fanbn j n > 0g and [a] L = fag, hence L 2 PR. As above, it is not satis ed am L an for m 6= n. But an 2 L , therefore L 2= PR. tu
We have introduced the new class of algebraic objects for systems behaviour modelling. Objects of this class are similar to deterministic nite automata. But presented models permit to describe hidden from observer behaviour of a system.
A model of this class can be obtained by a restriction some automaton on a nite subset of its states. An abstract concept to describe such models have been introduced. We call corresponding abstract objects by preautomata.
Theorem about universal globalisation for preautomata has been proved in the article. The theorem states that any preautomaton can be represented by a restriction of some automaton on a nite subset of its states.
Then we studied recognisers which based on preautomata and the corresponding class of languages.
Languages of this class have been called P-recognisable languages. The theorem about structure of P-recognisable languages have been proved.
Finally, the place of P-recognisable languages was determined among other classes of languages.