=Paper=
{{Paper
|id=None
|storemode=property
|title=Properties of Languages with Catenation and Shuffle
|pdfUrl=https://ceur-ws.org/Vol-928/0091.pdf
|volume=Vol-928
|dblpUrl=https://dblp.org/rec/conf/csp/FlickK12
}}
==Properties of Languages with Catenation and Shuffle==
https://ceur-ws.org/Vol-928/0091.pdf
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.