Let $X$ be a finite alphabet. Given two words $u, v \in X^{\ast}$ the shuffle operator is defined to be $$ u || v := \{ u_1 v_1 u_2 v_2 \ldots u_n v_n : 1 \le i \le n, u_i, v_i \in X^{\ast}, u = u_1 \ldots u_n, v = v_1 \ldots v_n \} $$ i.e. it is the set of all "interlaced" strings (notice its signature $X^{\ast}\times X^{\ast}\to 2^{X^{\ast}}$). For example $$ ab || c = \{ cab, acb, abc \}. $$ There is also an inductive definition \begin{align*} \varepsilon || u & = u || \varepsilon = \{u\} \\ au || bv & = a(u || bv) \cup b(au || v). \end{align*} This operator could be extended to languages. Now, for a language $L \subseteq X^{\ast}$ denote by $\mbox{perm}(L)$ the set of all permutations of words from $L$, for example $\mbox{perm}(\{ abc \}) = \{ abc, bac, acb, cba, cab, bca \}$. Now we have the inductive definition for $x \in X$ and $u \in X^{\ast}$ \begin{align*} \mbox{perm}(\varepsilon) & = \{\varepsilon\} \\ \mbox{perm}(xu) & = x || \mbox{perm}(u). \end{align*} which defines it for words, and then extended to languages. Now instead of all permutations, just consider the rotations, or the cyclic permutations, i.e. for $u \in X^{\ast}$ $$ \mbox{cycle}(L) := \{ vu : uv \in L\}. $$ For example $\mbox{cycle}(\{abc\}) = \{abc, bca, cab\}$. And similar the rotations and reflections, where if we define $\mbox{reverse}(u) = u_n \ldots u_1$ for $u = u_1 \ldots u_n$ with $u_i \in X$, then for $L \subset X^{\ast}$ the smallest set, called $\mbox{di}(L)$ such that $$ u \in \mbox{di}(L) \Rightarrow \mbox{cycle}(\{u\})\subseteq \mbox{di}(L), \quad\mbox{and}\quad\mbox{reverse}(u) \in \mbox{di}(L). $$ For example $\mbox{di}(\{abcd\}) = \{abcd, bcda, cdab, dabc, cbad, dcba, adcb, badc \}$. Now do the $\mbox{cycle}$-operator and the $\mbox{di}$-operator admit a similar inductive definition in terms of some composition of words, i.e. exists there some composition such that we can define them inductively like $\mbox{perm}$?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.