We present nite automata for shu e languages, iteration lemmata for languages with catenation and shu e, closure properties of such language classes, as well as decidability results. De nition 1. Shu e Finite Automaton A non-deterministic shu e nite automaton N SF A is de ned similar to nite automata as A = (Q; ; ; Q0; Qf ) with Q a nite set of states, Q0 Q
In [
In section 2 we introduce a nite automaton with shu e as bascic operation
as an analogon to well known nite automata with catenation as basic operation
and show the equivalence to shu e-rational sets. Section 3 deals with structural
properties as iteration lemmata and semilinearity. Finally, in section 4 closure
properties under language operations are investigated, as union, intersection,
catenation, shu e, their iterations, intersection with regular and shu e-rational
sets, complement, set di erence, reversal, pre x, and quotient. In section 5 some
decidability results are presented. Some complexity results are given in [
denotes the shu e of words, w v = fu1v1 unvnjw = J ui; v = J vig, also extended to languages by L1 L2 = Sv2L1;w2L2 v w.
e Finite Automata In case of shu e as basic operator one can also de ne a nite automaton, the shu e nite automaton. Remember that SHU F = RAT ( ) = ([; ; )(F IN ) is the closure of the nite languages under union, shu e and iterated shu e. the initial states, Qf Q the nal states, a nite set of symbols, and Q Q a nite set of transitions.
A con guration of A is a pair (q; w) 2 Q . A direct step of A is de ned by (q; w) ` (q0; w0) i (q; ; q0) 2 ^ 9w0 2 : w 2 f g fw0g. Let ` denote the re exive and transitive closure of `. The language accepted by A is L(A) = fw 2 j 9q0 2 Q09qf 2 Qf : (q0; w) ` (qf ; )g.
Let N SF A denote the class of all languages accepted by N SF A. Lemma 1. RAT ( )
N SF A.
Proof. L = fwg with w 2 . Then L is accepted by the shu e nite automaton A = (fq0; qf g; ; f(q0; w; qf )g; fq0g; fqf g).
L = L1 [L2. Let Ai = (Qi; i; i; Q0i; Qfi) accept Li. Wlog assume Q1 \Q2 = ;. Then L is accepted by A = (Q; ; ; Q0; Qf ) where Q = Q1 [ Q2, Q0 = fq0g, Qf = Qf1 [ Qf2, = 1 [ 2, and
= f(q0; ; q0i) j q0i 2 Q0i; = i 2 f1; 2gg [ 1 [ 2.
L = L1 L2. Let Ai = (Qi; i; i; Q0i; Qfi) accept Li. Wlog assume Q1 \Q2 = ;. Then L is accepted by A = (Q; ; ; Q0; Qf ) where
Q = Q1 [ Q2, Q0 = Q01, Qf = Qf2, = 1 [ 2, and
= f(qf1; ; q02) j qf1 2 Qf1; q02 2 Q02g [ 1 [ 2 L = L1 . Let A0 = (Q; ; 0; Q0; Qf ) accept M . Then L is accepted by the NSFA A = (Q; ; ; Q0; Q0f ) where Q0f = Q0 [ Qf , and
= f(qf ; ; q0) j q0 2 Q0; qf 2 Qf g [ 0
RAT ( ).
Proof. Let A = (Q; ; ; Q0; Qf ) be a NSFA. Construct a system of equations, using the set of states Q as variables: q = q0 i (q; ; q0) 2 , q = i (q; ; qf ) 2 ^ qf 2 Qf . Then L(A) = S q0 :
q02Q0
Theorem 1. N SF A = SHU F .
As an example, consider (fq0; q1g; fa; bg;f(q0; ab; q1); (q1; c; q1); (q1; cd; q0)g; fq0g; fq1g), which accepts the language fabg (fcdg fabg [ fcg) . 3
In this section we exhibit iteration lemmata for the rational, linear and algebraic
languages on catenation and shu e, which generalize the well known lemmata
for languages based on catenation (see also [
Iteration Lemmata Let the classes de ned by systems of equations be given by grammars in normal form, i.e. all productions are of the form X ! Y , X ! for RAT ( ; ), X ! Y , X ! Y , X ! for LIN ( ; ), and X ! Y Z, X ! for ALG( ; ), where X; Y; Z 2 V are variables, ; 2 C singletons, 2 f ; g.
Let jjwjj denote the length of the word jjwjj and for , jj jj := maxfjjwjj j w 2 g. Let X1 2 V be a distinguished (initial) variable, k = minfjj jj j 2 C; 6= f gg, and K = maxfjj jj j 2 Cg.
Furthermore, wlog it can be assumed that X ! f g implies X = X1 and in that case X1 doesn't occur on any righthand side of another production.
the yield of the tree, i.e. the set it evaluates to when seen as a term tree using and on the leaves, the following facts hold for d > 1: RAT ( ; ): (d 1) k jjAjj d K, LIN ( ; ): (d 1) k jjAjj d K, ALG( ; ): (d 1) k jjAjj 2d 1 K.
Note that, by the property of and , all x 2 A have the same length: 8x 2 A : jjxjj = jjAjj.
In the derivation tree nodes are labelled by pairs (X; ) 2 V f ; g, in case X ! Y Z with labels of children (Y; 0); (Z; 00), in case X ! Y or X ! Y with labels of children (Y; 0); or ; (Y; 0), respectively, and in case X ! with label of child .
Let = 2 jVj for RAT or LIN , and = 22 jVj 1 for ALG.
If now 9x 2 L : jjxjj > K then there exists a derivation tree for which a longest path from the root to the leaf has > 2 jVj nodes labelled with some (X; ). Therefore there exist 2 nodes with the same label on such a path. Numbering the labels from root to leaf with (X1; 1) to (Xd; d) one has (Xi; i) = (Xj ; j ) for some 1 i < j d where X` are variables and ` 2 f ; g. Note that for RAT and LIN there is just one longest path.
The rst case to be considered is RAT . Consider a derivation for a language L: (X1; 1) ! 1 ! 1 i 1 i ! 1 i 1 i ! 1 i 1 i ! 1 i 1 i which can be written 1(X2; 2) 1 ! 1 i 1(Xi; i) i 1 j 1(Xj ; j ) j 1 i i 1 j 1 j (Xj+1; j+1) j 1 j 1 j j+1 d 1Xd d 1 j 1 j j+1 d 1 d d 1
1 i i 1
j j 1 j j 1 1 (X1; 1) ! where % = 1 i 1, i
= i 1 1, = j 1 i, and , , % are terms.
Since (Xi; i) = (Xj ; j ) all k yields of derivation trees, and % k %(Xi; i) ! % (Xj ; j ) = j 1, i i 1 i i 1 1
1 ! % = j d 1 d d 1
j , k k and % k
L for k k are also terms and possible 0.
Choosing now (i; j) with (Xi; i) = (Xj ; j ) as the lowermost pair on the path, then 0 < jj jj . Furthermore,
i 0 < jj jj =: X
jj kjj
0 < jj jj 8k 2 N : % k 0 k
L.
Theorem 2. For any L 2 RAT ( ; ) there exists some 0 2 N such that for any x 2 L with jjxjj > 0 holds: x 2 % where % = 1 i 1, = i j 1, = j d 1 d d 1 j , = j 1 i, = i 1 1 2 f ; g, 2 C constants Lemma 3. L = fanbn j n
0g 62 RAT ( ; ).
Proof. If the iterated part in Theorem 2 consists either only of a's or b's then iteration would only increase the number of a's or b's, producing a word 62 L. If the iterated part contains both a's and b's then, since A B A B would produce some word uavbwaxby 62 L or ubvawbxay 62 L.
Theorem 3. LIN 6 RAT ( ; ).
The case LIN ( ; ) is similar. The di erence is that the expressions % and consists not only of operators but also constants , and not only of constants but also operators . , , and % , as well as k k and % k k (k 0), are terms as in case RAT ( ; ), and % k k L.
Taking now the uppermost pair (Xi; i) = (Xj ; j ) (i < j) one gets jj%
j 1 jj =: X jj kjj k=1
K :
Theorem 4. For any L 2 LIN ( ; ) there exists some 0 2 N such that for any x 2 L with jjxjj > 0 holds: x 2 % where %, , , are expressions with operators and constants 0 < jj% jj 0 8k 2 N : % k k L.
Lemma 4. L1 = fambmcndn j m; n 0g 62 LIN ( ; ),
L2 = fambmanbn j m; n 0g 62 LIN ( ; ),
L3 = fambm j m 0g 62 LIN ( ; ).
Proof. L1: If an iterated part contains 2 di erent symbols, e.g. a; b, then because of A B A B, some word uavbwaxby or ubvawbxay would be obtained. Therefore each iterated part can contain only 1 symbol. Now can contain only words aj bkc`dm. Hence the rst iterated part can contain only a's or b's. But then words with di erent numbers of a's and b's would be obtained. Similarly for the second iterated part. Similar for L2 and L3.
Theorem 5. CF 6 LIN ( ; ).
The case ALG( ; ) is even more general. Here the expressions % and consists not only of operators but also constants and entire terms, and not only of constants but also operators and entire terms. , , and % , as well as k k and % k k (k 0), are terms as in case RAT ( ; ), and % k k L.
Choosing the lowermost pair (Xi; i) = (Xj ; j ) (i < j) yields jj jj K.
Theorem 6. For any L 2 ALG( ; ) there exists some 0 2 N such that for any x 2 L with jjxjj > 0 holds: x 2 % where %, , , are expressions with operators, constants, and terms 0 < jj jj 0 8k 2 N : % k k L.
Lemma 5. L1 = fanbncn j n 0g 62 ALG( ; ),
L2 = famcnbmdn j m; n 0g 62 ALG( ; ).
Proof. Similar to the case LIN ( ; ). 3.2
Semilinearity Theorem 7. Any L 2 SHU F can be represented in the form
L = k [ ( i i=1
Ai ) where k < 1, i are singletons, and Ai nite sets.
Proof. Since
is commutative this is a special case of a general theorem in [
From this follows that SHU F is the same family that one gets when the operators iterated shu e, shu e and nally union of languages are applied any number of times, but in that order.
Lemma 6. SHU F = RAT ( ) = ([)( )( )(F IN ).
Theorem 8. Any L 2 ALG( ; ) is a semilinear set.
Proof. Any L 2 ALG( ; ) can be generated by a grammar in normal form.
From that construct a multiset grammar (also in normal form) as follows: for
X ! Y Z take X ! X Y , for X ! take X ! ( ), where ( ) is the
Parikh image of and multiset addition. By the property of and with
respect to addition of multiplicites of symbols and [
k (L) = [( ( i) i (Ai) ) : Since fa2n j n
0g 2 CS is not semilinear one gets Lemma 7. fa2n j n
0g 62 ALG( ; ).
CS. 4
In this section we consider closure properties of language classes under certain
operators, primarily for the more important classes from [
page, where [, \, , , , , \R, \S, , n, R, , and =1 denote union, intersection, catenation, shu e, catenation and shu e iteration, intersection with regular and shu e-rational sets, complement, set di erence, reversal, pre x, and left quotient with single words, respectively. 1. Union
Trivially, the classes RE G, LIN , CF , SHU F = RAT ( ) = ([; ; )(F IN ), E R = ([; ; ; )(F IN ), ([; ; ; )(F IN ), SE are closed under [. For the classes RAT ( ; ), LIN ( ; ), and ALG( ; ) this follows by construction of a grammar as follows:
sets of variables and initial variables X11, X21. Then L = L1 [ L2 is generated by a grammar with the union of variables for L1; L2, with additional initial variable X1 and additional productions X1 ! X11; X1 ! X21. 2. Intersection
It is well known that RE G is closed under \, whereas LIN and CF are not. Lemma 8. RE G ^ SHU F 6 ALG( ; ).
The structure of L1 \ L2 implies xi = _ xi = dyid and 8z 2 Ai : z = dz0d. Since jXj = 1, 9`9n : jfxnm j xnm 2 fx` A` gj = 1 (otherwise jL1 \L2 \Xj < 1). There is a maximal m with u(acb)md 2 fx`g [ A` since fx`g [ A` is nite. To get some v(acb)m0 d 2 X with m0 > m the only possibility is to use some w(acb)j d 2 A`. But that cannot produce u(acb)m0 d with m0 > m. 3. Catenation
From the well known closure of RE G and CF under , and the de nition
of the language classes it follows that E R and SE are closed under . For
RAT ( ; ), LIN ( ; ), and ALG( ; ) this is shown in a similar way as for
union, adding a new production X1 ! X11 X21. From the hierarchy results in
[
ply that RE G, SHU F , E S, SE are closed under , and that E R is not. For RAT ( ; ), LIN ( ; ), and ALG( ; ) closure is shown as for catenation, replacing by .
LIN and CF are not closed under since L1 = fambm j m 0g 2 LIN and L1 = fcndn j n 0g 2 LIN but
(L1 L2) \ (fag fcg fbg fdg ) = fambncmdn j m; n 0g 62 CF . 5. Catenation Iteration
Closure under catenation iteration is well known for RE G and CF . For E R, E S and SE this follows by de nition of the classes. For RAT ( ; ) and ALG( ; ) this is shown as follows:
For RAT ( ; ) replace all productions Y ! ( a constant) by productions Y ! X1 . For ALG( ; ) add a production X1 ! X1 X1.
It is also well known that LIN is not closed under catenation closure. SHU F
is not closed under by the hierarchy result in [
E R, E S, SE are closed under shu e iteration by de nition of the classes. For
RAT ( ; ) and ALG( ; ) this is shown as for catenation iteration, replacing
by . RE G is not closed under by the hierarchy results in [
L \ (fag fcg fbg fdg ) = famcnbmdn j m; n 0g 62 ALG( ; ). 7. Intersection with Regular Sets
Closure of RE G, LIN and CF under intersection with regular sets is well known. All other classes, except for E R, are not closed under \R by Lemma 8. 8. Intersection with Shu e-rational Sets
An analogous closure property is intersection with shu e-rational sets (\S). Lemma 8 implies that apart from RAT and E S all other classes are not closed under \S. 9. Complement
Since except for RE G all classes are not closed under intersection these classes are not closed under complement either. Thus the existence of an equivalent deterministic shu e nite automaton is rather improbable. 10. Set Di erence
ference either, except for RE G. 11. Reversal
For the classes de ned by algebraic closure this is a consequence from reversing all constants, and for those de ned by grammars in normal form a consequence from reversing all constants and replacing productions X ! Y Z by X ! Z Y . 12. Pre x
The set of pre xes of a language is de ned as (L) = fx j 9y : xy 2 Lg. Similarly suu xes are given by (L) = fx j 9y : yx 2 Lg. Then one has: Lemma 10. 1.
(L1 [ L2) = (L1) [ (L2),
structure of the expression follows that RE G, E R, SHU F and SE are closed under pre x operation.
For the closure of LIN and CF we recall the following proofs:
LIN : Consider a normal form grammar. De ne a copy V^ of the set of variables V, with X^1 as new initial variable, add a production X^ ! Y^ for any production X ! Y , X^ ! Y^ for any production Y ! Y , and X^ ! X for any variable.
CF : Similar to LIN , to a grammar in normal form add new productions X^ ! Y^ [ Y Z^ for any production X ! Y Z, and X^ ! X for any variable.
RAT ( ; ), LIN ( ; ) and ALG( ; ) are also closed under the pre x operation. Transform the equations of the equation system in normal form as follows: For X ! Y Z, add a new production X0 ! Y 0 Z0. Otherwise proceed as above. The correctness follows from lemma 10.
E S is not closed under pre x since (fabg ) = fabg fa; g 62 E S. This holds because for x 2 fabg fag one has jjxjja = jjxjjb + 1, and any iteration by or yields some y with jjyjja > jjyjjb + 1. Therefore a can only be added after an iteration. But for that only is available, giving e.g. uaav 62 (fabg ). 13. Quotient
A=B = fy 2 j 9x 2 B : xy 2 Ag. A special case is A = fxg with x 2 .
Lemma 11. A=(B [ C) = A=B [ A=C, A B (A=B),
2 B ) A A=B, jjfxg=Bjj < 1.
(A [ B)=C = A=C [ B=C, A=f g = A, A=B (A), Lemma 12. A=(B C) = (A=B)=C , (A B)=C = (A=C) B [ B=(C=A). Proof. z 2 A=(B C) , 9x 2 B 9y 2 C : (xy 2 B C ^ xyz 2 A) , 9x 2 B 9y 2 C : (xy 2 B C ^ yz 2 A=B ^ xyz 2 A) , z 2 (A=B)=C z 2 (A B)=C , 9x 2 C 9y0 2 9z0 2 B : (xy0 2 A ^ z = y0z0) _ 9x 2 C 9y 2 A 9z0 2 : (x = yz0 ^ z0z 2 B) , 9x 2 C 9y0 2 9z0 2 B : (y0 2 A=C ^ z = y0z0)
_ 9x 2 C 9y 2 A 9z0 2 : (z0 2 C=A ^ z0z 2 B) , z 2 (A=C) B _ z 2 B=(C=A).
Corollary 1. (A B)=fxg = (A=fxg) B [ B=(fxg=A). Note that jjfxg=Ajj < 1. For 2 f ; g de ne Lemma 13.
A( )0 = f g ; A( )(j+1) = A A( )j : A=B = A= [1 B( )i = [(A=B( )i) :
1 i=0
i=0 m Lemma 14. A =fxg = ([(A( )i=fxg)) A ; m jjxjj :
i=0
Note that A=B is the least x point of the monotone operator de ned by (A) = A [ A=B.
Proof. Wlog assume x 6= . x as a pre x can only be cut o from a a nite product A( )m with m jjxjj.
Lemma 15. (A B)=fxg = [ (A=fyg B=fzg) : y2 (A);z2 (B);x2fyg fzg Lemma 16. 1 i=1 (A=fyig) ; W = fyig : Proof. By induction. Wlog let x 6= . A( )0=fxg = f g=fxg = ;.
A( )1=fxg = A=fxg =
[ y12 (A);x2fy1g
A=fxg =
denotes the nite application of . Again, for given x union and are nite since there are only nitely many possible yj 2 for some m (A). Therefore,
Lemma 17. SHU F is closed under left quotient with a single word.
Lemma 18. SE is closed under left quotient with a single word. Proof. By structural induction using lemmata 11, 1, 15, 14, 16. k i=1 k i=1 m i=1 5
Since ALG( ; ) CS it follows that Theorem 10. The membership problem for ALG( ; ) is decidable. Theorem 11. Emptiness and niteness for ALG( ; ) are decidable. Proof. For the emptiness problem check whether there exists some w 2 L with jjwjj 2 0, and for the niteness problem whether there exists some w 2 L with 0 < jjwjj 2 0, using the iteration lemma for ALG( ; ). 6 Further research should be done in particular for more decidability problems, as language equivalence, whether the intersection of two languages is empty, or given a language of some class whether it belongs to a lower one. Such results are important in the area of concurrency.