\section{Closure properties}\label{sec:closure}

In this section we argue that  \malyprefix{pc}\CFL}  % $^\text{pc}$\ and \malyprefixpodw{tr}{pc}\CFL\ classes are closed under union and shuffle, and
 \malyprefix{pc}\CFL}  % $^\text{pc}$\ is closed under concatenation while \malyprefixpodw{tr}{pc}\CFL\ is not.
Then we show that \malyprefix{pc}\CFL}  % $^\text{pc}$\ is closed under homomorphic images and substitutions. 
In case of \malyprefixpodw{tr}{pc}\CFL\ we do not know the answer, however we suppose it is negative.
Finally, we show that both classes lack closure under inverse homomorphic images and
intersections with regular languages.

Comparing \malyprefix{pc}\CFL}  % $^\text{pc}$\ with {\sc cfl}, roughly speaking, one sacrifices intersection with regular languages and inverse homomorphic images but one gains shuffle.
Even if at first sight the properties listed above do not seem exciting, one should remember that 
both the classes considered here subsume also commutative context-free languages \malyprefix{c}\CFL}  % $^\text{c}$. 
Knowing that \malyprefix{c}\CFL}  % $^\text{c}$\ lacks closure under concatenation and homomorphic images, as shown in~\cite{PHDChristensen},
it seems that with \malyprefix{pc}\CFL}  % $^\text{pc}$\ one \emph{retrieves} these relevant closure properties.
This seems to confirm that \malyprefix{pc}\CFL}  % $^\text{pc}$\ is a natural class of languages.


\smallsection{Union and complement}
Both classes are closed under union and the construction is entirely standard.
On the other hand none of the classes is closed under complement.
\removed{
Assume two languages $L_1$ and $L_2$ belonging either to \malyprefixpodw{tr}{pc}\CFL\ or to \malyprefix{pc}\CFL}  % $^\text{pc}$.
Let $S_1$ and $S_2$ be the initial non-terminals of the corresponding grammars.
Then the grammar for $L_1 \cup L_2$ is straightforwardly obtained by adding to the union of two grammars
one additional initial non-terminal $S$ and additional productions
$S \trans[a] \alpha$ for all productions $S_1 \trans[a] \alpha$ or $S_2 \trans[a] \alpha$.
The dependence relation is the set-theoretic union of the two dependence relations,
thus transitivity of dependence is clearly preserved.
}


\smallsection{Shuffle and concatenation}
Both classes are closed under shuffle and the construction of a grammar for the shuffle 
$L_1 \, || \, L_2$ is easy. 
Wlog assume that the grammars that generate the two languages use distinct non-terminals.
Let $S_1$ and $S_2$ be the initial non-terminals.
Consider the union of grammars extended with one additional initial non-terminal $S$.
Add additional productions
\begin{equation} \label{eq:shuffleinit}
S \trans[a_1] \alpha_1 S_2  \qquad S \trans[a_2] \alpha_2 S_1
\end{equation}
for any production $S_1\trans[a_1]\alpha_1$ or $S_2\trans[a_2]\alpha_2$.
Finally, extend independence by imposing that whenever two non-terminals come from
different grammars they are independent. This clearly preserves transitivity of dependence.

In \malyprefix{pc}\CFL}  % $^\text{pc}$, concatenation $L_1 L_2$ is obtained similarly as shuffle.
The only difference is that two non-terminals coming from different grammars are always declared dependent,
and that only the left-hand productions in~\eqref{eq:shuffleinit} are added.
Note that concatenation is in our setting no more natural than shuffle.

\malyprefixpodw{tr}{pc}\CFL\ is not closed under concatenation, which one shows similarly as for \malyprefix{c}\CFL}  % $^\text{c}$~\cite{PHDChristensen}.
Consider $L_1 = \{ w : \nrof{a}{w} = \nrof{b}{w} = \nrof{c}{w} \geq 1, \nrof{d}{w} = 0 \}$ and $L_2 = \{ d \}$.
In the derivation of some $w \in L_1 L_2$ a configuration is necessarily reached with at least two different {thread}s nonempty,
as otherwise the language would be context-free. Thus the remaining suffix of $w$ is some shuffle of at least two words generated by 
these non-empty {thread}s, and only one of these words ends with $d$. If that subword is generated first, the whole word is not in $L_1 L_2$, which proves that $L_1 L_2$ may not belong to \malyprefix{c}\CFL}  % $^\text{c}$.


\smallsection{Homomorphic images and substitutions}
As we consider only Greibach grammars, the empty word never belongs to a partially-commutative context-free language.
Thus it is natural to consider only homomorphisms $h$ that do not contain the empty word in the image: $h(a) \neq \varepsilon$ for all letters $a$. 
Below we show that \malyprefix{pc}\CFL}  % $^\text{pc}$\ is closed under images of such homomorphisms. For \malyprefixpodw{tr}{pc}\CFL\ the question is still open;
we conjecture however a negative answer. 

We prefer to show a slightly stronger result: \malyprefix{pc}\CFL}  % $^\text{pc}$\ is closed under \emph{substitutions}.
A substitution $s$ assigns to each alphabet letter $a$ a language $s(a) \in $ \malyprefix{pc}\CFL}  % $^\text{pc}$. Similarly as above, we assume that the languages
$s(a)$ do not contain the empty word. For a language $L$, the substitution $L[s]$ contains all words that may be obtained from a word in $L$, by replacing each letter $a$ with any word from $s(a)$.

Assume a language $L \in$ \malyprefix{pc}\CFL}  % $^\text{pc}$, generated by a grammar $G$, and a substitution $s$. Thus each language $s(a)$ has its generating grammar $G_a$. We describe the construction of the grammar $G'$ for $L[s]$. The non-terminals of $G'$ will be the union of non-terminals of $G$ and all grammars $G_a$. Wlog we assume that the non-terminal sets are disjoint.

Consider an arbitrary production
$X \trans[a] \alpha$ in $G$.
Let $S_a$ be the initial non-terminal in $G_a$. For any production
$S_a \trans[b] \beta$
in $G_a$, we add to $G'$ the production:
$X \trans[b] \beta \alpha$.
The independence in $G'$ is defined as the set-theoretic union of independence relations of grammars $G$ and $G_a$.
Thus any pair of non-terminals coming from different grammars is declared dependent (note that this is not achievable if the dependence has to be transitive).

The construction guarantees that $G'$ generates exactly $L[s]$. Indeed, once a production $X \trans[b] \beta \alpha$ is fired, the non-terminals of $G_a$ block activity of other non-terminals, due to the dependence, until a word of $s(a)$ is generated.

We do not know whether the \malyprefixpodw{tr}{pc}\CFL\ class is closed under homomorphic images; however we suppose it is not. We conjecture that a counterexample is given by the language
\[
L = \{w: \nrof{a}{w}  = \nrof{b}{w} = \nrof{c}{w}, \nrof{d}{w} = 1\}
\]
together with the homomorphism $h(a) = a$, $h(b) = b$, $h(c) = c$, $h(d) = dd$.


