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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.