Properties of Languages with Catenation and Shuffle Nils Erik Flick and Manfred Kudlek Fachbereich Informatik, MIN-Fakultät, Universität Hamburg, DE email: {flick,kudlek}@informatik.uni-hamburg.de Abstract. We present finite automata for shuffle languages, iteration lemmata for languages with catenation and shuffle, closure properties of such language classes, as well as decidability results. Keywords: shuffle catenation languages, structural and closure properties 1 Introduction In [4] language classes based on the two operators catenation and shuffle were investigated, and a complete hierarchy was established. Such classes are impor- tant in the area of concurrency, in particular for modelling client/server systems [2, 3]. This paper actually is a continuation of [4]. For definitions and results we refer to it. Here we deal in particular with the upper hierarchy of that article. In section 2 we introduce a finite automaton with shuffle as bascic operation as an analogon to well known finite automata with catenation as basic operation and show the equivalence to shuffle-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, shuffle, their iterations, intersection with regular and shuffle-rational sets, complement, set difference, reversal, prefix, and quotient. In section 5 some decidability results are presented. Some complexity results are given in [1]. In this article, always denotes concatenation of words or J languages J and denotes the shuffle of words, w v = {u1 vS1 · · · un vn |w = ui , v = vi }, also extended to languages by L1 L2 = v∈L1 ,w∈L2 v w. 2 Shuffle Finite Automata In case of shuffle as basic operator one can also define a finite automaton, the shuffle finite automaton. Remember that SHUF = RAT ( ) = (∪, , )(FIN ) is the closure of the finite languages under union, shuffle and iterated shuffle. Definition 1. Shuffle Finite Automaton A non-deterministic shuffle finite automaton N SF A is defined similar to finite automata as A = (Q, Σ, δ, Q0 , Qf ) with Q a finite set of states, Q0 ⊆ Q the initial states, Qf ⊆ Q the final states, Σ a finite set of symbols, and δ ⊆ Q × Σ ∗ × Q a finite set of transitions. A configuration of A is a pair (q, w) ∈ Q × Σ ∗ . A direct step of A is defined by (q, w) ` (q 0 , w0 ) iff (q, α, q 0 ) ∈ δ ∧ ∃w0 ∈ Σ ∗ : w ∈ {α} {w0 }. Let `∗ denote the reflexive and transitive closure of `. The language accepted by A is L(A) = {w ∈ Σ ∗ | ∃q0 ∈ Q0 ∃qf ∈ Qf : (q0 , w) `∗ (qf , λ)}. Let N SF A denote the class of all languages accepted by N SF A. Lemma 1. RAT ( ) ⊆ N SFA. Proof. L = {w} with w ∈ Σ ∗ . Then L is accepted by the shuffle finite automaton A = ({q0 , qf }, Σ, {(q0 , w, qf )}, {q0 }, {qf }). L = L1 ∪L2 . Let Ai = (Qi , Σi , δi , Q0i , Qf i ) accept Li . Wlog assume Q1 ∩Q2 = ∅. Then L is accepted by A = (Q, Σ, δ, Q0 , Qf ) where Q = Q1 ∪ Q2 , Q0 = {q0 }, Qf = Qf 1 ∪ Qf 2 , Σ = Σ1 ∪ Σ2 , and δ = {(q0 , λ, q0i ) | q0i ∈ Q0i , = i ∈ {1, 2}} ∪ δ1 ∪ δ2 . L = L1 L2 . Let Ai = (Qi , Σi , δi , Q0i , Qf i ) accept Li . Wlog assume Q1 ∩Q2 = ∅. Then L is accepted by A = (Q, Σ, δ, Q0 , Qf ) where Q = Q1 ∪ Q2 , Q0 = Q01 , Qf = Qf 2 , Σ = Σ1 ∪ Σ2 , and δ = {(qf 1 , λ, q02 ) | qf 1 ∈ Qf 1 , q02 ∈ Q02 } ∪ δ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 δ = {(qf , λ, q0 ) | q0 ∈ Q0 , qf ∈ Qf } ∪ δ 0  Lemma 2. N SF A ⊆ RAT ( ). Proof. Let A = (Q, Σ, δ, Q0 , Qf ) be a NSFA. Construct a system of equations, using the set of states Q as variables: q S= q 0 α iff (q, α, q 0 ) ∈ δ, q = α iff (q, α, qf ) ∈ δ ∗ ∧ qf ∈ Qf . Then L(A) = q0 .  q0 ∈Q0 From this we get Theorem 1. N SF A = SHUF. As an example, consider ({q0 , q1 }, {a, b},{(q0 , ab, q1 ), (q1 , c, q1 ), (q1 , cd, q0 )}, {q0 }, {q1 }), which accepts the language {ab} ({cd} {ab} ∪ {c}) . 3 Structural Properties In this section we exhibit iteration lemmata for the rational, linear and algebraic languages on catenation and shuffle, which generalize the well known lemmata for languages based on catenation (see also [7]), and semilinearity of all classes considered. Structural properties are used to show part of the relationships of RAT ( , ), LIN ( , ), ALG( , ) to the Chomsky hierarchy REG ⊂ CF ⊂ CS. 3.1 Iteration Lemmata Let the classes defined 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 ∈ V are variables, α, β ∈ C singletons, ◦ ∈ { , }. Let ||w|| denote the length of the word ||w|| and for α ⊆ Σ ∗ , ||α|| := max{||w|| | w ∈ α}. Let X1 ∈ V be a distinguished (initial) variable, k = min{||α|| | α ∈ C, α 6= {λ}}, and K = max{||α|| | α ∈ C}. Furthermore, wlog it can be assumed that X → {λ} implies X = X1 and in that case X1 doesn’t occur on any righthand side of another production. Consider now a derivation tree with depth d. Then for the set A defined by 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 ≤ ||A|| ≤ d · K, LIN ( , ): (d − 1) · k ≤ ||A|| ≤ d · K, ALG( , ): (d − 1) · k ≤ ||A|| ≤ 2d−1 · K. Note that, by the property of and , all x ∈ A have the same length: ∀x ∈ A : ||x|| = ||A||. In the derivation tree nodes are labelled by pairs (X, ◦) ∈ V × { , }, 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 · |V| for RAT or LIN , and κ = 22·|V|−1 for ALG. If now ∃x ∈ L : ||x|| > κ · K then there exists a derivation tree for which a longest path from the root to the leaf has > 2 · |V| 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 ◦` ∈ { , }. Note that for RAT and LIN there is just one longest path. In the sequel we shall use prefix notation. The first case to be considered is RAT . Consider a derivation for a language L: (X1 , ◦1 ) → ◦1 (X2 , ◦2 )α1 →∗ ◦1 · · · ◦i−1 (Xi , ◦i )αi−1 · · · α1 →∗ ◦1 · · · ◦i−1 ◦i · · · ◦j−1 (Xj , ◦j )αj−1 · · · αi αi−1 · · · α1 → ◦1 · · · ◦i−1 ◦i · · · ◦j−1 ◦j (Xj+1 , ◦j+1 )αj−1 · · · αi αi−1 · · · α1 →∗ ◦1 · · · ◦i−1 ◦i · · · ◦j−1 ◦j ◦j+1 · · · ◦d−1 Xd αd−1 · · · αj αj−1 · · · αi αi−1 · · · α1 → ◦1 · · · ◦i−1 ◦i · · · ◦j−1 ◦j ◦j+1 · · · ◦d−1 αd αd−1 · · · αj αj−1 · · · αi αi−1 · · · α1 which can be written (X1 , ◦1 ) →∗ %(Xi , ◦i )ξ →∗ %σ(Xj , ◦j )ηξ →∗ %στ ηξ where % = ◦1 · · · ◦i−1 , σ = ◦i · · · ◦j−1 , τ = ◦j · · · ◦d−1 αd αd−1 · · · αj , ξ = αi−1 · · · α1 , η = αj−1 · · · αi , and τ , στ η, %στ ηξ are terms. Since (Xi , ◦i ) = (Xj , ◦j ) all σ k τ η k and %σ k τ η k ξ are also terms and possible yields of derivation trees, and %σ k τ η k ξ ⊆ L for k ≥ 0. Choosing now (i, j) with (Xi , ◦i ) = (Xj , ◦j ) as the lowermost pair on the path, then 0 < ||στ η|| ≤ κ. Furthermore, i X 0 < ||η|| =: ||αk || ≤ κ · K . k=j−1 Therefore Theorem 2. For any L ∈ RAT ( , ) there exists some κ0 ∈ N such that for any x ∈ L with ||x|| > κ0 holds: x ∈ %στ ηξ where % = ◦1 · · · ◦i−1 , σ = ◦i · · · ◦j−1 , τ = ◦j · · · ◦d−1 αd αd−1 · · · αj , η = αj−1 · · · αi , ξ = αi−1 · · · α1 ◦ ∈ { , }, α ∈ C constants 0 < ||στ η|| ≤ κ0 ∀k ∈ N : %σ k τ η k ξ ⊆ L. Lemma 3. L = {an bn | n ≥ 0} 6∈ 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 6∈ L. If the iterated part contains both a’s and b’s then, since A B ⊆ A B would produce some word uavbwaxby 6∈ L or ubvawbxay 6∈ L.  This implies Theorem 3. LIN 6⊆ RAT ( , ). The case LIN ( , ) is similar. The difference 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 j−1 X ||%σηξ|| =: ||αk || ≤ κ · K . k=1 From this one gets Theorem 4. For any L ∈ LIN ( , ) there exists some κ0 ∈ N such that for any x ∈ L with ||x|| > κ0 holds: x ∈ %στ ηξ where %, σ, η, ξ are expressions with operators and constants 0 < ||%σηξ|| ≤ κ0 ∀k ∈ N : %σ k τ η k ξ ⊆ L. Lemma 4. L1 = {am bm cn dn | m, n ≥ 0} 6∈ LIN ( , ), L2 = {am bm an bn | m, n ≥ 0} 6∈ LIN ( , ), L3 = {am bm | m ≥ 0} 6∈ LIN ( , ). Proof. L1 : If an iterated part contains 2 different 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 bk c` dm . Hence the first iterated part can contain only a’s or b’s. But then words with different numbers of a’s and b’s would be obtained. Similarly for the second iterated part. Similar for L2 and L3 .  From this follows 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 ||στ η|| ≤ κ·K. From this follows Theorem 6. For any L ∈ ALG( , ) there exists some κ0 ∈ N such that for any x ∈ L with ||x|| > κ0 holds: x ∈ %στ ηξ where %, σ, η, ξ are expressions with operators, constants, and terms 0 < ||στ η|| ≤ κ0 ∀k ∈ N : %σ k τ η k ξ ⊆ L. Lemma 5. L1 = {an bn cn | n ≥ 0} 6∈ ALG( , ), L2 = {am cn bm dn | m, n ≥ 0} 6∈ ALG( , ). Proof. Similar to the case LIN ( , ).  3.2 Semilinearity Theorem 7. Any L ∈ SHU F can be represented in the form k [ L= (αi Ai ) i=1 where k < ∞, αi are singletons, and Ai finite sets. Proof. Since is commutative this is a special case of a general theorem in [8]. From this follows that SHUF is the same family that one gets when the operators iterated shuffle, shuffle and finally union of languages are applied any number of times, but in that order. Lemma 6. SHUF = RAT ( ) = (∪)( )( )(FIN ). Any of the classes considered contain only semilinear sets. Theorem 8. Any L ∈ ALG( , ) is a semilinear set. Proof. Any L ∈ 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 [9] one gets a semilinear set, more precisely [k ψ(L) = (ψ(αi ) ⊕ ψ(Ai )⊕ ) . i  n Since {a2 | n ≥ 0} ∈ CS is not semilinear one gets n Lemma 7. {a2 | n ≥ 0} 6∈ ALG( , ). Theorem 9. ALG( , ) ⊂ CS. 4 Closure Properties In this section we consider closure properties of language classes under certain operators, primarily for the more important classes from [4]. These are, apart from REG, LIN and CF, the classes ER (extended regular expressions of [6]), SHUF, ES = (∪, , , )(FIN ) (extended shuffle expressions, in analogy to ER), SE = (∪, , , , )(FIN ) (the languages defined by the so-called shuffle expressions of [5]), RAT ( , ), LIN ( , ), and ALG( , ). In the sequel ∧ applied on language classes has the meaning L1 ∧ L2 = {L1 ∩ L2 | L1 ∈ L1 , L2 ∈ L2 }. Similarly for operators ∨ (for ∪), , and . All closure results achieved so far are summarized in Table 1 on the facing page, where ∪, ∩, , , , , ∩R, ∩S, − , \, R , π, and /1 denote union, in- tersection, catenation, shuffle, catenation and shuffle iteration, intersection with regular and shuffle-rational sets, complement, set difference, reversal, prefix, and left quotient with single words, respectively. 1. Union Trivially, the classes REG, LIN , CF, SHUF = RAT ( ) = (∪, , )(FIN ), ER = (∪, , , )(FIN ), (∪, , , )(FIN ), SE are closed under ∪. For the classes RAT ( , ), LIN ( , ), and ALG( , ) this follows by construction of a grammar as follows: Let L1 , L2 be generated by grammars in normal form with initial disjoint 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 REG is closed under ∩, whereas LIN and CF are not. Lemma 8. REG ∧ SHUF 6⊆ ALG( , ). ∪ ∩ ∩R ∩S − \ R π /1 REG Y Y Y Y Y N Y N Y Y Y Y Y LIN Y N N N N N Y N N N Y Y Y CF Y N Y N Y N Y N N N Y Y Y ER Y N Y N Y Y N N N N Y Y N Table 1 SHUF Y N N Y N Y N N N N Y Y Y ES Y N N Y Y Y N N N Y N N SE Y N Y Y Y Y N N N N Y Y Y RAT ( , ) Y N Y Y Y Y N N N N Y Y LIN ( , ) Y N N N N N N N N N Y Y ALG( , ) Y N Y Y Y Y N N N N Y Y Proof. Consider L1 = {a} {b} {c} and L2 = {abc} . Then L1 ∩ L2 = {an bn cn | n ≥ 0} 6∈ ALG( , ) by Lemma 5. Note that L1 ∈ ( , )(FIN ) and L2 ∈ ( )(FIN ).  The hierarchy results in [4] imply that ER, ES, SE, RAT ( , ), LIN ( , ), and ALG( , ) are not closed under ∩. It remains to investigate SHUF. Lemma 9. SHUF ∧ SHU F 6⊆ SHU F. Proof. Consider L1 = {da, bd, ba, c} ∈ SHUF and {dd, acb} ∈ SHUF, and assume L1 ∩ L2 ∈ SHU F. It is easy to see that x ∈ L1 ∩ L2 ⇒ x = λ ∨ x = dx0 d. Furthermore X = {xmn = dn an cn bn dn d(acb)m d | m, n ≥ 1} ⊆ L1 ∩ L2 since xmn ∈ {da}( )n {bd}( )n {c}( )n {da} {bd} {ba}( )(m−1) {c}( )m and xmn ∈ {dd}( )n {acb}( )n {dd} {acb}( )m . By the normal form theorem for SHUF k [ L1 ∩ L2 = ({xi } Ai ) . i=1 The structure of L1 ∩ L2 implies xi = λ ∨ xi = dyi d and ∀z ∈ Ai : z = dz 0 d. Since |X| = ∞, ∃`∃n : |{xnm | xnm ∈ {x` A` }| = ∞ (otherwise |L1 ∩L2 ∩X| < ∞). There is a maximal m with u(acb)m d ∈ {x` } ∪ A` since {x` } ∪ A` is finite. 0 To get some v(acb)m d ∈ X with m0 > m the only possibility is to use some 0 w(acb)j d ∈ A` . But that cannot produce u(acb)m d with m0 > m.  3. Catenation From the well known closure of REG and CF under , and the definition of the language classes it follows that ER 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 [4] follows that SHUF and ES are not closed under catenation. 4. Shuffle The hierarchy result in [4] and the definition of the language classes im- ply that REG, SHUF, ES, SE are closed under , and that ER is not. For RAT ( , ), LIN ( , ), and ALG( , ) closure is shown as for catenation, replacing by . LIN and CF are not closed under since L1 = {am bm | m ≥ 0} ∈ LIN n n and L1 = {c d | n ≥ 0} ∈ LIN but (L1 L2 ) ∩ ({a} {c} {b} {d} ) = {am bn cm dn | m, n ≥ 0} 6∈ CF. 5. Catenation Iteration Closure under catenation iteration is well known for REG and CF. For ER, ES and SE this follows by definition of the classes. For RAT ( , ) and ALG( , ) this is shown as follows: Let L be generated by a grammar in normal form with initial variable X1 . 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. SHUF is not closed under by the hierarchy result in [4]. LIN ( , ) is not closed under by Lemma 4. 6. Shuffle Iteration ER, ES, SE are closed under shuffle iteration by definition of the classes. For RAT ( , ) and ALG( , ) this is shown as for catenation iteration, replacing by . REG is not closed under by the hierarchy results in [4] and definition. LIN , CF and LIN ( , ) are not closed under shuffle iteration since L = {am bm , cn dn | m, n ≥ 0} ∈ LIN but L ∩ ({a} {c} {b} {d} ) = {am cn bm dn | m, n ≥ 0} 6∈ ALG( , ). 7. Intersection with Regular Sets Closure of REG, LIN and CF under intersection with regular sets is well known. All other classes, except for ER, are not closed under ∩R by Lemma 8. 8. Intersection with Shuffle-rational Sets An analogous closure property is intersection with shuffle-rational sets (∩S). Lemma 8 implies that apart from RAT and ES all other classes are not closed under ∩S. 9. Complement Since except for REG all classes are not closed under intersection these classes are not closed under complement either. Thus the existence of an equivalent deterministic shuffle finite automaton is rather improbable. 10. Set Difference Since all classes contain the language Σ ∗ they are not closed under set dif- ference either, except for REG. 11. Reversal All language classes considered are closed under reversal (or mirror image). For the classes defined by algebraic closure this is a consequence from reversing all constants, and for those defined by grammars in normal form a consequence from reversing all constants and replacing productions X → Y ◦Z by X → Z ◦Y . 12. Prefix The set of prefixes of a language is defined as π(L) = {x | ∃y : xy ∈ L}. Similarly suufixes are given by σ(L) = {x | ∃y : yx ∈ L}. Then one has: Lemma 10. 1. π(L1 ∪ L2 ) = π(L1 ) ∪ π(L2 ), 2. π(L1 L2 ) = π(L1 ) ∪ L1 π(L2 ), 3. π(L ) = L π(L), 4. π(L1 L2 ) = π(L1 ) π(L2 ), 5. π(L ) = (π(L)) . Proof. 1., 2.: trivial. 3.: π(L ) = π(L L ∪ {λ}) = π(L L) ∪ {λ} =L π(L) ∪ π(L) ∪ {λ} = L π(L). 4.: Wlog the shuffle of two languages can be expressed as n K n K n K L1 L2 = {x ∈ Σ ∗ | x = yi zi ∧ yi ∈ L1 ∧ zi ∧ ||yi || ≤ 1 ∧ ||zi || ≤ 1} i=1 i=1 i=1 J where denotes finite application of . Then m−1 K n K π(L1 L2 ) = {u ∈ Σ ∗ | ((u = ( yi zi ) ym ∧ v = zm yi zi ) i=1 i=m+1 m K n K n K n K ∨ (u = yi zi ∧ v = yi zi )) ∧ xi ∈ L1 ∧ yi ∈ L2 } i=1 i=m+1 i=1 i=1 m−1 K m K m−1 K = {u ∈ Σ ∗ | (u = yi zi ) ym ∧ yi ∈ π(L1 ) ∧ zi ∈ π(L2 )) i=1 i=1 i=1 m K m K m K ∨ (u = yi zi ∧ yi ∈ π(L1 ) ∧ zi ∈ π(L2 ))} = π(L1 ) π(L2 ) . i=1 i=1 i=1 5.: By induction from 4.  From Lemma 10, the algebraic definition of classes and by induction on the structure of the expression follows that REG, ER, SHUF and SE are closed under prefix operation. For the closure of LIN and CF we recall the following proofs: LIN : Consider a normal form grammar. Define a copy V̂ of the set of vari- ables V, with X̂1 as new initial variable, add a production X̂ → Ŷ for any production X → Y α, X̂ → α Ŷ 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 Ẑ for any production X → Y Z, and X̂ → X for any variable. RAT ( , ), LIN ( , ) and ALG( , ) are also closed under the prefix operation. Transform the equations of the equation system in normal form as follows: For X → Y Z, add a new production X 0 → Y 0 Z 0 . Otherwise proceed as above. The correctness follows from lemma 10. ES is not closed under prefix since π({ab} ) = {ab} {a, λ} 6∈ ES. This holds because for x ∈ {ab} {a} one has ||x||a = ||x||b + 1, and any iteration by or yields some y with ||y||a > ||y||b + 1. Therefore a can only be added after an iteration. But for that only is available, giving e.g. uaav 6∈ π({ab} ). 13. Quotient The left (catenation) quotient of a language A by B is defined by A/B = {y ∈ Σ ∗ | ∃x ∈ B : xy ∈ A}. A special case is A = {x} with x ∈ Σ ∗ . Trivially one has Lemma 11. A/(B ∪ C) = A/B ∪ A/C, (A ∪ B)/C = A/C ∪ B/C, A ⊆ B (A/B), A/{λ} = A, λ ∈ B ⇒ A ⊆ A/B, A/B ⊆ σ(A), ||{x}/B|| < ∞. Furthermore Lemma 12. A/(B C) = (A/B)/C , (A B)/C = (A/C) B ∪ B/(C/A). Proof. z ∈ A/(B C) ⇔ ∃x ∈ B ∃y ∈ C : (xy ∈ B C ∧ xyz ∈ A) ⇔ ∃x ∈ B ∃y ∈ C : (xy ∈ B C ∧ yz ∈ A/B ∧ xyz ∈ A) ⇔ z ∈ (A/B)/C z ∈ (A B)/C ⇔ ∃x ∈ C ∃y 0 ∈ Σ ∗ ∃z 0 ∈ B : (xy 0 ∈ A ∧ z = y 0 z 0 ) ∨ ∃x ∈ C ∃y ∈ A ∃z 0 ∈ Σ ∗ : (x = yz 0 ∧ z 0 z ∈ B) ⇔ ∃x ∈ C ∃y 0 ∈ Σ ∗ ∃z 0 ∈ B : (y 0 ∈ A/C ∧ z = y 0 z 0 ) ∨ ∃x ∈ C ∃y ∈ A ∃z 0 ∈ Σ ∗ : (z 0 ∈ C/A ∧ z 0 z ∈ B) ⇔ z ∈ (A/C) B ∨ z ∈ B/(C/A).  This implies Corollary 1. (A B)/{x} = (A/{x}) B ∪ B/({x}/A). Note that ||{x}/A|| < ∞. For ◦ ∈ { , } define A(◦)0 = {λ} , A(◦)(j+1) = A◦A(◦)j . ∞ ∞ Lemma 13. A/B = A/ [ B ( )i = [ (A/B ( )i ) . i=0 i=0 Proof. Applying Lemma 11.  Note that A/B is the least fix point of the monotone operator τ defined by τ (A) = A ∪ A/B. m [ Lemma 14. A /{x} = ( (A( )i /{x})) A , m ≤ ||x|| . i=0 Proof. Wlog assume x 6= λ. x as a prefix can only be cut off from a a finite product A( )m with m ≤ ||x||.  [ Lemma 15. (A B)/{x} = (A/{y} B/{z}) . y∈π(A),z∈π(B),x∈{y} {z} Proof. w ∈ (A B)/{x} ⇔ xw ∈ A B ⇔ ∃y ∈ A ∃z ∈ B : xw ∈ {y} {z} ⇔ ∃y1 ∈ A ∃y2 ∈ A ∃z1 ∈ B ∃z2 ∈ B : (y = y1 y2 ∧ z = z1 z2 ∧ x ∈ {y1 } {z1 } ∧ w ∈ {y2 } {z2 }) ⇔ y1 ∈ π(A) ∧ z1 ∈ π(B) ∧ x ∈ {y1 } {z1 } ∧ w ∈ (A/{y1 }) (B/{z1 }). Note that for given x the union is finite.  [ ∞ ∞ Lemma 16. A /{x} = (A/{yi }) , W = {yi } . yj ∈π(A),x∈W i=1 i=1 Proof. By induction. Wlog let x 6= λ. A( )0 /{x} = {λ}/{x} = ∅. [ A( )1 /{x} = A/{x} = A/{x} y1 ∈π(A),x∈{y1 } [ k k ( )k A /{x} = (A/{yi }) , Wk = {yi } . yj ∈π(A),x∈Wk i=1 i=1 A( )(k+1) /{x} = (A( )k A)/{x} [ = (A( )k /{y}) (A/{y(k+1) }) y∈A( )k ,y (k+1) ∈π(A),x∈{y} {y(k+1) } [ [ k = (A/{yi }) (A/{y(k+1) }) y∈π(A( (k+1) ∈π(A),x∈{y} {y(k+1) } yj ∈π(A),y∈Wk i=1 )k ),y [ k+1 k = (A/{yi }) , W(k+1) = {yi } . yj ∈π(A),x∈W(k+1) i=1 i=1 Here denotes the finite application of . Again, for given x union and are finite since there are only finitely many possible yj ∈ π(A). Therefore, for some m [ m m A /{x} = (A/{yi }) , W = {yi } . yj ∈π(A),x∈W i=1 i=1  From the considerations above follows Lemma 17. SHUF is closed under left quotient with a single word. Proof. By structural induction using lemmata 11, 15, 16.  Lemma 18. SE is closed under left quotient with a single word. Proof. By structural induction using lemmata 11, 1, 15, 14, 16.  Symmetrically,both are also closed under right quotient with a single word. For the classes REG, LIN , and CF it is well known that they are closed under left and right quotient with regular sets, hence also under left and right quotient with a single word. Since {ab} /1 {a} = {b} {ab} 6∈ ES which can be shown as for the nonclo- sure of ES under prefix, ES is not closed under left quotient with a single word. ER is not because {abc} /{a} = {bc} {abc} 6∈ ER by [4] Lemma 7. 5 Decidability Properties In this section we present some decidability results. Since ALG( , ) ⊂ CS it follows that Theorem 10. The membership problem for ALG( , ) is decidable. Theorem 11. Emptiness and finiteness for ALG( , ) are decidable. Proof. For the emptiness problem check whether there exists some w ∈ L with ||w|| ≤ 2 · κ0 , and for the finiteness problem whether there exists some w ∈ L with κ0 < ||w|| ≤ 2 · κ0 , using the iteration lemma for ALG( , ).  6 Outlook 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. References 1. Berglund, Martin; Björklund, Henrik; Högberg, Johanna: Recognizing Shuffle Lan- guages. LNCS 6638, pp. 142-154, 2011. 2. Czaja, Ludwik: On Deadlock and Fairness Decision Problems for Computations on Client-server Systems. FI 109 (3) pp. 255-264, 2011. 3. Czaja, Ludwik; Kudlek, Manfred: Language Theoretic Properties of Client/Server Systems. Proceedings of CS&P 2011, pp. 79-84, 2011. 4. Flick, Nils Erik; Kudlek, Manfred: On A Hierarchy of Languages with Catenation and Shuffle. DLT, LNCS 7410/2012, pp. 452–458, Springer 2012. 5. Gischer, Jay: Shuffle Languages, Petri Nets, and Context-sensitive Grammars. CACM 24 (9), pp. 597–605, 1981. 6. Jantzen, Matthias: Extending Regular Expressions with Iterated Shuffle. TCS 38, pp. 223–247, 1985. 7. Kudlek, Manfred: On General Iteration Lemmata for Certain Classes of Word, Trace and Graph Languages. FI 37 (4), pp. 413–422, 1999. 8. Kudlek, Manfred: On Semilinear Sets over Commutative Semirings. FI 79 (3-4), pp. 447–452, 2007. 9. Kudlek, Manfred; Martı́n Vide, Carlos; Păun, Gheorghe: Toward FMT ( Formal Macroset Theory ). In: Multiset Processing, eds. Calude, Cristian; Păun, Gheorghe; Rozenberg, Grzegorz; Salomaa, Arto, LNCS 2235, pp. 123-133, 2000.