Introduction

The experience of software development demonstrates that we have no the means for forecasting of progress of software projects (see [1]). So, in 2009, only 32% of the software development projects were successful. At the same time, the percentage of projects that ended with a significant budget overruns and the disruption of a schedule was 44%, and the projects that were interrupted in the form of loss control costs or timelines -24% of total software development projects. As we can see, the implementation of different methods in software management, the use of increasingly sophisticated technologies in software development, have not led to significant improvement in the quality of software development processes. The reason for the complexity of the development processes of large software systems is the need to provide correct handling for all possible flows of system events. One of the authors of this article in 1990 noted [12]: "it is almost impossible to foresee the sequence of the information processing procedures for complex computer systems, and therefore impossible to plan the flow of control". Rejection of an identification of all possible control flows can provide scalability and flexibility of software product in a process of system design. Breaking down of monolithic architectures leads us to the concept of data-driven systems [11], in particular -to event-driven architecture (EDA) [4].

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 flows of events, not only single events. The flow 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 flows. This work describes one mathematical model of a machine for the event flows 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 flows to highlight from them reasonable messages that are carried by these flows.

The aim of this paper is to study recognisers which are similar to automatabased recognisers. But we will suggest that a reconiser responses to finite sequences of events. This modification leads to study of partial actions of finite generated free monoids on a set as a recogniser's model.

The notion of a partial action was introduced for groups in [3] and for monoids in [10].

This paper is organised as follows.

In section 1, definitions 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 clarified 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.

Preliminaries

The notion of a partial action is adopted from [6] as follows.

Definition 1. Suppose X is an arbitrary set, M is a monoid with unit 1, and

X × M X : (x, m) → x • m is a partial map. The triple (X, M, •) is called a partial M -action on X iff the following conditions are held x • 1 = x for all x ∈ X;

(1)

if x • m 1 and (x • m 1 ) • m 2 are defined then x • (m 1 m 2 ) is defined and (x • m 1 ) • m 2 = x • (m 1 m 2 ); (2) if x • m 1 and x • (m 1 m 2 ) are defined then (x • m 1 ) • m 2 is defined and x • (m 1 m 2 ) = (x • m 1 ) • m 2 .(3)

We write

x • m = ∅ if x • m is defined, and x • m = ∅ if x • m is undefined.

The case of a finite generated free monoid M will be considered in the article only. Therefore we need to reformulate Definition 1. Definition 2. Let Q be a set of states, Σ be a finite alphabet, and suppose a partial Σ * -action on Q is defined 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 finite alphabet, and suppose a Σ * -action on X is defined. We can build a partial Σ * -action on Q with respect to the next formula

x • w = ∅, iff x • w / ∈ Q x • w, iff x • w ∈ Q when x ∈ Q and w ∈ Σ * .

It is easy to prove that conditions 1, 2, and 3 of Definition 1 are held. Hence, P = (Q, Σ, •) is a preautomaton. We can consider the preautomaton P as a restriction of a deterministic automaton [5

] A = (X, Σ, •) on the set Q.

Example 1 describes a general case. It will be demonstrated in the next section.

The following definition makes it possible to consider the class of all preautomata as a category.

Definition 3. Suppose P 1 = (Q 1 , Σ, •) and P 2 = (Q 2 , Σ, •) are preautomata, ψ : Q 1 −→ Q 2 is a map. The map ψ is called an equivariant map if for each x ∈ Q 1 and w ∈ Σ * such that x • w = ∅ the following condition is held: ψ(x) • w = ∅ and ψ(x • w) = ψ(x) • w.

The class of all Σ-preautomata with equivariant maps as morphisms is a category [9]. The proof is trivial. We denote this category by ΣPA, and by ΣPA(P 1 , P 2 ) we denote a set of morphisms from P 1 to P 2 when P 1 and P 2 are preautomata.

As usual [9], we introduce notions of a monomorphism, an epimorphism, and an isomorphism. Note, that an equivariant map is a monomorphism iff it is injective; in the category ΣPA there are bimorphisms which are not isomorphisms. Definition 4. We shall say that a preautomaton

(Q, Σ, •) is a finite preautoma- ton iff the set Q is finite.

The class of all finite Σ-preautomata with equivariant maps form a subcategory of the category ΣPA. We denote this subcategory by ΣFPA.

Universal Globalisation of Preautomata

The aim of this section is to prove that each preautomaton is a restriction of some automaton with same alphabet.

Definition 5. An automaton A = (X, Σ, •) is called a globalization of a preau- tomaton P = (Q, Σ, •) if there is a monomorphism ζ ∈ ΣPA(P, A).

At first, for each preautomaton P = (Q, Σ, •) we build a set Q gl and an injection ι :

Q −→ Q gl . Put Q = Q × Σ * .

For any q 1 , q 2 ∈ Q and w 1 , w 2 ∈ Σ * we shall write (q 1 , w 1 ) (q 2 , w 2 ) iff for some u ∈ Σ * is held the following condition:

w 1 = uw 2 and ∅ = q 1 • u = q 2 .