\smallsection{Intersection with regular languages}
Both classes \malyprefix{pc}\CFL}  % $^\text{pc}$\ and \malyprefixpodw{tr}{pc}\CFL\ lack closure under intersection with regular languages.
Let $L=\{w: \nrof{a}{w} = \nrof{b}{w} = \nrof{c}{w} \}$. Clearly $L \in $ \malyprefix{c}\CFL}  % $^\text{c}$\ but
$L \cap a^*b^*c^*$ is not in \malyprefix{pc}\CFL}  % $^\text{pc}$\ (and also not in \malyprefix{shuffle}\CFL\ defined in a moment) according to:
\begin{lemma}\label{anbncn}
The language $L=\{a^n b^n c^n: n \geq 1\}$ is not in \malyprefix{pc}\CFL}  % $^\text{pc}$\ $\cup$ \malyprefix{shuffle}\CFL.
\end{lemma}
It is worth noting that the lack of closure is not surprising as the emptiness problem
for intersection of a partially-com\-mu\-ta\-tive context-free language with a regular language is undecidable,
even if the dependence is assumed to be transitive.
Roughly speaking \malyprefixpodw{tr}{pc}\CFL\ correspond to stateless multi-pushdown
automata and intersection with regular language corresponds do adding the state which makes the
model Turing powerful.

\smallsection{Inverse homomorphic images}
Both  \malyprefix{pc}\CFL}  % $^\text{pc}$\ and \malyprefixpodw{tr}{pc}\CFL\ are not closed under inverse homomorphic images.
Consider the shuffle $L = L_1 \, || \, L_2$  of two context-free languages 
\[
L_1=\{A^{n+1} S B^n T : n \geq 1 \} \qquad L_2=\{S B^n T C^n : n \geq 1 \},
\]
and  
the homomorphism $h$ given by $h(a)=A$, $h(s)=SS$, $h(b)=BB$, $h(t)=TT$ and $h(c)=C$. 
If $h^{-1}(L) = \{a^{n+1} s b^n t c^n: n \geq 1\}$ were in \malyprefix{pc}\CFL}  % $^\text{pc}$\ then its image under a homomorphism $g(s) = b, g(t) = c$,
that is the language $L$ in Lemma~\ref{anbncn}, would be in \malyprefix{pc}\CFL}  % $^\text{pc}$\ as well -- a contradiction.




\removed{
\smallsection{Complement}

None of the classes is closed under complement as otherwise one would deduce closure under intersection, using the law
\begin{equation*}
L\cap K = \overline{\overline{L}\cup\overline{K}} .
\end{equation*}
}




\section{Expressiveness}\label{sec:express}

Now we are ready to compare the expressive power of \malyprefixpodw{tr}{pc}\CFL\ and \malyprefix{pc}\CFL}  % $^\text{pc}$\ with other classes.
We show that \malyprefixpodw{tr}{pc}\CFL\ is a strict subclass of \malyprefix{pc}\CFL}  % $^\text{pc}$\ and that
both \malyprefix{shuffle}\CFL\ and \malyprefix{trace}\CFL\ are incomparable with either \malyprefix{pc}\CFL}  % $^\text{pc}$\ or \malyprefixpodw{tr}{pc}\CFL.
More specifically, our results are as follows:
\newcommand{\tPCCFL\ is a strict subclass of \PCCFL}{\malyprefixpodw{tr}{pc}\CFL\ is a strict subclass of \malyprefix{pc}\CFL}  % $^\text{pc}$}
\begin{theorem} \label{thm:strict}
\tPCCFL\ is a strict subclass of \PCCFL.
\end{theorem}
\newcommand{\tPCCFL\ is not included in \PAL\ $\cup$ \TCFL}{\malyprefixpodw{tr}{pc}\CFL\ is not included in \malyprefix{shuffle}\CFL\ $\cup$ \malyprefix{trace}\CFL}
\newcommand{\PAL\ is not included in \PCCFL\ $\cup$ \TCFL}{\malyprefix{shuffle}\CFL\ is not included in \malyprefix{pc}\CFL}  % $^\text{pc}$\ $\cup$ \malyprefix{trace}\CFL}
\newcommand{\TCFL\ is not included in \PCCFL\ $\cup$ \PAL}{\malyprefix{trace}\CFL\ is not included in \malyprefix{pc}\CFL}  % $^\text{pc}$\ $\cup$ \malyprefix{shuffle}\CFL}
\newcommand{\tPCCFL\ $\cap$ \PAL\ is not included in \TCFL}{\malyprefixpodw{tr}{pc}\CFL\ $\cap$ \malyprefix{shuffle}\CFL\ is not included in \malyprefix{trace}\CFL}
\newcommand{\tPCCFL\ $\cap$ \TCFL\ is not included in \PAL}{\malyprefixpodw{tr}{pc}\CFL\ $\cap$ \malyprefix{trace}\CFL\ is not included in \malyprefix{shuffle}\CFL}
\begin{theorem} \label{thm:non-incl-add}
The following non-inclusions hold:
\begin{enumerate}
\item[(1)] \tPCCFL\ $\cap$ \PAL\ is not included in \TCFL.
\item[(2)] \tPCCFL\ $\cap$ \TCFL\ is not included in \PAL.
\end{enumerate}
\end{theorem}

\begin{theorem} \label{thm:non-incl}
The following non-inclusions hold:
\begin{enumerate}
\item[(1)] \tPCCFL\ is not included in \PAL\ $\cup$ \TCFL;
\item[(2)] \PAL\ is not included in \PCCFL\ $\cup$ \TCFL;
\item[(3)] \TCFL\ is not included in \PCCFL\ $\cup$ \PAL.
\end{enumerate}
\end{theorem}
The proofs of the results are by identifying witnessing languages
$L_1$ \ldots $L_6$, as illustrated in Figure~\ref{fig:express}.
The pumping lemmas, namely Lemma~\ref{lemma-tPCCFL} and Lemma~\ref{lemma-PCCFL},
are sufficient to prove Theorem~\ref{thm:strict} and Theorem~\ref{thm:non-incl}(3), respectively.
On the other hand they are not sufficient for
Theorem~\ref{thm:non-incl-add}(2) and Theorem~\ref{thm:non-incl}(1)--(2),
as \malyprefix{shuffle}\CFL\ satisfies both the lemmas, and thus we have to perform a more delicate analysis of a derivation tree.
We illustrate the first kind of argument in the proof of Theorem~\ref{thm:non-incl}(3) and the second kind in the
proof of Theorem~\ref{thm:non-incl}(2) below.
\begin{figure}[h]
\begin{center}
\includegraphics[width = 72mm, height = 37mm]{exprlight4.png}
\end{center}
\caption{Relating the expressive power.}
\label{fig:express}
\end{figure}


\newcommand{\bar{a}}{\bar{a}}
\newcommand{\bar{d}}{\bar{d}}

\begin{proofof}{Theorem~\ref{thm:non-incl}(3)}
Consider the language
\begin{equation}\label{shuffle_form}
L_6 = \{w \in \bigcup_{n\geq 0} \Big( a^n \bar{a}\, \bar{d}\, d^n \, || \, b^n c^n \Big)
 : \text{every } b \text{ preceds every } d \text{ and } \bar{d} \text{ in } w \} .
