On a compact encoding of the swap automaton

Abstract

Given a string $P$ of length $m$ over an alphabet $\Sigma$ of size $\sigma$, a swapped version of $P$ is a string derived from $P$ by a series of local swaps, i.e., swaps of adjacent symbols, such that each symbol can participate in at most one swap. We present a theoretical analysis of the nondeterministic finite automaton for the language ${\bigcup }_{P^{\prime }\in {\Pi }_P}{\Sigma }^{\ast }{P}^{\prime }$ (swap automaton for short), where ${\Pi }_P$ is the set of swapped versions of $P$. Our study is based on the bit-parallel simulation of the same automaton due to Fredriksson, and reveals an interesting combinatorial property that links the automaton to the one for the language ${\Sigma }^{\ast }P$. By exploiting this property and the method presented by Cantone et al. (2010), we obtain a bit-parallel encoding of the swap automaton which takes $O(σ^2\ceil{k/w})$ space and allows one to simulate the automaton on a string of length $n$ in time $O(n\ceil{k/w})$, where $\ceil{m/σ}\le k\le m$.