Denote by the least equivalence on Q such that the condition (q 1 , w 1 ) (q 2 , w 2 ) ⇒ (q 1 , w 1 ) (q 2 , w 2 ) is satisfied. Now, by definition put Q gl = Q/ . Denote by [q, w] the -class of the (q, w) ∈ Q.

Lemma 1. The triple P gl = (Q gl , Σ, •) is an automaton, where the action is defined by the formula [q, w] • a = [q, wa], when q ∈ Q, w ∈ Σ * , and a ∈ Σ.

Proof. One can establish this fact by direct checking of automaton's definition.

Then, express explicitly the condition (q 1 , w 1 ) (q 2 , w 2 ), where q 1 , q 2 ∈ Q, w 1 , w 2 ∈ Σ * . Definition 6. Suppose q ∈ Q and w ∈ Σ * , we shall say that they form a canonical piar iff for each u, v ∈ Σ * such that uv = w the following condition is held q • u = ∅ ⇒ u = .

We shall use the notation q × w if q and w form a canonical piar.

Lemma 2. Suppose q 1 , q 2 ∈ Q and w 1 , w 2 ∈ Σ * then (q 1 , w 1 ) (q 2 , w 2 ) iff there exist u 1 , u 2 , and s in Σ * such that

w 1 = u 1 s, w 2 = u 2 s, q 1 • u 1 = ∅, q 2 • u 2 = ∅, q 1 • u 1 = q 2 •

u 2 , and for q = q 1 • u 1 = q 2 • u 2 the condition q × s is held.

Proof. Evidently, the conclusion of the Lemma defines some equivalence, which we denote by ∼. The assertion (q 1 , w 1 ) (q 2 , w 2 ) ⇒ (q 1 , w 1 ) ∼ (q 2 , w 2 ) follows from the definition of ∼. Now, one can use the definition of and check that the condition (q 1 , w 1 ) ∼ (q 2 , w 2 ) ⇒ (q 1 , w 1 ) (q 2 , w 2 ) is satisfied. From this assertion and the definition of it follows that ∼ equals .

Corollary 1. In each -class there exists an unique canonical pair (q, w) ∈ Q.

By definition, put ι(q) = [q, ]. Then from the Corallary 1 it follows that the map ι : Q −→ Q gl is injective.

Theorem 1 (about Universal Globalisation). The map ι : Q −→ Q gl defines a globalisation ι : P −→ P gl . It satisfies the following condition: for any globalisation ζ : P −→ A there is a unique morphism ψ ∈ ΣPA(P gl , A) such that the diagram

P A P gl E ζ d d ι ψ is commutative.

Proof. First let us prove that ι is an equivariant map. In fact, suppose q • w = ∅ when q ∈ Q and w ∈ Σ * . Using Lemma 2, we get

ι(q • w) = [q • w, ] = [q, w] = [q, ] • w = ι(q) • w.

Hence, ι is an injective morphism, i.e. a monomorphism, and ι : P −→ P gl is a globalisation. Let [q, w] be an element of Q gl . Without loss of generality, we can assume that q × w. By definition, put ψ([q, w]) = ζ(q) • w.

By construction, if q and w as above and u ∈ Σ * then

ψ([q, w] • u) = ψ([q, wu]) = ψ([q • wu 1 , u 2 ]) = ζ(q • wu 1 ) • u 2 = ζ(q) • (wu 1 u 2 ) = ((ζ(q) • w) • u) = ψ([q, w]) • u