\end{equation}
Clearly, $L_6$ is the trace closure of the context-free language
$
\{
(a\,b)^n \bar{a}\, \bar{d}\, (c\,d)^n 
: n\geq 0\},
$
if for the independence on alphabet letters one chooses the symmetric closure of:
\[
\{a, \bar{a}\} \times \{
b, c
\} \;\cup\; \{ \bar{d}, d \} \times \{ c \} .
\]
Using Lemma~\ref{lemma-PCCFL} we will show that
$L_6$ belongs to neither \malyprefix{pc}\CFL}  % $^\text{pc}$\ nor \malyprefix{shuffle}\CFL.
Consider a word 
\[
w_n = a^n \bar{a}\, 
b^n c^n 
\bar{d}\, d^n
\]
and recall that for $n$ larger that $N$ of Lemma~\ref{lemma-PCCFL} we would obtain
\[
w_n \in x\, (y' \, || \, z) \qquad y' \in s\, (y \, || \, t)
\]
for a substring $y'$ of $w_n$. Recall also the pumping scheme of {\sc shuffle pumping}\ from Lemma~\ref{lemma-PCCFL}:
\begin{equation} \label{eq:recall-pumping}
x s^m y t^m z \in L_6, \ \ \text{ for } m \geq 0.
\end{equation}
We do a sequence of simple observations. First, to keep the same number of appearances of letters $a, b, c$ and $d$,
each of the four letters must appear either in $s$ or $t$.
Second, both $s$ and $t$ are necessarily non-empty as otherwise we would observe an illegal order of letters in~\eqref{eq:recall-pumping}, and moreover $a$ and $b$ occur in $s$ and $c$ and $d$ occur in $t$,
keeping in mind that in $L_6$ every $a$ precedes every $d$ and every $b$ precedes every $c$ and $d$.
Third, the length of the prefix $x$ is at most $n$, as otherwise both $s$ and $t$ would appear to the right of $\bar{a}$ and thus could not contain $a$.
\slcomm{zmiana dowodu - recenzent 2}
Thus, $x$ contains only $a$. Now, $\overline{d}$ is not in $x$,
cannot be in $s$ or $t$, and cannot be in $z$ since otherwise
($s$ and) $t$ could not contain $d$. Therefore $\overline{d}$
is in $y$, and $z$ contains no $b$. As neither $x$ nor $z$
contains $b$, and $w_n\in x(y'\parallel z)$, $y'$ must contain
$n$ occurrences of $b$, but $|y'|=|syt|\leq N$, hence this is not
possible.
We have thus shown that $L_6$ does not satisfy Lemma~\ref{lemma-PCCFL} and therefore it does not belong to \malyprefix{pc}\CFL}  % $^\text{pc}$\ $\cup$ \malyprefix{shuffle}\CFL.
\end{proofof}


\begin{proofof}{Theorem~\ref{thm:non-incl-add}(2)}
Consider the language $L_3 \in $ \malyprefixpodw{tr}{pc}\CFL:
\begin{equation}\label{eq:languagel3}
L_3 = \bigcup_{n \geq 0} a^n s \, (b^n \, || \, c^n)
\end{equation}
 and a grammar that generates the language:
\[
\begin{array}{ccccccccccc}
S & \trans[a] & SP & \hspace{0.5cm} &
P & \trans[b] & C & \hspace{0.5cm} &
C & \trans[c] & \varepsilon \\
S & \trans[s] & \varepsilon & \hspace{0.5cm} &
P & \trans[c] & B & \hspace{0.5cm} &
B & \trans[b] & \varepsilon
\end{array}
\]

The initial non-terminal is $S$ and the threads are $\{S, P\}, \{B\}, \{C\}$.
$L_3$ also belongs to \malyprefix{trace}\CFL\ as it is the trace closure of the context-free language 
$\{a^n s (bc)^n : n \geq 0\}$ with independence $\{(b,c), (c,b)\}$.

It remains thus to show that $L_3 \notin$ \malyprefix{shuffle}\CFL.
Intuitively, the idea is to show that $L_3$ cannot benefit from parallel composition.

Assume that $L_3 \in $ \malyprefix{shuffle}\CFL, aiming at deducing a contradiction.
Fix a grammar that generates $L_3$. For simplicity think of the productions of the 
following form
(the first two we will call \emph{sequential}):
\[
X \trans[a] \varepsilon \qquad
X \trans[\varepsilon] Y  ;  Z \qquad
X \trans[\varepsilon] Y \, || \, Z .
\]
We will exploit the property that  $s$ divides every word in $L_3$
into two separated regions.
We partition the non-terminals into symbols that generate some word
containing $s$, and symbols that do not; and call them $s$-symbols and 
non-$s$-symbols, respectively.
By {\sc Substitutivity}, each word generated by an $s$-symbol contains necessarily $s$.

Consider a derivation tree $T$ of a word $w s v \in L_3$.
The unique path leading from the root to the leaf labeled by $s$ call
\emph{the spine}.
Observe that an $s$-symbol may only appear on the spine and
a non-$s$-symbol may only appear outside the spine.
Knowing that the number of occurrences of $a$ and $b$ on both sides of the spine
is the same, we deduce that 
\begin{align} \label{eq:spine-seq}
\text{each production labeling a node of the spine is necessarily sequential.}
\end{align}
Indeed, assume a parallel production $X \trans[\varepsilon] Y \, || \, Z$ 
labels a node of the spine. Wlog. let $Y$ be a $s$-symbol.
Let $u$, $u'$ be the subwords induced by the $Y$-node and $Z$-node, respectively.
Clearly there are two interleavings of $u$ and $u'$  such that
the letter $s$, appearing in $u$, is placed in the interleaving in two different positions in the word $u'$.
Thus at least one of these interleavings must lead to a violation of the condition~\eqref{eq:languagel3}
in a word belonging to $L_3$.
Condition~\eqref{eq:spine-seq} is thus proved.


Now consider a non-$s$-symbol $X$ appearing in $T$.
The number of occurrences $\nrof{a}{u}$ of $a$ in all words $u$ generated by $X$ is necessarily
the same, and the same applies to $\nrof{b}{u}$ and $\nrof{c}{u}$.
Indeed, otherwise one gets a similar contradiction as above by considering two words
induced by the $X$ node, differing in the number of occurrences of $a$ or $b$, and using {\sc Substitutivity}.
As a consequence $X$ generates a finite language which may clearly be
defined by a context-free grammar, say $G_X$. 

If we apply the last observation to the very first non-$s$-symbol $X$ on every path
in $T$ (except the spine), we obtain a tree without parallel nodes.
As $G_X$ does not depend on the particular derivation tree $T$ chosen, and the word $w s v \in L_3$ 
was chosen arbitrary, we conclude that $L_3$ is generated by a context-free grammar.
The grammar is obtained by replacing productions of every non-$s$-symbol $X$ in $G$ with $G_X$.
As $L$ is clearly not context-free we obtain a contradiction and thus complete the proof.
\end{proofof}


\section{Introduction}


Closure of languages classes under shuffle is intensively investigated, see for instance~\cite{BBCPR10} 
and further references therein.
This paper is about a subtle way of introducing shuffle into context-free grammars.

\smallsection{Process algebraic motivation} 
In the context of infinite-state verification there are two basic well known classes of systems.
\emph{Context-free processes}, called traditionally BPA\footnote{A shorthand for Basic Process Algebra.}~\cite{BK84}, stand for the most fundamental abstract model of sequential recursive programs.
BPA contains configuration graphs induced by context-free grammars in Grei\-bach normal form.
The commutative variant, \emph{commutative context-free processes}, traditionally called BPP\footnote{A shorthand for Basic Parallel Processes Algebra.}, was proposed in~\cite{PHDChristensen} as the abstract model of concurrent programs. 
BPP differs from BPA in that it has parallel composition instead of sequential composition. 
Thus a configuration is a finite multiset of non-terminals rather than a sequence.

A natural generalization of both BPA and BPP is \emph{Process Algebra} ({\sc pa})~\cite{BK84} where one allows for both kinds of composition.\footnote{The algebra of~\cite{BK84} includes also left merge operation, not considered in this paper.}
A standard reference for a process-rewrite formulation of PA is~\cite{Mayr00}. 
However, {\sc pa}\ does not seem to have good algorithmic properties. For instance, bisimulation equivalence is not known to be decidable, a long standing open problem~\cite{Srba02}, while the algorithm for normed PA is very complex and as costly as double exponential time~\cite{DBLP:conf/icalp/HirshfeldJ99}.
This has recently motivated investigation of an alternative but equally natural generalization of both BPA and BPP,
namely \emph{partially-commutative context-free processes}, called {\sc BPC}\footnote{A shorthand for Basic Partially Commutative Algebra.} in~\cite{CFL09}.
{\sc BPC}\ processes are also defined by a Greibach grammar, but one additionally assumes a binary 
\emph{independence relation} among non-terminals, like in trace theory~\cite{Mazurkiewicz88}, 
and only independent pairs of non-terminals commute.
We stress that the independence is imposed not on alphabet letters, which is usually the case in trace languages, but on non-terminals. Thus a configuration may be modeled as a trace over non-terminals. 
BPA is a special case where no non-terminals commute while BPP, on the other hand, is another special case where all non-terminals commute. 

In~\cite{CFL09,CFL11}  an efficient polynomial-time procedure has been developed for bisimulation equivalence, that works correctly in the subclass of normed {\sc BPC}\ that strictly contains both normed BPA and BPP.
We also very recently analyzed the reachability problem for {\sc BPC}~\cite{CHL12}.
In this paper we continue the program that aims at finding a robust class subsuming BPA and BPP,
however this time from the language-theoretic perspective.

\smallsection{Language theoretic motivation}
BPA clearly defines context-free languages ({\sc cfl}) and BPP defines so called commutative context-free languages (\malyprefix{c}\CFL}  % $^\text{c}$)~\cite{PHDChristensen}\footnote{In fact, BPA and BPP define {\sc cfl}\ and \malyprefix{c}\CFL}  % $^\text{c}$\ not containing the empty word,
respectively.}, equivalently characterized as languages of com\-mu\-ni\-ca\-tion-free Petri nets. 
In this paper we focus on \emph{partially-commutative context-free languages} (\malyprefix{pc}\CFL}  % $^\text{pc}$)~\cite{CFL11} that are defined by {\sc BPC}. Our aim is to investigate properties of this class and to relate its expressiveness with other classes.

