| Version current |
Version 1 |
| Let $\Sigma$ be an alphabet and $u$ a word over $\Sigma$. Write $u$ as a product of symbols in $\Sigma$: |
Let $\Sigma$ be an alphabet and $u$ a word over $\Sigma$. Write $u$ as a product of symbols in $\Sigma$: |
| $$u=a_1 \cdots a_n$$ |
$$u=a_1 \cdots a_n$$ |
| where $a_i \in \Sigma$. A \PMlinkescapetext{\emph{permutation}} of $u$ is a word of the form $$a_{\pi(1)} \cdots a_{\pi(n)},$$ |
where $a_i \in \Sigma$. A \PMlinkescapetext{\emph{permutation}} of $u$ is a word of the form $$a_{\pi(1)} \cdots a_{\pi(n)},$$ |
| where $\pi$ is a permutation on $\lbrace 1,\ldots, n\rbrace$. The set of all permutations of $u$ is denoted by $\operatorname{com}(u)$. If $\Sigma =\lbrace b_1,\ldots, b_m\rbrace$, it is easy to see that $\operatorname{com}(u)$ has $$\frac{n!}{n_1! \cdots n_m!}$$ elements, where $n_i=|u|_{b_i}$, the number of occurrences of $b_i$ in $u$. |
where $\pi$ is a permutation on $\lbrace 1,\ldots, n\rbrace$. The set of all permutations of $u$ is denoted by $$\operatorname{com}(u).$$ Define a binary relation $\sim$ on $\Sigma^*$ by: $u\sim v$ if $v$ is a permutation of $u$. Then $\sim$ is a congruence relation on $\Sigma^*$ with respect to concatenation. In fact, $\Sigma^*/\sim$ is a commutative monoid. |
|
|
| Define a binary relation $\sim$ on $\Sigma^*$ by: $u\sim v$ if $v$ is a permutation of $u$. Then $\sim$ is a congruence relation on $\Sigma^*$ with respect to concatenation. In fact, $\Sigma^*/\sim$ is a commutative monoid. |
|
|
|
| A language $L$ over $\Sigma$ is said to be \emph{commutative} if for every $u\in L$, we have $\operatorname{com}(u) \subseteq L$. Two equivalent characterization of a commutative language $L$ are: |
A language $L$ over $\Sigma$ is said to be \emph{commutative} if for every $u\in L$, we have $\operatorname{com}(u) \subseteq L$. Two equivalent characterization of a commutative language $L$ are: |
| \begin{itemize} |
\begin{itemize} |
|
\item If $u=vxyw \in L$, then $vyxw \in L$.
|
\item If $u=vabw \in L$, then $vbaw \in L$.
|
|
\item $\Psi^{-1}\circ \Psi(L)\subseteq L$, where $\Psi$ is the Parikh mapping over $\Sigma$ (under some ordering).
|
\item $\Psi^{-1}\circ \Psi(L)\subseteq L$, where $\Psi$ is the Parikh mapping over $\Sigma$ |
| \end{itemize} |
\end{itemize} |
|
|
| The first equivalence comes from the fact that if $vyxw$ is just a permutation of $vxyw$, and that every permutation on $\lbrace 1,\ldots, n\rbrace$ may be expressed as a product of transpositions. The second equivalence is the realization of the fact that $\operatorname{com}(u)$ is just the set $$\lbrace v\mid |v|_a = |u|_a, a\in \Sigma \rbrace.$$ |
More to come... |
|
|
| We have just seen some examples of commutative closed langauges, such as $\operatorname{com}(u)$ for any word $u$, and $\Psi^{-1}\circ \Psi(L)$, for any language $L$. |
|
|
|
| Given a language $L$, the smallest commutative language containing $L$ is called the \emph{commutative closure} of $L$. It is not hard to see that $\Psi^{-1}\circ \Psi(L)$ is the \emph{commutative closure} of $L$. |
|
|
|
| For example, if $L=\lbrace (abc)^n \mid n\ge 0\rbrace$, then $\Psi^{-1}\circ \Psi(L) = \lbrace w\mid |w|_a=|w|_b = |w|_c\rbrace$. |
|
|
|
| \textbf{Remark}. The above example illustrates the fact that the families of regular languages and context-free languages are not closed under commutative closures. However, it can be shown that the families of context-sensitive languages and type-0 languages are closed under commutative closures. |
|
|
|
| \begin{thebibliography}{9} |
|
| \bibitem{mi} M. Ito, {\em Algebraic Theory of Automata and Languages}, World Scientific, Singapore (2004). |
|
| \end{thebibliography} |
|
