We present basic structures, de nitions, normal forms, and a hierarchy of languages based on catenation, shu e and their iterations, de ned by algebraic closure or least x point solution of systems of equations. Formal language theory normally deals with subsets of , all words over a nite alphabet, using as basic binary operator catenation, denoted by in the sequel. This gives a basic monoid with and , the empty word. Other binary operators
Introduction
In this paper, we establish a hierarchy of languages expressing possibilities of
iterated sequential and parallel compositions of basic events, based on extending
the construction principles behind the well-known regular and context-free
languages with another operation known as the shu e [
In section 2 we introduce or recall the basic de nitions and structures needed for further investigation, such as monoids, semirings, bi-monoids and bi-semirings, furthermore systems of equations and their least x point solutions, and normal forms for them, as well as algebraic closure of nite sets under certain language operators. In section 3 we investigate the complete hierarchy of language classes de ned as algebraic closures of union, catenation, shu e and their iterations applied on the class of nite languages, as well as classes de ned by least x point solutions of systems of equations, and their relation to the Chomsky hierarchy. Section 4 o ers an outlook for further research in the area such as closure of language classes under certain operators, or decidability problems. have also been considered, as e.g. shu e, denoted by , which we de ne below under \basic structures".
In contrast to catenation is also commutative; like catenation, it can be used to de ne another monoid with the nite subsets of as domain. Another possibility is to combine both operators. Extending and the domain of to languages gives rise to a basic bi-monoid with f g as common neutral element, and the class of nite subsets of as domain. 2.1
In what follows we present, partially recalling, the de nitions of such structures more precisely. For w 2 let jjwjj denote the length of w. If A then jAj denotes the cardinality of A which also can be in nite. In particular, jj jj = 0. For A let jjAjj = maxfjjwjj j w 2 Ag the norm of A.
Based on the monoid M = ( ; ; ), where is a ( nite) alphabet, the binary operation catenation, and is the neutral element for the operator , S = (2 ; ;; f g; [; ) is an !-complete semiring since is associative, [ is commutative, associative and distributive with , and
A [ Bj = [(A j j
Bj ) ; ([ Bj ) j
A = [(Bj j
A)
for all A; Bj 2 2 where the union can also be in nite. Elements (words) w 2
or singletons fwg can be seen as basic elements (atoms). At a somehow higher
level also nite sets can serve as such. For that let 21 = f 2 2 j j j = 1g,the
class of singletons, and consider F IN = 2f = f 2 2 j j j < 1g, the class of
nite sets of words. This can be generated from the rst one by usual extension
to sets. For a general treatment of semirings and related structures see [
A similar construct holds for the shu e operator ! 2 , which can be de ned recursively as follows: For all a; b 2 and v; w 2 , w = w = fwg; aw bv = fag (w bv) [ fbg (aw v) and extended to sets from now on: : 2 2 ! 2 , A B = S w v. w2A;v2B
Here the basic monoid is M = (2f ; f g; ). Then S = (2 ; ;; f g; [; ) is an !-complete semiring as well since is associative, [ is commutative, associative and distributive with , and
A [ Bj = [(A j j
Bj ) ; ([ Bj ) j
A = [(Bj j
A) for all A; Bj 2 2 .
A bi-monoid is a structure D = (D; 1; ; ) where and binary operations on D, and 1 is the common neutral element.
A bi-semiring is a structure B = (B; 0; 1; ; ; ) where (B; 0; 1; ; ) and (B; 0; 1; ; ) are semirings, i.e. is a commutative and associative binary operation on B, and are associative binary operations on B, 0 is the neuare associative tral element of , and 1 the common neutral element of more, is distributive with and , i.e. x (y z) = (x x (y z) = (x y) (x z) for all x; y; z 2 B.
A bi-semiring B is !-complete if and y) x x
M yj = j M yj = j
M(x M(x j j yj ) ; (M yj )
j yj ) ; (M yj ) j x =
M(yj x =
M(yj j j x) ; x) for x; yj 2 B and arbitrary ( nite or in nite) 'sums' L with .
Let be an alphabet. Then D = (21 ; f g; ; ) is the basic bi-monoid for formal languages using both operations, and , similar to B for formal languages with only.
Then B = (2 ; ;; f g; [; ; ) is a bi-semiring since [ distributes with and . This bi-semiring is also !-complete. 2.2
It is well known that the class CF of context-free languages can be characterized by least x point solutions of systems of equations using structures based on catenation . Similar characterizations can be de ned for languages based on structures with or with both, and , respectively.
Let V be a nite set of variables, standing for subsets X , and C a nite set of constants 2 21 or 2 2f , thus elements of the basic structure. Thus V = fX1; ; Xmg and C = f 1; ; ng.
A monomial is a nite expression m(X) on V [ C using binary operations , or , or both and , where X denotes the tuple of (ordered) variables, e.g. (X1 1) (X2 X3).
A polynomial p(X) is a nite union of monomials.
A system of equations is a system Xi = pi(X) (1 form X = p(X). i m), or in compact
A system of equations is called algebraic if the monomials occurring in the system of equations are arbitrary, linear if all monomials have one of the forms (A X) B, A (X B), or A with X 2 V, A; B expressions of constants only, and 2 f ; g, rational if all monomials have the form X A or A.
If the underlying semiring or bi-semiring is !-complete such a system has a solution as least x point. This can be constructed by iteration, starting with X(0) = ;, and iterating X(j+1) = p(X(j)).
Clearly, X(j) X(j+1) for 0 j, where is meant componentwise for all 0 i m, thus a monotone sequence. This is shown by induction, the basis ; X(1) being trivial, and with induction hypothesis X(j) X(j+1) and X(j+1) = p(X(j)) p(X(j+1)) = X(j+2).
Since X(j) , a total upper bound, there exists limj!1X(j) = Y which is the least x point solution, i.e. Y = p(Y ).
Each component of the least x point solution de nes a formal language of the system's kind (algebraic, linear, rational), e.g the component belonging to the rst variable X1.
Corresponding to the underlying semirings, di erent language classes can be de ned. These are
ALG( ) = CF , LIN ( ) = LIN , RAT ( ) = RE G, ALG( ) = LIN ( ) = RAT ( ) = SHU F ,
ALG( ; ), LIN ( ; ), RAT ( ; ).
Example 1. An example of a rational system of equations is given by X = X [ X [ with singletons f ; ; g = C from disjoint alphabets. The least x point solution is a set of languages de ned by the following terms in pre x notation, where h : f ; g ! C is a homomorphism de ned by h( ) = , h( ) = , and R denotes the reverse.
[ u2f ; g u h(u)R = ( )
In case of one single commutative operator the classes of algebraic, linear,
and rational languages coincide [
Whereas in a system of equations one gets least x points solutions for all variables, grammars just produce the solution of a distinguished variable, the initial variable. The equations are written as basic derivation steps, e.g. for
X = (Y ) [ (Y Z) X [ gives the productions X ! (Y ), X ! (Y ), X ! . 2.3
Another characterization of languages is achieved by application of some language operators on a basic class of languages. The operators can be applied either in arbitrary, prescribed, or somehow mixed order. In this way one gets algebraic closures under the language operators, i.e the least class of languages closed under such operators.
Here we consider the operators [, , and , as well as their iterations and , applied on members of the basic class F IN of nite languages. Using the operator [ one could also take 1 , the class of singletons as basic class. But for convenience we start with F IN .
([; ; )(F IN ) means that the operators [, , and are applied in arbitrary order and arbitrary often on nite sets, whereas ([; )( )( )(F IN ) means that at rst is applied arbitrary often, then arbitrary often, and nally [ and arbitrary often and in arbitrary order. Note the non-application of corresponding operators is always understood, i.e. each algebraic closure also contains F IN .
Note that for any set A the following facts hold: (A ) = (A ) = (A ) = A , A A , and (A ) = A .
Important classes are ([; ; )(F IN ) = SHU F , ([; ; ; )(F IN ) = E R, ([; ; ; )(F IN ) = E S, and ([; ; ; ; )(F IN ) = SE where E S stands for extended shu e expression, analogous to E R for extended regular expression. 2.4
For any system of equations an equivalent one with possibly more variables can be constructed such that the solution of the new system coincides with the solution of the old system on the variables of the old system, and the monomials of the new system are of a simple form. This will be shown for systems with operators ; . Since [ is idempotent, i.e. e [ e = e for any expression, wlog e occurs only once as a monomial in a polynomial.
In case of an algebraic system consider a monomial. If it is of the form Y Z, Y , or , where Y; Z 2 V, 2 f ; g, 2 C, leave it unchanged. If the form is Y or Y , add a new variable Z, replace the monomial by Y Z or Z Y , respectively, and add a new equation Z = to the system.
If it has the form e1 e2 where e1; e2 are expressions such that it is not of the form above, add new variables Z1; Z2, replace e1 e2 by Z1 Z2 and add new equations Z1 = e1, Z2 = e2 to the system. Repeat the procedure until all (also new) monomials are of the form above.
Note that also expressions A consisting only of constants are reduced. Thus only forms Y Z, Y , or are achieved.
In case of a linear system of equations leave unchanged monomials of the form Y , Y , Y , and . Otherwise proceed as for algebraic systems.
Thus there are only monomials of the form Y , Y , Y , or .
In case of a rational system of equations leave unchanged monomials of the form Y , Y , or . Otherwise proceed as for algebraic systems. Only expressions of constants are processed. Thus one gets the normal form Y , Y , or .
Another reduction is the eliminations of polynomials of the form Y .
If X occurs in its own polynomial then it can be removed. To show that let X = pX (X) = qX (X) [ X be the component for X in the system of equations X = p(X). Consider also the system X0 = p0(X0) which is identical to the rst one except for pX (X) replaced by qX (X0). Then X(j) = X0(j) for all j 0 in the x point approximation. This is shown by induction.
X(0) = ; = X0(0) With the induction hypothesis X(j) = X0(j) follows X(j+1) = p(X(j)) = p(X0(j)) where pX (X(j)) = qX (X(j)) [ X(j) = qX (X0(j)) [ X0(j) = qX (X0(j)) since X0(j) p(X0(j)) = X0(j+1), and therefore p(X0(j)) = p0(X0(j)) = X0(j+1), yielding X(j+1) = X0(j+1).
Hence both systems have the same least x point solution.
Therefore: Lemma 1. To any system of equations there exists an equivalent one with respect to least xpoint, with following normal forms of the monomials: algebraic: Y Z, Y linear: Y , Y rational: Y , Y where Y; Z 2 V, 2 21 . , ,
Y ,
Y , 3
Hierarchies In this section we present two language hierarchies, a lower and an upper one. 3.1
The rst hierarchy we will establish is one of families of languages (in the sense
of [
Two classes coincide since RE G is closed under [
([; ; )(F IN ), i.e. RE G is closed unProof. Let R1; R2 2 RE G. Then R1; R2 are accepted by deterministic nite automata A1 = (Q1; 1; 1; q01; Qf1) and A2 = (Q2; 2; 2; q02; Qf2). Construct a NFA A = (Q; ; ; q0; Qf ) by Q = Q1 Q2, = 1 [ 2, q0 = (q01; q02), Qf = Qf1 Qf2, ((q; s); x; (q0; s)) 2 if 1(q; x) = q0 or ((q; s); y; (q; s0)) 2 if 2(s; y) = s0. Then A accepts the language R1 R2.
From this follows Theorem 1. ([; ; ; )(F IN ) = ([; ; )(F IN ) = RE G.
All of the inclusions in the diagram of Figure 1 are proper; to show this, it is su cient to prove the following lemmata (by counterexamples): { ( ; )(F IN ) \ ( ; )(F IN ) 6 E S (Lemma 2) { ([; )(F IN ) \ ([; )(F IN ) 6 ( ; ; ; )(F IN ) (Lemma 4) { ( ; )(F IN ) 6 E R (Lemma 8) { ( ; )(F IN ) 6 ([; ; )(F IN ) (Lemma 6) { ( ; )(F IN ) 6 ( ; ; )(F IN ) (Lemma 5) { ( )(F IN ) 6 ([; ; ; )(F IN ) (Lemma 10) { ( )(F IN ) 6 ([; ; ; )(F IN ) (Lemma 9) Lemma 2. fag fbg = fag fbg 62 E S.
OCC AKA Q C A
Q Q B B B B
B ) ([
([ CQA C QA C C C
C ) (
Q A Q A
Q A A ) ( ) ([ Proof. 8L 2 ES 9m 2 N : ((k > 1; ` > 1; k + ` > m; akb` 2 L) ) 9ubav 2 L). But this is not true for fag
fbg .
Proof by structural induction: A language in ES A [ B, A B, A or A in nitely many words of the shape ambn but A with A; B 2 L . For any nite language L let m = kLk. If A does not contain or A does, then this is due to A containing akb` words up to a certain length or ak and b ` words. In any case, wrongly ordered words result. If A and B have the property, then A [ B obviously has it and for A
B, a contradiction is also reached if one of them, wlog A, contains a word uav and B contains a word u2bv2.
Lemma 3. Let vector
(w) 2 N , extended to languages.
: L ! N
be the Parikh mapping that takes a word w to the with components identical to the multiplicities of symbols from For any language L 2 ( ; ; ; )(F IN ), we have that (9w 2 L 9 2 N 8k 2 N : (w) + k 2 (L)) Proof. By structural induction over an ( ; ; ; )-term for L. If A; B have the property with vector A(w) depending on w, resp. B(w), then in A B, the same vectors can be used ( A(u) is good for any word uv 2 A B and by assumption some 0 A(u) is good for any other word u2v 2 A B and vice versa). For A B, the same holds. For A and A , any new word can be su xed with formerly possible iterations.
Lemma 4. fag [ fbg
= fag [ fbg 62 ( ; ; ; )(F IN ).
Proof. Applying Lemma 3 to w = fag and = f(b; 1)g.
Lemma 5. ( ; )(F IN ) 6 ( ; ; )(F IN ).
Proof. Consider L = fabg fcd; ef g 2 ( ; )(F IN ). Assume L 2 ( ; ; )(F IN ).
Let L = A with A 6= ;, A 6= f g. Now cd 2 L. Either cd 2 Ai for some i yielding cdcd 2 L, a contradiction, or c 2 Ai, d 2 Aj for some i; j yielding dc 2 L, also a contradiction. L = A gives the same contradiction.
Let L = A B with A 6= f g, B 6= f g.
If there exists xcy 2 A then there exists neither ucv 2 B nor u0ev0 2 B nor u00f v00 2 B since otherwise xcyuev 2 L or xcvu0ev0 2 L or xcyu00f v00 2 L, all contradictions. Therefore either xcydz 2 A or udv 2 B possible. But then there would be no xeyf z 2 L, a contradiction.
Lemma 6. ( ; )(F IN ) 6 ([; ; )(F IN ).
Proof. Any language of L2 = ([; ; )(F IN ) is a nite union Si Li of languages which are either nite or Li = Ai or Ai for languages Ai. If w 2 A, ww 2 A and ww 2 A . Suppose L1 = fag fbg 2 L2. Then L1 is in nite and a 2 L1, and a word an with n > the longest word in any of the nite languages, must be in one of the languages Ai so we conclude aa 2 L1, which is wrong. Lemma 7. Every language L 2 E R can be written as a union as follows, with I a nite set and all K(i) 2 N, for a nite number of sets Aik 2 E R which are all either nite or Cik or Cik for some Cik 2 E R.
K(i) L = [ K Aik
i2I k=0 This follows from the distributivity of over [: A (B[C) = A B[A C. Such a representation is of course not unique. Note that below any iterated catenation or iterated shu e the term Cik might be arbitrarily complex.
Proof. Proceed by structural induction. If L is already nite, or the shu e or iteration closure of some language in E R, then I is a singleton set and the union contains one trivial product. If L = M [N , with IM and IN wlog disjoint possible K(i) index sets of the respective unions, then L = S J Aik. If L = M N , i2IM [IN k=0 then L =
K(i)
S J Aik (i;j)2IM IN k=0
K(j) J Ajk, with jIM j k=0 jIN j such products.
Lemma 8. ( ; )(F IN ) 6 E R.
Proof. Consider L = fabcg fbcg 62 E R. The following property holds: (1) 8w 2 L : jjwjja + 1 = jjwjjb = jjwjjc.
Using a representation from lemma 7, L can be written as a nite union indexed by I such that for each i 2 I, there is a maximum number m(i) of letters contributed by the nite languages: m(i) =
X k2f0; ;K(i)g;jAikj<1 jjAikjj
Obviously, if n > m, not all a can come from nite Ak. Hence there must exist some in nite set Aa to the left of Akb such that a` 2 Aa for some ` > 0. A contradiction.
L0 = fabg fcg 62 E R is a simpler language with a similar property. It can be shown in a similar way, using 8w 2 L0 j jjwjja = jjwjjb and words ancbn 2 L0. Lemma 9. ( )(F IN ) 6 ( ; [; ; )(F IN ) = RE G.
Proof. fabg is not regular because fabg \ (fag fbg ) is not.
Lemma 10. ( )(F IN ) 6 ( ; [; ; )(F IN ).
Proof. Consider L = fabg 2 ( )(F IN ). L 62 ([; ; ; )(F IN ).
Assume the contrary. Since jjLjj = 1 the operation , the only one producing in nite sets, has to be used at least once, A = B . Let it be the last one in the structural tree representing L. Clearly, B 6= ;, B 6= f g, and 9w 2 B : w = uav. But then uuaavv 2 fwg fwg A. Neither nor will erase such a word u0aav0. A contradiction. In this part we investigate higher important language classes, in particular those de ned by systems of equations, and their relations to well known classes. This is illustrated in Figure 2.
A A
CF = ALG( )
6 LIN = LIN ( )
KA A A A
CS
6 : ALG( ; )
6 : LIN ( ; ) RAT ( ; ) 6 6
SE =
YHHHH Proof. Construction of a system of equations by structural induction. It su ces to start with singletons.
2 1 . X1 =
.
A [ B with Y; Z variables for A; B. Add X1 = Y1; X1 = Z1.
B. Add X1 = Z1 and Z = Y1 if Z = is an equation for A. Similar for A
B with replaced by equation for A. Similar for A
The least x point solution X ful lls X fw j jjwjja = jjwjjb = jjwjjc = jjwjjdg whose words of length 4k; k 2 N can be easily calculated: some of them are dkbk(ca)k, (dcba)k. Some words not in any solution X are any words ending in d, or words with aa or cc in xes.
We prove that no in nite subset of X containing in nitely many dkbk(ca)k words is in SE.
1) X = A or 2) X = A are out, because for 2) no word with an arbitrary number of consecutive c or a is in X; and for 1) eventually some di would have to be in A, which can then be added to the end, yielding a word not in X. So any language whose minimal SE term has depth 1, does not provide the solution X. All other possibilities reduce the question of nding such a SE language to the question of nding one with a minimal term depth reduced by 1:
X = A [ B still means that one of A and B still contains in nitely many such words and none contains a word not in X, begging the question.
X = A B, with non-trivial A and B, means all dkbk(ca)k words must come from A and B wholesale because otherwise the balance between the numbers of occurrences of a; b; c and d can necessarily be upset by pumping.
X = A B, with non-trivial A and B, means that if A contains any word ucv, B contains neither u2av2 nor u3cv3. Neither can it contain any word with b nor d since no word in X ends with either of these.
Lemma 13. (also [
To prove the following lemma iteration lemmata for the classes RAT ( ; ),
LIN ( ; ) and ALG( ; ), similar to such for REG, LIN and CF are applied.
For lack of space they and the following counterxexamples will be presented in
another article. For general iteration lemmata see [
Lemma 14. L1 = fanbn j n
L2 = fambmcndn j m; n L3 = fanbncn j n
Putting together the last lemmata as well as such known for the Chomsky hierarchy and from Figure 1, we get the complete diagram shown in Figure 2.
Outlook In another paper we have investigated structural, closure and decidability properties of language classes presented in this paper, as well as iteration lemmata for them, and their relation to semilinear sets.
It would also be interesting to know for each of the proper inclusions in the
diagrams whether it is decidable if a language of the higher family, given by a
term of the corresponding type, is also a member of the lower one ([