The class \malyprefix{pc}\CFL}  % $^\text{pc}$\ extends {\sc cfl}\ and is closed under the shuffle operation.
By a shuffle of two words we mean here an arbitrary interleaving of these words and
by shuffle of two languages we mean all shuffles of all pairs of words from the two languages.
Other similar extensions of {\sc cfl}\ may be found in the literature.
One such extension is {\sc pa}\ languages. We use a shorthand \malyprefix{shuffle}\CFL\ for this class --
as far as languages are concerned, {\sc pa}\ is equivalent to context-free grammars where one allows 
to use both concatenation and shuffle in productions~\cite{Gischer81,NSS03}.
Another related class is trace-closures of {\sc cfl}\ (name this class \malyprefix{trace}\CFL), 
where one assumes, contrary to \malyprefix{pc}\CFL}  % $^\text{pc}$, an independence relation on alphabet letters. 
We have found it appealing to relate the expressive power of \malyprefix{pc}\CFL}  % $^\text{pc}$\ with \malyprefix{shuffle}\CFL\ and \malyprefix{trace}\CFL.
 
\smallsection{Our contribution}
First, we show that a relevant subclass of \malyprefix{pc}\CFL}  % $^\text{pc}$, subject to the restriction that the complement of independence relation is transitive, has a natural corresponding automaton model: stateless multi-pushdown automata (Section~\ref{sec:prelim}). We also prove that the membership problem for \malyprefix{pc}\CFL}  % $^\text{pc}$\ is NP-complete thus the complexity remains the same as for \malyprefix{c}\CFL}  % $^\text{c}$\
 (Section~\ref{sec:derivtrees}).

Second, in Section~\ref{sec:closure}  we investigate stability of \malyprefix{pc}\CFL}  % $^\text{pc}$\ under natural operations. In particular, \malyprefix{pc}\CFL}  % $^\text{pc}$\ turns out to be stable under homomorphic images, substitutions and shuffle. On the other hand, the class is not stable under inverse homomorphic images and under intersections with regular languages. The latter is not very surprising as we consider a natural extension of \malyprefix{c}\CFL}  % $^\text{c}$, 
the class that lacks not only the two closure properties, but even lacks closure under concatenation and homomorphic images! With \malyprefix{pc}\CFL}  % $^\text{pc}$\ one regains closure under concatenation and homomorphic images.

Third, in Sections~\ref{sec:plemmas} and~\ref{sec:express}  we perform mutual comparison of expressiveness of \malyprefix{pc}\CFL}  % $^\text{pc}$, transitive \malyprefix{pc}\CFL}  % $^\text{pc}$, \malyprefix{shuffle}\CFL\ and \malyprefix{trace}\CFL, proving them all pairwise incomparable (except for the trivial inclusion of transitive \malyprefix{pc}\CFL}  % $^\text{pc}$\ in \malyprefix{pc}\CFL}  % $^\text{pc}$, that we prove to be strict). 
Note that incomparability with respect to languages implies incomparability with respect to bisimulation or other equivalences.
As one of the tools we formulate and prove pumping lemmas for classes \malyprefix{pc}\CFL}  % $^\text{pc}$, transitive \malyprefix{pc}\CFL}  % $^\text{pc}$\ and \malyprefix{shuffle}\CFL.
This provides an elegant completion of known pumping properties of regular, context-free and commutative context-free languages.

Technically, the most difficult part is Sections~\ref{sec:plemmas} and~\ref{sec:express}. On the other hand,
the results of Sections~\ref{sec:prelim} and~\ref{sec:closure} confirm clearly
that \malyprefix{pc}\CFL}  % $^\text{pc}$ \ is a natural class of languages extending {\sc cfl}, with good algorithmic and closure properties.


