On a compact encoding of the swap automaton

Kimmo Fredriksson, Emanuele Giaquinta

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…