when u = u 1 u 2 and q × (wu 1 ). Thus, ψ ∈ ΣPA(P gl , 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?".

Problem 1. Let P = (Q, Σ, •) be a finte preatomaton. Determine the necessary and sufficient existance conditions of a finite globalisation of P.

Preacceptors and P-Recognisable Languages

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 [2,5]. In this section we shall connect each preautomaton with some language. The class of such languges will be called as the class of P-recognisable language.

We begin with some notation.

Evidently, A = (Σ * , Σ, •) is an automaton. Therefore, we can define a preautomaton P = (Q, Σ, •) as the restriction A on the set Q. Now, consider the preacceptor P([ ] ρ , T ), where

T = {[w 1 ] ρ , . . . , [w n ] ρ }. If w ∈ L then w ρ w i for some 1 ≤ i ≤ n by assumption, therefore ∅ = [ ] ρ • w = [w i ] ρ ∈ T and w is recognised by P([ ] ρ , T ). If w is recognised by P([ ] ρ , T ) then ∅ = [ ] ρ • w ∈ T , i.e. [w] ρ = [w i ] ρ for some 1 ≤ i ≤ n. Hence, w ∈ L.

This completes the proof.

Corollary 2. Let L 1 and L 2 be P-recognasible languages over the same alphabet then L 1 L 2 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.

Structure of P-Recognisable Languages

In this section we shall prove that the structure of P-recognisable languages is similar to the structure of recognisable languages [2].

Lemma 3. Let L be a P-languages then L = n i=1 L i , where

L i L j = ∅ for 1 ≤ i = j ≤ n;(5)

each L i is recognised by a preacceptor that its terminal subset

is an unit set.

Proof. Let P(q in , T ) be a preacceptor that recognises the language L. Suppose T = {q 1 , . . . , q n } then denote by L i the language recognised by P(q in , {q i }), where 1 ≤ i = j ≤ n. By construction, properties ( 5) and ( 6) are satisfied.

Let us remember [2,8] 1. let L be a subset of Σ * , and u be a word over

Σ * then u −1 L = {w ∈ Σ * | uw ∈ L}; 2. a language L ⊂ Σ * is unitary if for any u 1 , u 2 ∈ L it is held u −1 1 L = u −1 2 L; 3. a language L ⊂ Σ * is a prefix code iff for any u, v ∈ Σ * such that u, uv ∈ L it follows v = .

Note, if L is a prefix code then from ∈ L it follows L = { }.

Lemma 4. Let L be a language over an alphabet Σ then L is unitary iff L is recognised by a preacceptor such that its terminal subset is a unit set.

Proof. Let L be a unitary language then there exists an acceptor A(q in , {q accept }) which recognises the language L [2]. Denote by P(q in , {q accept }) the restriction of A(q in , {q accept }) on the set {q in , q accept } then the preacceptor P(q in , {q accept })

recognises the language L. Conversely, suppose L is recognised by some preacceptor P(q in , {q accept }), and P gl ([q in , ], {[q accept , ]}) is its universal globalisation. The acceptor P gl ([q in , ], {[q accept , ]}) recognises the language L. Using results of [2, Prop. 1.1], one can get that L is an unitary language.

Theorem 3 (about Structure of P-recognisable Languages). Let L be a P-recognisable language then L = n i=1

E i B * i

, where E i , B i are prefix codes for i = 1, . . . n, and

E i B * i E j B * j = ∅ for 1 ≤ i = j ≤ n.

Proof. Indeed, from Lemma 3 and Lemma 4 follows that L = n i=1 L i , where each L i is a unitary language, and

L i L j = ∅ if i = j. In [2, Prop. 3.4

] it has been proved that any unitary language has the representation EB * , when E, B are prefix codes. This completes the proof.

Problem 2. Describe the class of languages with structure as in Theorem 3 which are P-recognisable.

Preautomata Recognition Capability

In this section we compare the class of P-recognisable language with other classes of languages [7]: the class of recognisable languages, the class of context free languages, the classes of recursive and recursively enumerable languages. At first, 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 [7], E 1 = {a n b n | n > 0} ⊂ {a, b} * is a context free language. It is evident that E 1 is a prefix code. From Lemma 4 it follows that E 1 is P-recognisable.

We need to improve Theorem 2.

Definition 10. Let L be a language over an alphabet Σ, u, v be words over Σ. We shall use notation u ρ L v iff for any w ∈ Σ * it is satisfied uw ∈ L ⇔ vw ∈ 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 iff L is a finite union of ρ L -classes.

Proof. It follows from Theorem 2 and properties of right syntactic congruences [8, p. 27].

Example 3. Let L 1 be a language that is formed by all palindromes over the alphabet {a, b}. Note, that L 1 is a context free language [7]. But it is easy to see, that it is not held a m ρ L1 a n for 0 < m < n. Therefore, L 1 ⊃ n>0 [a n ] ρ L 1 and L 1 is not P-recognisable.

Example 4. Let E 2 be a language over the alphabet {a, b, c}. Suppose E 2 = {a n b n c n | n > 0}. It is evident, that E 2 is a prefix code, therefore it is Precognisable. But well known [7], E 2 is not a context free language.

Example 5. Let L 2 be a language over the alphabet {a}. Suppose L 2 = {a n 2 | n > 0}. Evidently, L 2 is a recursive language. It is easy to see, that L 2 is not P-recognisable.

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 finite alphabet is countable. The cardinality of the class of all prefix codes over some finite alphabet equals to the cardinality of continuum. This completes the proof.

Next proposition establishes that the class of P-recognisable languages is not closed under operations of a Kleene algebra. Proposition 4. Let Σ be a finite alphabet such that its power greater than 1, and ΣPR be the class of P-recognisable languages over Σ then

there exist L 1 , L 2 ∈ ΣPR such that L 1 ∪ L 2 / ∈ ΣPR(7)there exist L 1 , L 2 ∈ ΣPR such that L 1 • L 2 / ∈ ΣPR(8)

there exists L ∈ ΣPR such that L * / ∈ ΣPR

Proof. To prove (7) put

L 1 = {a n | n > 0}, L 2 = {a n b n | n > 0}, and L = L 1 ∪ L 2 . Evidently, L 1 , L 2 ∈ ΣPR and for any n > 0 it is satisfied [a n ] ρ L ⊂ L.

But it is not satisfied a m ρ L a n for m = n. From Proposition 2 it follows that L / ∈ ΣPR. To prove (8) put L = L 1 • L 2 . Suppose that 1 < m < n then it is not satisfied a m+1 b ρ L a n+1 b. Indeed,

Conclusion

We have introduced the new class of algebraic objects for systems behaviour modelling. Objects of this class are similar to deterministic finite 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 finite 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 finite 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.