Yet another relevant language class is that defined by so called Dynamic Pushdown Networks~\cite{BMT05}.
The class extends {\sc cfl}\ and is closed under shuffle. We do not investigate this class here,
but we conjecture that it is incomparable with \malyprefix{pc}\CFL}  % $^\text{pc}$.

Some of the proofs are omitted
due to space limitation.



\section{Other extensions of context-free languages}

There are two other language classes know from the literature that,
similarly as \malyprefix{pc}\CFL}  % $^\text{pc}$, extend {\sc cfl}\ with some amount of commutation.

\smallsection{{\sc pa}\ languages}
The formalism to be described below is traditionally called \emph{Process Algebra} ({\sc pa})~\cite{BK84,Mayr00}.
It is however nothing else than an extension of Greibach context-free grammars
with an explicit shuffle operation: a production has the form
\[
X \trans[a] t,
\]
where $t$ is an arbitrary term built from non-terminals using binary operations of sequential composition '$ ; $' and
parallel composition '$\, || \,$'. The first operation one may interpret as concatenation of languages, and the second one as shuffle (thus the overloading of the symbol $\, || \,$ is absolutely deliberate). 
The \emph{empty term} $\varepsilon$ is also allowed.

For convenience, terms are only considered up to a structural equivalence, that imposes associativity of both operations, commutativity of $\, || \,$, and neutrality of $\varepsilon$ with respect to
both operations.

A \emph{configuration} is an arbitrary term of the above form.
Steps between configurations are defined by the following rules (the last rule is in fact redundant due to commutativity of $\, || \,$, but we prefer to keep it for readability):
\[
\frac{X \trans[a] t \text{ is a production}}{X \trans[a] t}  
\qquad
\frac{t \trans[a] t'}{t  ;  u \trans[a] t'  ;  u}
\qquad
\frac{t \trans[a] t'}{t \, || \, u \trans[a] t' \, || \, u}
\qquad
\frac{u \trans[a] u'}{t \, || \, u \trans[a] t \, || \, u'}
\]
As usual, a derivation is a sequence of configurations starting from a distinguished initial configuration $S$, ending in the
empty configuration, such that every subsequent configuration is obtained from a preceding one by a single step.
Other notions, including the language generated by a grammar, or derivation trees, may be defined similarly as for \malyprefix{pc}\CFL}  % $^\text{pc}$.
The class of languages we denote by \malyprefix{shuffle}\CFL.

In particular, \malyprefix{shuffle}\CFL\ satisfy the three properties mentioned above: {\sc Induced subword}, {\sc  Infix rearrangement}\ and {\sc Substitutivity}.

The difference between \malyprefix{pc}\CFL}  % $^\text{pc}$\ and \malyprefix{shuffle}\CFL\ is, roughly, a difference between
specifying commutation explicitly in productions, or implicitly by an independence relation.


\smallsection{Trace-closures of {\sc cfl}}
To define \malyprefix{trace}\CFL\ we need to assume that an independence
relation ranges not over non-terminals but over alphabet letters instead.
As usual, one defines \emph{trace equivalence} over words:
two words are equivalent if one may be transformed into another by swaps of neighboring independent letters.
A context-free language $L$ is not closed under this equivalence in general and  its \emph{trace closure}
\[
\{w : w \text{ is trace equivalent to some }  v \in L \}
\]
is in general not context-free. By \malyprefix{trace}\CFL\ we denote the class containing trace closures of context-free languages. 
Clearly \malyprefix{trace}\CFL\ is a superclass of {\sc cfl}.


\section{Pumping lemmas}\label{sec:plemmas}

Now we analyze how much the classical idea of pumping extends from {\sc cfl}\ to larger classes.
Roughly speaking, the intuitive cutting and pasting in a derivation tree does not 
translate to the property of a language as easily as in the case of {\sc cfl}.

We formulate two different pumping lemmas. 
Remarkably, with one of them we complete nicely the picture of pumping lemmas known 
for regular, context-free and commutative context-free languages.

As expected, the pumping lemmas appear to be useful tool for relating the expressive power of language classes, as we demonstrate in Section~\ref{sec:express}.



\smallsection{The pumping lemmas}
The length of a word $w$ is written $\len{w}$. To motivate our conditions we start by recalling the 
pumping scheme proposed for \malyprefix{c}\CFL}  % $^\text{c}$\ 
by~\cite{PHDChristensen}.

\begin{quote}
({\sc \malyprefix{c}\CFL}  % $^\text{c}$-pumping}~\cite{PHDChristensen})\ \ 
\emph{There is a constant $N$ such that if $w\in L$ with $\len{w} > N$ then there exist words $x, y, s$ such that
\begin{enumerate}
\item $w \in x\, (s \, || \, y)$,
\item $1 \leq \len{s} \leq N$, and
\item $\forall m\geq 0$,  $x\, s^m y \in L$.\footnote{In fact in~\cite{PHDChristensen}, 
the pumping scheme was $x\, s^m y'$, with a suffix $y'$ of $w$ (think of $y' \in s \, || \, y$), rather than  $x\, s^m y$. The proofs of both are very similar. 
We discuss this issue further in Remark~\ref{rem:pumpscheme}.}
\end{enumerate}
}
\end{quote}

\noindent
Point 1 reads as: $w$ is a concatenation of some prefix $x$ and an interleaving of $s$ and $y$.
We define now two new conditions on a language $L$.  

\begin{quote}
({\sc shuffle pumping})\ \ 
\emph{There is a constant $N$ such that if $w\in L$ with $\len{w} > N$ then there exist words $x, y, z, s, t$ such that
\begin{enumerate}
\item $w \in x\, ((s\, (y \, || \, t)) \, || \, z)$,
\item $1 \leq \len{s}, \len{s\, y\, t} \leq N$, and
\item $\forall m\geq 0$,  $x\, s^m y\, t^m z \in L$.
\end{enumerate}
}
\end{quote}
Point 1 reads as: there is some subword $y'$ of $w$ with $w \in x\, (y' \, || \, z)$ and $y' \in s\, (y \, || \, t)$.
\begin{quote}
({\sc concat. pumping})\ \ 
\emph{There is a constant $N$ such that if $w\in L$ with $\len{w} > N$ then there exist words $x, y, z, s, t$ such that
\begin{enumerate}
\item $w = x\, y\, z$,
\item $1 \leq \len{s\, t} \leq N$, and
\item $\forall m\geq 0$,  $x\, s^m y\, t^m z \in L$.
\end{enumerate}
}
\end{quote}
Call the words $s$, $t$ \emph{repeatable words}.
The difference between the two conditions concentrates on the word $y$ that separates the repeatable words in 
$x\, s^m y\, t^m z$.
On one hand {\sc shuffle pumping}\ seems weaker as $y$ is no more an infix of $w$, but an arbitrary subword (subsequence). 
On the other hand {\sc shuffle pumping}\ seems stronger as the length of $y$ is bounded.


\begin{lemma}\label{lemma-PCCFL}
Every language $L \in$ \malyprefix{pc}\CFL}  % $^\text{pc}$\ $\cup$ \malyprefix{shuffle}\CFL\ satisfies {\sc shuffle pumping}.
\end{lemma}
As an example of application we provide now a proof missing in Section~\ref{sec:closure}.

