Decomposing regular languages under shuffle along trajectories

Sungmin Kim, Hyunki Hong, Taeryung Lim, Yo-Sub Han and Kai Salomaa.
To be presented at CIAA'26.

Definitions

Shuffle along trajectories: the shuffle of two languages $L_1$ and $L_2$ over $\Sigma$ along a trajectory language $T$ over {$0,1$} is the language obtained by interleaving strings $w_1\in L_1$ and $w_2\in L_2$ by placing characters from $w_1$ and $w_2$ respectively at positions designated by $0$’s and $1$’s in trajectories $t\in T$.
Decomposition under shuffle along trajectories: given a regular language $R$ and a trajectory language $T$, compute two languages $L_1$ and $L_2$ whose shuffle along $T$ equals $R$.

Summary of results

• Algorithms for computing the decompositions for two well-known trajectory languages:
  • $(01)^*+(10)^*$ (perfect shuffle)
  • $(01)^*(\lambda+0+00)$ (2-comet shuffle)
• A decomposition technique using Büchi automata, where the language of the automaton is non-empty iff there exists a non-trivial decomposition of $R$
• Corollary: with respect to either trajectory, if there exists a non-trivial decomposition of $R$, then there exists a decomposition where both languages are regular.

Keywords shuffle along trajectories, language decomposition, Büchi automata, control string