commutative language
Let $\mathrm{\Sigma}$ be an alphabet and $u$ a word over $\mathrm{\Sigma}$. Write $u$ as a product^{} of symbols in $\mathrm{\Sigma}$:
$$u={a}_{1}\mathrm{\cdots}{a}_{n}$$ 
where ${a}_{i}\in \mathrm{\Sigma}$. A of $u$ is a word of the form
$${a}_{\pi (1)}\mathrm{\cdots}{a}_{\pi (n)},$$ 
where $\pi $ is a permutation^{} on $\{1,\mathrm{\dots},n\}$. The set of all permutations of $u$ is denoted by $\mathrm{com}(u)$. If $\mathrm{\Sigma}=\{{b}_{1},\mathrm{\dots},{b}_{m}\}$, it is easy to see that $\mathrm{com}(u)$ has
$$\frac{n!}{{n}_{1}!\mathrm{\cdots}{n}_{m}!}$$ 
elements, where ${n}_{i}={u}_{{b}_{i}}$, the number of occurrences of ${b}_{i}$ in $u$.
Define a binary relation^{} $\sim $ on ${\mathrm{\Sigma}}^{*}$ by: $u\sim v$ if $v$ is a permutation of $u$. Then $\sim $ is a congruence relation^{} on ${\mathrm{\Sigma}}^{*}$ with respect to concatenation^{}. In fact, ${\mathrm{\Sigma}}^{*}/\sim $ is a commutative monoid.
A language^{} $L$ over $\mathrm{\Sigma}$ is said to be commutative^{} if for every $u\in L$, we have $\mathrm{com}(u)\subseteq L$. Two equivalent^{} characterization of a commutative language $L$ are:

•
If $u=vxyw\in L$, then $vyxw\in L$.

•
${\mathrm{\Psi}}^{1}\circ \mathrm{\Psi}(L)\subseteq L$, where $\mathrm{\Psi}$ is the Parikh mapping over $\mathrm{\Sigma}$ (under some ordering).
The first equivalence comes from the fact that if $vyxw$ is just a permutation of $vxyw$, and that every permutation on $\{1,\mathrm{\dots},n\}$ may be expressed as a product of transpositions^{}. The second equivalence is the realization of the fact that $\mathrm{com}(u)$ is just the set
$$\{v\mid {v}_{a}={u}_{a},a\in \mathrm{\Sigma}\}.$$ 
We have just seen some examples of commutative closed langauges, such as $\mathrm{com}(u)$ for any word $u$, and ${\mathrm{\Psi}}^{1}\circ \mathrm{\Psi}(L)$, for any language $L$.
Given a language $L$, the smallest commutative language containing $L$ is called the commutative closure of $L$. It is not hard to see that ${\mathrm{\Psi}}^{1}\circ \mathrm{\Psi}(L)$ is the commutative closure of $L$.
For example, if $L=\{{(abc)}^{n}\mid n\ge 0\}$, then ${\mathrm{\Psi}}^{1}\circ \mathrm{\Psi}(L)=\{w\mid {w}_{a}={w}_{b}={w}_{c}\}$.
Remark. The above example illustrates the fact that the families of regular languages and contextfree languages are not closed under^{} commutative closures. However, it can be shown that the families of contextsensitive languages and type0 languages are closed under commutative closures.
References
 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
Title  commutative language 

Canonical name  CommutativeLanguage 
Date of creation  20130322 18:56:56 
Last modified on  20130322 18:56:56 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  5 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q70 
Defines  commutative 
Defines  commutative closure 