\begin{proofof}{Lemma~\ref{anbncn}}
Assume towards contradiction that $L=\{a^n b^n c^n: n\geq 1\}$ is in \malyprefix{pc}\CFL}  % $^\text{pc}$\ or in \malyprefix{shuffle}\CFL\ and 
apply Lemma~\ref{lemma-PCCFL}.
Observe that the two repeatable words $s$ and $t$ have necessarily jointly the same number of letters $a$, $b$ and $c$.
Thus one of them has to contains two different letters. Repeating this word twice leads to a contradiction.
\end{proofof}
\begin{lemma}\label{lemma-tPCCFL}
Every language $L \in$ \malyprefixpodw{tr}{pc}\CFL\ $\cup$ \malyprefix{shuffle}\CFL\ satisfies {\sc concat. pumping}.
\end{lemma}
Class \malyprefix{pc}\CFL}  % $^\text{pc}$\ does not satisfy {\sc concat. pumping}, as witnessed by the language from Example~\ref{ex:nottransitive}.
Moreover in {\sc concat. pumping}\ one can not bound the length of the word $y$.  


\smallsection{Relating conditions}
The condition {\sc shuffle pumping}\ is similar to the classical context-free pumping --
the only difference is the words $s$, $y$, $t$ and $z$ are subwords, not necessarily infixes, of $w$.
We claim it is an elegant completion of the pumping lemmas for 
regular languages (RL), context-free languages ({\sc cfl}) and commutative context-free languages (\malyprefix{c}\CFL}  % $^\text{c}$) (see~\cite{PHDChristensen}). 
All of these lemmas may be characterized by the following two characteristics:
\begin{enumerate}
\item Are there one or two pumping positions?
\item Are repeatable words infixes or subwords a given word?
\end{enumerate}
The known pumping lemmas have the following characteristics:
\begin{itemize}
\item RL: 1 pumping position, a repeatable word is an infix
\item {\sc cfl}: 2 pumping positions, repeatable words are infixes
\item \malyprefix{c}\CFL}  % $^\text{c}$: 1 pumping position, a repeatable word is a subword~\cite{PHDChristensen}.
\end{itemize}
In this light, our condition {\sc shuffle pumping}\ offers an elegant completion of the picture: 2 pumping positions, repeatable words are subwords.
In other words, {\sc shuffle pumping}\ weakens \malyprefix{c}\CFL}  % $^\text{c}$-pumping in the same way as {\sc cfl}-pumping weakens RL-pumping (2 pumping positions instead of one).
The other way around: {\sc shuffle pumping}\ weakens {\sc cfl}-pumping in the same way as \malyprefix{c}\CFL}  % $^\text{c}$-pumping weakens RL-pumping (repeatable word is no more an infix). The relationships between the four pumping conditions is depicted in the following diagram:
\[
\xymatrix @C-4pc{
& \ar@{--}[rrrddd] & \text{{\sc shuffle pumping}} &\ar@{--}[lllddd] & \\
\ar@{--}[rrdd] &  \text{\ \ \ \ \ \ \ {\sc cfl}-pumping\ \ } \ar@{=>}[ru] && \text{\ \ \malyprefix{c}\CFL}  % $^\text{c}$-pumping\ \ \ } \ar@{=>}[lu] & \ar@{--}[lldd] \\
\txt{two pumping\\positions} && \text{RL-pumping} \ar@{=>}[ru] \ar@{=>}[lu] && \txt{repeatable subword} \\
&\txt{\ \ one pumping\\ \ position} && \txt{repeatable infix} &
} 
\]


\begin{remark} \label{rem:pumpscheme}
It is worth mentioning that another pumping scheme could be used in place of {\sc shuffle pumping}\ in Lemma~\ref{lemma-PCCFL}: instead of
$
x\, s^m y\, t^m z,
$
one may consider
\[
x\, s^m y'\, t^m z,
\]
with $w \in x\, (y' \, || \, z)$ and $y' \in (s\, (y \, || \, t))$.
The proof would be very similar.
\end{remark}


\section{Preliminaries}\label{sec:prelim}

By an \emph{interleaving} of two words $w$ and $v$, of length $m$ and $n$, respectively,
 we mean any word $u$ of length $m+n$ such that its positions $I = \{1, \ldots, m+n\}$ may be
split into two disjoint sets $I_w$ and $I_v$ such that $u$ restricted to $I_w$ equals $w$
and $u$ restricted to $I_v$ equals $v$. Let $w \, || \, v$ denote the set of all the interleavings
of $w$ and $v$, which is clearly a finite set.
By a shuffle of two languages $L$ and $K$ we mean
\[
L \, || \, K  =  \bigcup_{w \in L, v \in K} w \, || \, v .
\]


\smallsection{Partially-commutative context-free languages}
\label{sec:pccfl}
The class of languages to be defined below has been introduced in~\cite{CFL11}, 
however our presentation and terminology here is different.

A Greibach context-free grammar consists of a finite alphabet, a finite set of non-terminal symbols $V$ with a distinguished initial symbol $S\in V$ and a finite set of productions of the form
\begin{equation}
\label{eq:gnf-rule}
X \trans[a] \alpha,
\end{equation}
where $X \in V$, $\alpha \in V^*$ and $a$ is an alphabet letter. Additionally we assume that a grammar is always equipped with a symmetric and irreflexive 
relation $I\subseteq V\times V$ called the \emph{independence relation}.
For convenience we also use the complement $D = (V\times V) \setminus I$, called the \emph{dependence relation}.
Two non-terminals $X, Y\in V$ are called \emph{independent} if $(X,Y)\in I$, and otherwise \emph{dependent}.

Any $\alpha \in V^*$ we call a \emph{configuration}.
A \emph{derivation} is a sequence of configurations 
such that every configuration is obtained from the preceding one via a \emph{step} and the last one is the empty configuration. There are two kinds of steps:
\begin{itemize} 
\item \emph{production step}: $X \beta \trans[a] \alpha \beta$, for a production $X \trans[a] \alpha$;
\item \emph{swap step}: $\alpha X Y \beta \trans \alpha Y X \beta$, where $X$ and $Y$ are independent.
\end{itemize}
Every derivation \emph{defines} a word $w$ obtained by concatenation of alphabet letters occurring in the production steps.
We write $\alpha \trans[w] \beta$ if there is a derivation that defines $w$, starts in $\alpha$ and ends in $\beta$.
We usually assume that a derivation starts with a configuration consisting of a single non-terminal, say $X$.
If $X \trans[w] \varepsilon$ then we say that $X$ \emph{generates} $w$.
Note that the length of $w$ is the same as the number of production steps performed in any derivation that defines $w$. We assume wlog.~that every non-terminal $X$ generates some word.

The language generated by a grammar is the set of all words generated by the initial non-terminal.
The class of all so generated languages we call 
\emph{partially-commutative context-free languages} (\malyprefix{pc}\CFL}  % $^\text{pc}$)~\cite{CFL11}.
It clearly contains all context-free languages ({\sc cfl}) and commutative 
context-free languages\footnote{The commutative context-free languages are also called \emph{BPP languages}.} (\malyprefix{c}\CFL}  % $^\text{c}$)~\cite{PHDChristensen}. 
These two subclasses are special cases, where independence is either the identity, or the full relation, respectively.

