Constructing $k$-ary Orientable Sequences with Asymptotically Optimal Length
<|reference_start|>Constructing $k$-ary Orientable Sequences with Asymptotically Optimal Length: An orientable sequence of order $n$ over an alphabet $\{0,1,\ldots, k{-}1\}$ is a cyclic sequence such that each length-$n$ substring appears at most once \emph{in either direction}. When $k= 2$, efficient algorithms are known to construct binary orientable sequences, with asymptotically optimal length, by applying the classic cycle-joining technique. The key to the construction is the definition of a parent rule to construct a cycle-joining tree of asymmetric bracelets. Unfortunately, the parent rule does not generalize to larger alphabets. Furthermore, unlike the binary case, a cycle-joining tree does not immediately lead to a simple successor-rule when $k \geq 3$ unless the tree has certain properties. In this paper, we derive a parent rule to derive a cycle-joining tree of $k$-ary asymmetric bracelets. This leads to a successor rule that constructs asymptotically optimal $k$-ary orientable sequences in $O(n)$ time per symbol using $O(n)$ space. In the special case when $n=2$, we provide a simple construction of $k$-ary orientable sequences of maximal length.<|reference_end|>
@article{gabrić2024constructing,
    title={Constructing $k$-ary Orientable Sequences with Asymptotically Optimal
  Length},
    author={Daniel Gabri'c and Joe Sawada},
    journal={arXiv preprint arXiv:2407.07029},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.07029},
    primaryClass={cs.DM cs.IT math.CO math.IT}
}