\begin{myexample}\label{ex:nottransitive}
For illustration, consider the grammar:
\[
\begin{array}{cclccclccclcccl}
P & \trans[a] & W B C \bar{B} &\hspace{0.5cm}& 
W & \trans[a] & W B C   &\hspace{0.5cm}& 
\bar{B} & \trans[\bar{b}] & \varepsilon &\hspace{0.5cm}& B & \trans[b] & \varepsilon \\
&&&& 
W & \trans[\bar{a}] & \bar{C} &&       
\bar{C} & \trans[\bar{c}] & \varepsilon && C & \trans[c] & \varepsilon 
\end{array}
\]

The initial non-terminal is $P$ and the independence relation is the symmetric closure of $\{B, \bar{B}\} \times \{C, \bar{C}\}$.
Here is an example derivation of the word $a \bar{a} b \bar{b} \bar{c} c$.
\[
\begin{array}{rcccccccccc}
P & \trans[a] & W B C \bar{B} & \trans[\bar{a}] &
\bar{C} B C \bar{B} & \trans &
\bar{C} B \bar{B} C  & \trans &
B \bar{C} \bar{B} C  & \trans \\
&& B \bar{B}  \bar{C} C &   
\trans[b] & \bar{B} \bar{C} C & \trans[\bar{b}] & \bar{C} C & \trans[\bar{c}] & C & \trans[c] & \varepsilon 
\end{array}
\]
In a similar way a word $a^n \bar{a} b^n \bar{b} \bar{c} c^n$ is generated, for any $n \geq 1$, 
but also $a^n \bar{a} \bar{c} c^n b^n \bar{b}$ or $a^n \bar{a} \bar{c} b^n c^n \bar{b}$.
The language generated is
\[
\bigcup_{n \geq 1} a^n \bar{a} \, (b^n \bar{b} \, || \, \bar{c} c^n).
\]
\end{myexample}

We might have defined configurations as Ma\-zur\-kie\-wicz traces~\cite{Mazurkiewicz88} rather than words over non-terminals
(like in~\cite{CFL11}).
This would mean that \emph{trace equivalent} configurations are not distinguished. 
In our terminology, two configurations are trace equivalent when one may be transformed into another using solely swap steps.
It is our deliberate choice to keep the swap steps explicit.

\removed{
\smallsection{Silent productions}
In the above definitions one could allow for \emph{silent production}, i.e., with $a = \varepsilon$.
Clearly, the resulting class \malyprefix{pc}\CFL}  % $^\text{pc}$$_{\varepsilon}$ is strictly larger, 
as languages in \malyprefix{pc}\CFL}  % $^\text{pc}$\ never contain the empty word $\varepsilon$.
We claim that the extension would be non-trivial:
\begin{proposition}\label{p:epsPCCFL}
\malyprefix{pc}\CFL}  % $^\text{pc}$$_{\varepsilon}$ $\setminus$ \malyprefix{pc}\CFL}  % $^\text{pc}$\ contains a language $L$ with $\varepsilon \notin L$.
\end{proposition}
Having said that, we claim that most of our results remain valid if silent productions are allowed.
In this paper we do not consider silent productions for simplicity.
}



\smallsection{Transitive dependence}
We distinguish a subclass of \malyprefix{pc}\CFL}  % $^\text{pc}$\ where dependence is assumed to be transitive, being thus an equivalence. 
This subclass we name \malyprefixpodw{tr}{pc}\CFL.
Equivalence classes of dependence will be called \emph{{thread}s}. 

In Example~\ref{ex:nottransitive} the dependence is not transitive, as it contains $(P,B)$ and $(P,C)$ but not $(B,C)$.
In fact we show later that this language does not belong to \malyprefixpodw{tr}{pc}\CFL.
Both {\sc cfl}\ and \malyprefix{c}\CFL}  % $^\text{c}$\ are strict subclasses of \malyprefixpodw{tr}{pc}\CFL.

\begin{myexample}\label{ex:transitive}
As an illustration, consider the language generated by:
\[
\begin{array}{ccccccccccccccc}
S & \trans[s] & \varepsilon &\hspace{0.5cm}& 
S & \trans[a] & S A  &\hspace{0.5cm}& 
A & \trans[c] & A' &\hspace{0.5cm}& 
A' & \trans[a] & \varepsilon \\
&&&&       
S & \trans[b] & S B  && 
B & \trans[c] & B' && 
B' & \trans[b] & \varepsilon 
\end{array}
\]

with initial non-terminal $S$ and the {thread}s $\{S, A, B\}$, $\{A'\}$ and $\{B'\}$.
Here is an example derivation  of the word $absccab$.
\[
S\trans[a] S A \trans[b] S B A \trans[s] B A \trans[c] B' A \trans A B'
\trans[c] A' B' \trans[a] B' \trans[b] \varepsilon.
\]
The language contains words of the form $w s v$, 
where $w$ contains only $a$ and $b$ and $v$ contains only $a$, $b$ and $c$.
Writing $\nrof{a}{w}$ for the number of occurrences of $a$ in $w$ and $|w|$ for the length of $w$,
we may characterize the language by the following conditions:
\begin{itemize}
\item $\nrof{a}{w} = \nrof{a}{v}$, $\nrof{b}{w} = \nrof{b}{v}$ and $\nrof{c}{v} = \nrof{a}{v} + \nrof{b}{v}$,
\item any prefix $v'$ of $v$ and any suffix $w'$ of $w$ such that $\nrof{c}{v'} = |w'|$ fulfills
\[
    \nrof{a}{w'} \geq \nrof{a}{v'} \qquad \text{and} \qquad
    \nrof{b}{w'} \geq \nrof{b}{v'}.
\]
\end{itemize}
\end{myexample}


\smallsection{Automaton model}
A multi-pushdown automaton is like a single-pushdown one.
In a single step one symbol is popped from one of the stacks,\footnote{If we allowed for popping from more than one stack at a time,
the model would clearly become Turing-complete, even with only one state.} and a number of symbols are
pushed on the stacks. 
The number of stacks is fixed for an automaton.
Assume there is only one state, or equivalently no state, and $k$ stacks.
Then a transition of an automaton is of the form:
\begin{equation} \label{eq:mpdatran}
X \trans[a] \a_1 \ldots \a_k,
\end{equation}
to mean that when an automaton reads $a$, it pops $X$ and pushes the sequence of symbols $\a_i$ on the $i$th stack,
 for $i = 1 \ldots k$. Observe that wlog. one may assume that stack alphabets are disjoint. The following result is an easy observation:
\begin{theorem}[\cite{CHL12}]
The \malyprefixpodw{tr}{pc}\CFL\ class is expressively equivalent to stateless multi-push\-down automata.
\end{theorem}
Indeed, an equivalence class of configurations with respect to trace equivalence is represented
by a tuple of strings, one per thread. Similarly, a production $X \trans[a] \alpha$ is represented, up to swap steps, 
exactly as in~\eqref{eq:mpdatran}, with $\a_i$ being the projection of $\a$ on the $i$th thread.

Similarly, one could also define an operational model for general \malyprefix{pc}\CFL}  % $^\text{pc}$, with a stack replaced by a partially ordered structure.

\section{Derivation trees} \label{sec:derivtrees}

It is very convenient to use derivation trees instead of derivations themselves.
However it is not completely obvious how to define this notion in presence of commutativity of non-terminals.
Below we adopt an intuitive approach using colors.

Fix a derivation $X \trans[w] \varepsilon$.
Clearly a configuration is a sequence of \emph{non-terminal occurrences}.
We assume that every non-terminal occurrence in a derivation will be colored, including the occurrence of $X$ in the initial configuration.
We impose the following simple discipline of coloring:
\begin{itemize}
  \item if a swap step $\alpha X Y \beta \trans \alpha Y X \beta$ is performed, every non-terminal occurrence in the right-hand 
  side configuration
  inherits its color from the corresponding occurrence of the same non-terminal on the left-hand side.
  \item if a production step $X \beta \trans[a] \alpha \beta$ is performed, the non-terminal occurrences in $\beta$ preserve 
  their colors, while all the non-terminals occurrences in $\alpha$ get fresh colors. Note that the color of the occurrence of $X$ 
  in the beginning of $X \beta$ disappears as a result of the step. We say that this disappearing color \emph{drops} the fresh colors. 
\end{itemize}
Intuitively, a color is intended to represent the 'life cycle' of one occurrence of a non-terminal during a derivation.
Observe that non-terminal occurrences in a given configuration are always labeled with different colors, and that the total
number of colors used in a derivation equals the number of production steps.

\begin{myexample}
A disciplined coloring of the derivation from Example~\ref{ex:transitive} is shown below.
Colors are $1, 2, \ldots$ and the coloring is denoted by subscripts. 
\begin{equation} \label{eq:deriv}
S_1\trans[a] S_2 A_3 \trans[b] S_4 B_5 A_3 \trans[s] B_5 A_3 \trans[c] B'_6 A_3 \trans A_3 B'_6
\trans[c] A'_7 B'_6 \trans[a] B'_6 \trans[b] \varepsilon.
\end{equation}


Color $1$ drops colors $2$ and $3$, color $3$ drops color $7$, etc.
\end{myexample}

With the use of our coloring discipline, every derivation induces naturally a tree.
The tree nodes are all colors appearing in the derivation. The color $c_1$ is a parent of $c_2$ precisely if $c_1$ drops $c_2$.
Every tree node $c$ is labeled by a non-terminal. If convenient, one may think that
every node is labeled by a production that made color $c$ disappear.

There may be many different derivations inducing the same tree.
Even worse, two derivations \emph{of different words} may induce the same tree, as shown in the example below.

\begin{myexample} \label{ex:derivtree}
Continuing the last example, the derivation~\eqref{eq:deriv} induces the following tree:
\begin{center}
\begin{tikzpicture}[inner sep=3pt, level distance=1cm, sibling distance=5cm]
  \node at (0,0) {$1 : {S \trans[a] S A}$}
  child[sibling distance=3cm] {node {$2 : {S \trans[b] S B}$}
    child {node{$4 : {S \trans[s] \varepsilon}$}}
    child {node{$5 : {B \trans[c] B'}$}
      child {node{$6 : {B' \trans[b] \varepsilon}$}}}}
  child {node {$3 : {A \trans[c] A'}$}
    child {node {$7 : {A' \trans[a] \varepsilon}$}}};
\end{tikzpicture}
\end{center}
However, exactly the same tree is induced by the derivation:
\[
S_1 \trans[a] S_2 A_3 \trans[b] S_4 B_5 A_3 \trans[s] B_5 A_3 \trans[c] B'_6 A_3 \trans[b] A_3 \trans[c] A'_7 \trans[a] \varepsilon
\]
of a different word $abscbca \neq absccab$. Intuitively, the words defined by subtrees rooted in $3$ and $6$, namely $c a$ and $b$ respectively, this time come in a different order. In fact all the interleavings of these two words are allowed.
\end{myexample}

\newcommand{{\sc Induced subword}}{{\sc Induced subword}}
\newcommand{{\sc  Infix rearrangement}}{{\sc  Infix rearrangement}}
\newcommand{{\sc Substitutivity}}{{\sc Substitutivity}}
\smallsection{Useful properties}
The examples confirm that our notion of derivation tree is more complex than the classical one.
However, trees may be still very useful for reasoning about partially-commutative context-free languages,
as they immediately bring to light the following useful properties:
\vskip 1mm
\noindent{{\sc Induced subword}.}
Given a derivation tree of a word $w$, every node $c$ induces a subword 
(i.e. a subsequence but not an infix in general) of $w$.
Indeed, the subword is obtained by concatenating only those letters from $w$
whose color, as a tree node, belongs to the subtree rooted in $c$.
We implicitly assign here to the letter of every production step a color that disappears in this step.
For instance, for both words considered in the last example, the subword induced by the node $2$ is $bscb$.
Analogously one defines the subword induced by a subset of nodes of a derivation tree, assuming this subset
 to be an antichain with respect to the tree ancestor relation.
\vskip 1mm
\noindent{{\sc  Infix rearrangement}.}
The induced subword may be rearranged into an infix. Let $L \in $ \malyprefix{pc}\CFL}  % $^\text{pc}$\ and
let $v$ be the subword of $w \in L$ induced by a tree node $c$.
Clearly, $w \in v \, || \, u$,
i.e., $v$ is interleaved with the remaining subword $u$ of $w$.
Then $u$ may be split into $u = u_1 u_2$ so that $u_1 v \, u_2 \in L$. 
Indeed, let $u_1$ be the prefix of $w$ preceding the first letter of $v$.
In any derivation, after $u_1$, the non-terminal that labels $c$ is clearly active.
Performing the whole derivation $X \trans[v] \varepsilon$ immediately after $u_1$ does the job.
\vskip 1mm
\noindent{{\sc Substitutivity}.}
In any derivation tree, one may replace a subtree rooted in a node $c$ 
by an arbitrary derivation tree $t$, 
assumed that both $c$ and the root of $t$ are labeled with the same non-terminal. The resulting tree is 
clearly induced by some derivation too.



\smallsection{Membership problem}
A derivation tree is of linear size in terms of the length of the word, which is useful for easily obtaining 
the upper bound for the membership problem, where
given a word $w$ and a presentation of a language $L$, one asks if $w \in L$?
\begin{theorem}
The membership problem is NP-complete both for \malyprefix{pc}\CFL}  % $^\text{pc}$\ and \malyprefixpodw{tr}{pc}\CFL.
\end{theorem}
NP-hardness follows easily from NP-hardness of the membership problem for
\malyprefix{c}\CFL}  % $^\text{c}$, shown in~\cite{DBLP:journals/fuin/Esparza97}. The NP upper bound
one obtains easily: guess a tree and the order of its nodes, and then check in polynomial time
whether the tree is induced by some derivation of the given word that respects the order of nodes.


