1 Introduction↩︎

Orientable sequences were introduced by Burns and Mitchell [1] and studied by Dai, Martin, Robshaw, and Wild [2] with applications related to robotic position sensing. In particular, consider an autonomous robot with limited sensors. To determine its location on a cyclic track labeled with black and white squares, the robot scans a window of \(n\) squares directly beneath it. For the position and orientation to be uniquely determined, the track must be designed with the property that each length \(n\) window can appear at most once in either direction. A cyclic binary sequence (track) with such a property is called an orientable sequence of order \(n\) (an \(\mathcal{OS}(n)\)). By this definition, an orientable sequence does not contain a length-\(n\) substring that is a palindrome.

Orientable sequences do not exist for \(n=1\), and somewhat surprisingly, the maximum length \(M_n\) of an \(\mathcal{OS}(n)\) is known only for \(1 < n \leq 7\). Since the number of palindromes of length \(n\) is \(2^{\lfloor (n+1)/2\rfloor}\), a trivial upper bound on \(M_n\) is \((2^n - 2^{\lfloor (n+1)/2\rfloor})/2= 2^{n-1} - 2^{\lfloor(n-1)/2\rfloor}\).

In addition to providing a tighter upper bound, Dai, Martin, Robshaw, and Wild [2] provide a lower bound \(L_n\) on \(M_n\) by demonstrating the existence of \(\mathcal{OS}(n)\)s via cycle-joining with length \(L_n\) asymptotic to their upper bound. They conclude by stating the following open problem relating to orientable sequences whose lengths (periods) attain the lower bound. See Section 2.1 for the explicit upper and lower bounds.

We note that the lower bound on the maximum period was obtained using an existence construction …  It is an open problem whether a more practical procedure exists for the construction of orientable sequences that have this asymptotically optimal period.

Recently, some progress was made in this direction by Mitchell and Wild [3]. They apply Lempel’s lift [4] to obtain an \(\mathcal{OS}(n)\) recursively from an \(\mathcal{OS}(n{-}1)\). This construction can generate orientable sequences in \(O(1)\)-amortized time per bit; however, it requires exponential space, and there is an exponential time delay before the first bit can be output. Furthermore, they state that their work “only partially answers the question, since the periods/lengths of the sequences produced are not asymptotically optimal.”

Outline. ¹ In Section 2, we present necessary background definitions and notation, a review of the lower bound \(L_n\) and upper bound \(U_n\) from [2], and a review of the cycle-joining technique. In Section 3, we provide a parent rule for constructing a cycle-joining tree composed of “reverse-disjoint” cycles corresponding to asymmetric bracelets. This leads to our \(O(n)\) time per bit construction of orientable sequences of length \(L_n\). In Section 4, we present properties of the periodic nodes in our cycle-joining tree and in Section 5, we provide an algorithm for determining the children of a given node. In Section 6, we convert our cycle-joining trees to concatenation trees, which leads to a construction requiring \(O(1\))-amortized time per bit. In Section 7 we discuss the algorithmic techniques used to extend our constructed orientable sequences to find longer ones for \(n\leq 20\). Then in Section 8, we apply similar techniques to find some longest known acyclic orientable sequences for \(n\leq 20\). We conclude in Section 9 with a summary of our results and directions for future research. Implementations of our algorithms are available for download at http://debruijnsequence.org/db/orientable.

1.1 Related work↩︎

Recall the problem of determining a robot’s position and orientation on a track. Suppose now that we allow the track to be non-cyclic. That is, the beginning of the track and the end of the track are not connected. Then the corresponding sequence that allows one to determine orientation and position is called an acyclic orientable sequence. One does not consider the substrings in the wraparound for this variation of an orientable sequence. Note that one can always construct an acyclic \(\mathcal{OS}(n)\) from a cyclic \(\mathcal{OS}(n)\) by taking the cyclic \(\mathcal{OS}(n)\) and appending its prefix of length \(n{-}1\) to the end. See the paper by Burns and Mitchell [1] for more on acyclic orientable sequences, which they call aperiodic \(2\)-orientable window sequences. Alhakim et al. [7] generalize the recursive results of Mitchell and Wild [3] to construct orientable sequences over alphabets of size two or greater; they also generalize the upper bound, by Dai et al. [2], on the length of an orientable sequence. Rampersad and Shallit [8] showed that for every alphabet of size two or greater, there is an infinite sequence such that for every sufficiently long substring, the reversal of the substring does not appear in the sequence. Fleischer and Shallit [9] later reproved the results of the previous paper using theorem-proving software. See [10], [11] for more work on sequences avoiding reversals of substrings.

2 Preliminaries↩︎

Let \(\mathbf{B}(n)\) denote the set of all length-\(n\) binary strings. Let \(\alpha = \mathtt{a}_1\mathtt{a}_2\cdots \mathtt{a}_n \in \mathbf{B}(n)\) and \(\beta = \mathtt{b}_1\mathtt{b}_2\cdots \mathtt{b}_m \in \mathbf{B}(m)\) for some \(m,n\geq 0\). Throughout this paper, we assume \(0<1\) and use lexicographic order when comparing two binary strings. More specifically, we say that \(\alpha < \beta\) either if \(\alpha\) is a prefix of \(\beta\) or if \(\mathtt{a}_i < \mathtt{b}_i\) for the smallest \(i\) such that \(\mathtt{a}_i \neq \mathtt{b}_i\). We say that \(\alpha\) is a rotation of \(\beta\) if \(m=n\) and there exist strings \(x\) and \(y\) such that \(\alpha = xy\) and \(\beta = yx\). The weight (density) of a binary string is the number of \(1\)s in the string. Let \(\overline{\mathtt{a}}_i\) denote the complement of bit \(\mathtt{a}_i\). Let \(\alpha^R\) denote the reversal \(\mathtt{a}_n\cdots \mathtt{a}_2\mathtt{a}_1\) of \(\alpha\); \(\alpha\) is a palindrome if \(\alpha = \alpha^R\). For \(j\geq 1\), let \(\alpha^j\) denote \(j\) copies of \(\alpha\) concatenated together. If \(\alpha = \gamma^j\) for some non-empty string \(\gamma\) and some \(j > 1\), then \(\alpha\) is said to be periodic²; otherwise, \(\alpha\) is said to be aperiodic (or primitive). Let \(\mathop{\mathrm{ap}}(\alpha)\) denote the shortest string \(\gamma\) such that \(\alpha = \gamma^t\) for some positive integer \(t\); we say \(\gamma\) is the aperiodic prefix of \(\alpha\). Observe that \(\alpha\) is aperiodic if and only if \(\mathop{\mathrm{ap}}(\alpha) = \alpha\).

A necklace class is an equivalence class of strings under rotation. Let \([\alpha]\) denote the set of strings in \(\alpha\)’s necklace class. We say \(\alpha\) is a necklace if it is the lexicographically smallest string in \([\alpha]\). Let \(\tilde{\alpha}\) denote the necklace in \([\alpha]\). Let \(\mathbf{N}(n)\) denote the set of length-\(n\) necklaces. A bracelet class is an equivalence class of strings under rotation and reversal; let \(\langle \alpha \rangle\) denote the set of strings in \(\alpha\)’s bracelet class. Thus, \(\langle \alpha \rangle = [\alpha] \cup [\alpha^R]\). We say \(\alpha\) is a bracelet if it is the lexicographically smallest string in \(\langle \alpha \rangle\). Note that in general, a bracelet is always a necklace, but a necklace need not be a bracelet. For example, the string \(001011\) is both a bracelet and a necklace, but the string \(001101\) is a necklace not a bracelet. A necklace \(\alpha\) is symmetric if it belongs to the same necklace class as \(\alpha^R\), i.e., both \(\alpha\) and \(\alpha^R\) belong to \([\alpha]\). By this definition, a symmetric necklace is necessarily a bracelet. If a necklace or bracelet is not symmetric, it is said to be asymmetric. Let \(\mathbf{A}(n)\) denote the set of all asymmetric bracelets of length \(n\). Table ¿tbl:tab:neck? lists all \(60\) necklaces of length \(n=9\) partitioned into asymmetric necklace pairs and symmetric necklaces. The asymmetric necklace pairs belong to the same bracelet class, and the first string in each pair is an asymmetric bracelet. Thus, \(|\mathbf{A}(9)| = 14\). In general, \(|\mathbf{A}(n)|\) is equal to the number of necklaces of length \(n\) minus the number of bracelets of length \(n\); for \(n=6, 7, \ldots 15\), this sequence of values \(|\mathbf{A}(n)|\) is given by \(1\), \(2\), \(6\), \(14\), \(30\), \(62\), \(128\), \(252\), \(495\), \(968\) and it corresponds to sequence A059076 in The On-Line Encyclopedia of Integer Sequences [12]. Asymmetric bracelets have been studied previously in the context of efficiently ranking/unranking bracelets [13].

Lemma 2 is considered a folklore result in combinatorics on words; see Theorem 4 in [15] for a variant of the lemma. We provide a short proof for the interested reader.

2.1 Bounds on \(M_n\)↩︎

Dai, Martin, Robshaw, and Wild [2] gave a lower bound \(L_n\) and an upper bound \(U_n\) on the maximum length \(M_n\) of an \(\mathcal{OS}(n)\).³ The lower bound \(L_n\) corresponds to the length of the sequence that results from joining all asymmetric necklaces in a specific way. Their lower bound \(L_n\) is the following, where \(\mu\) is the Möbius function: \[\label{eqn:L} L_n =\sum_{\alpha \in \mathbf{A}(n)}|\mathop{\mathrm{ap}}(\alpha)| = \left( 2^{n-1} - \frac{1}{2} \sum_{d | n} \mu(n/d) \frac{n}{d} H(d) \right), \;\;\text{ where } \;\;H(d) = \frac{1}{2} \sum\limits_{i | d} i \left( 2^{\lfloor \frac{i+1}{2} \rfloor} + 2^{\lfloor \frac{i}{2} \rfloor +1} \right).\tag{1}\]

Their upper bound \(U_n\) is the following:\(^{\ref{note1}}\)

These bounds are calculated in Table ¿tbl:table:bounds? for \(n\) up to 20. This table also illustrates the length \(R_n\) of the \(\mathcal{OS}(n)\) produced by the recursive construction by Mitchell and Wild [3], starting from an initial orientable sequence of length 80 for \(n=8\). The column labeled \(L^*_n\) indicates the longest known orientable sequences we discovered by applying a combination of techniques (discussed in Section 7) to our orientable sequences of length \(L_n\).

2.2 Cycle joining↩︎

Given \(\mathbf{S}\subseteq \mathbf{B}(n)\), a universal cycle \(U\) for \(\mathbf{S}\) is a cyclic sequence of length \(|\mathbf{S}|\) that contains each string in \(\mathbf{S}\) as a substring (exactly once). Thus, an orientable sequence is a universal cycle. If \(\mathbf{S}= \mathbf{B}(n)\) then \(U\) is known as a de Bruijn sequence. Given a universal cycle \(U\) for \(\mathbf{S}\), a successor rule for \(U\) is a function \(f:\mathbf{S}\rightarrow \{0,1\}\) such that \(f(\alpha)\) is the bit following \(\alpha\) in \(U\).

Cycle-joining is perhaps the most fundamental technique applied to construct universal cycles. For instance, see [2]. If \(\mathbf{S}\) is closed under rotation, then it can be partitioned into necklace classes (cycles); each cycle is disjoint. Let \(\alpha = \mathtt{a}_1\mathtt{a}_2\cdots \mathtt{a}_n\) and \(\hat{\alpha} = \mathtt{\overline{a}}_1\mathtt{a}_2\cdots \mathtt{a}_n\); we say \((\alpha, \hat{\alpha})\) is a conjugate pair. Two disjoint cycles can be joined if they each contain one string of a conjugate pair as a substring. This approach resembles pioneering algorithm of Hierholzer (1873) to construct an Euler cycle in an Eulerian graph.

A cycle-joining tree is a tree with nodes representing disjoint universal cycles; an edge between two nodes implies they each contain one string of a conjugate pair. If \(\mathbf{S}\) is the set of all length-\(n\) strings belonging to the disjoint cycles of a cycle-joining tree, then the tree defines a universal \(U\) for \(\mathbf{S}\) along with a corresponding successor rule; see Section 3 for an example. For most universal cycle constructions, a corresponding cycle-joining tree can be defined by a rather simple parent rule. For example, when \(\mathbf{S}= \mathbf{B}(n)\), the following are perhaps the simplest parent rules that define how to construct cycle-joining trees with nodes corresponding to necklace cycles represented by \(\mathbf{N}(n)\) [5], [16], [17].

• Last-\(0\): rooted at \(1^n\) and the parent of every other node \(\alpha \in \mathbf{N}(n)\) is obtained by flipping the last \(0\).

• First-\(1\): rooted at \(0^n\) and the parent of every other node \(\alpha \in \mathbf{N}(n)\) is obtained by flipping the first \(1\).

• Last-\(1\): rooted at \(0^n\) and the parent of every other node \(\alpha \in \mathbf{N}(n)\) is obtained by flipping the last \(1\).

• First-\(0\): rooted at \(1^n\) and the parent of every other node \(\alpha \in \mathbf{N}(n)\) is obtained by flipping the first \(0\).

These rules induce the cycle-joining trees \(\mathrm{T}_1\), \(\mathrm{T}_2\), \(\mathrm{T}_3\), \(\mathrm{T}_4\) illustrated in Figure 1 for \(n=6\). Note that for \(\mathrm{T}_3\) and \(\mathrm{T}_4\), the parent of a node \(\alpha\) is obtained by first flipping the highlighted bit and then rotating the string to its lexicographically least rotation to obtain a necklace. Each node \(\alpha\) and its parent \(\beta\) are joined by a conjugate pair, where the highlighted bit in \(\alpha\) is the first bit in one of the conjugates. For example, the nodes \(\alpha = 0{\boldsymbol{\textcolor{red}}{1}}1011\) and \(\beta = 001011\) in \(\mathrm{T}_2\) from Figure 1 are joined by the conjugate pair \(({\boldsymbol{\textcolor{red}}{1}}10110, 010110)\).

3 An efficient cycle-joining construction of orientable sequences↩︎

Consider the set of asymmetric bracelets \(\mathbf{A}(n) = \{\alpha_1, \alpha_2, \ldots, \alpha_t\}\). Recall, that each symmetric bracelet is a necklace. Let \(\mathbf{S}(n) = [\alpha_1] \cup [\alpha_2] \cup \cdots \cup [ \alpha_t ]\). From [2], we have \(|\mathbf{S}(n)| = L_n\). By definition, there is no string \(\alpha \in \mathbf{S}(n)\) such that \(\alpha^R \in \mathbf{S}(n)\). Thus, a universal cycle for \(\mathbf{S}(n)\) is an \(\mathcal{OS}(n)\). To construct a cycle-joining tree with nodes \(\mathbf{A}(n)\), we apply a combination of three of the four simple parent rules described in the previous section. First, we demonstrate that there is no such parent rule using at most two rules in combination. Assume \(n \geq 8\). Observe that none of the necklaces in \(\mathbf{A}(n)\) have weight \(0\), \(1\), \(2\), \(n{-}2\), \(n{-}1\), or, \(n\). Thus, \(0^{n-4}1011\) and \(0^{n-5}10011\) are both necklaces in \(\mathbf{A}(n)\) with minimal weight three. Similarly, \(00101^{n-4}\) and \(001101^{n-5}\) are necklaces in \(\mathbf{A}(n)\) with maximal weight \(n{-}3\). Therefore, when considering a parent rule for a cycle-joining tree with nodes \(\mathbf{A}(n)\), the rule must be able to flip a \(0\) to a \(1\), or a \(1\) to a \(0\), i.e., if the rule applies a combination of the four rules from Section 2.2, it must include one of First-\(0\) or Last-\(0\), and one of First-\(1\) and Last-\(1\).

Let \(\alpha = \mathtt{a}_1\mathtt{a}_2\cdots \mathtt{a}_n\) denote a necklace in \(\mathbf{A}(n)\); it must begin with \(0\) and end with \(1\). Then let

• \(\mathop{\mathrm{first1}}(\alpha)\) be the necklace \(\mathtt{a}_1\cdots\mathtt{a}_{i-1}{\boldsymbol{\textcolor{blue}}{0}}\mathtt{a}_{i+1}\cdots \mathtt{a}_n\), where \(i\) is the index of the first \(1\) in \(\alpha\);

• \(\mathop{\mathrm{last1}}(\alpha)\) be the necklace of \([\mathtt{a}_1\mathtt{a}_2 \cdots \mathtt{a}_{n-1}{\boldsymbol{\textcolor{blue}}{0}}]\);

• \(\mathop{\mathrm{first0}}(\alpha)\) be the necklace of \([{\boldsymbol{\textcolor{red}}{1}}\mathtt{a}_2 \cdots \mathtt{a}_{n}]\);

• \(\mathop{\mathrm{last0}}(\alpha)\) be the necklace \(\mathtt{a}_1\cdots\mathtt{a}_{j-1}{\boldsymbol{\textcolor{red}}{1}}\mathtt{a}_{j+1}\cdots \mathtt{a}_n\), where \(j\) is the index of the last \(0\) in \(\alpha\).

Note that \(\mathop{\mathrm{first1}}(\alpha)\) and \(\mathop{\mathrm{last0}}(\alpha)\) are necklaces (easily observed by definition) obtained by flipping the \(i\)-th and \(j\)-th bit in \(\alpha\), respectively; \(\mathop{\mathrm{last1}}(\alpha)\) and \(\mathop{\mathrm{first0}}(\alpha)\) are the result of flipping a bit and rotating the resulting string to obtain a necklace. The following remark follows from the definition of necklace.

Proposition [prop:2rules] illustrates that for \(n\) sufficiently large, no two of the above four parent rules can be applied in combination to obtain a cycle-joining tree with nodes \(\mathbf{A}(n)\).

For \(n \geq 6\), we choose the lexicographically smallest length-\(n\) asymmetric bracelet \(\mathit{r}_n=0^{n-4}1011\) to be the root of our cycle-joining tree.

Let \(\mathbb{T}_n\) denote the cycle-joining tree with nodes \(\mathbf{A}(n)\) induced by the parent rule in (2 ); Figure 2 illustrates \(\mathbb{T}_9\). The proof of Theorem 1 relies on the following lemma.

Proof of Theorem 1. Let \(\alpha\) be an asymmetric bracelet in \(\mathbf{A}(n) \setminus \{\mathit{r}_n\}\). We can write \(\alpha\) as \(0^i1\beta\) for some string \(\beta\) and \(i \geq 1\). We demonstrate that the parent rule \(\mathop{\mathrm{par}}\) from (2 ) induces a path from \(\alpha\) to \(\mathit{r}_n\), i.e., there exists an integer \(j\) such that \(\mathop{\mathrm{par}}^j(\alpha) = \mathit{r}_n\). Note that \(\mathit{r}_n\) is the unique asymmetric bracelet with prefix \(0^{n-4}\). By Lemma 3, \(\mathop{\mathrm{par}}(\alpha) \in \mathbf{A}(n)\). In the first two cases of the parent rule, \(\mathop{\mathrm{par}}(\alpha)\) will have prefix \(0^{i+1}\). If the third case applies, Lemma 3 states that \(\mathop{\mathrm{last1}}( \mathop{\mathrm{last0}}(\alpha))\) is an asymmetric bracelet. Thus, \(\mathop{\mathrm{par}}(\mathop{\mathrm{par}}(\alpha))\) is either \(\mathop{\mathrm{first1}}( \mathop{\mathrm{last0}}(\alpha))\) or \(\mathop{\mathrm{last1}}( \mathop{\mathrm{last0}}(\alpha))\); in each case the resulting asymmetric bracelet has prefix \(0^{i+1}\). Since either \(\mathop{\mathrm{par}}(\alpha)\) or \(\mathop{\mathrm{par}}(\mathop{\mathrm{par}}(\alpha))\) has prefix \(0^{i+1}\), the parent rule induces a path from \(\alpha\) to \(\mathit{r}_n\) and the height of the resulting tree is at most \(2(n-4)-1\).

3.1 A successor rule↩︎

Each application of the parent rule \(\mathop{\mathrm{par}}(\alpha)\) in (2 ) corresponds to a conjugate pair. For instance, consider the asymmetric bracelet \(\alpha = 00010111{\boldsymbol{\textcolor{blue}}{1}}\). The parent of \(\alpha\) is obtained by flipping the last \(1\) to obtain \(00010111{\boldsymbol{\textcolor{blue}}{0}}\) (see Figure 2). The corresponding conjugate pair is \(({\boldsymbol{\textcolor{blue}}{1}}00010111, {\boldsymbol{\textcolor{blue}}{0}}00010111)\). Let \(\mathbf{C}(n)\) denote the set of all strings belonging to a conjugate pair in the cycle-joining tree \(\mathbb{T}_n\). Then the following is a successor rule for an \(\mathcal{OS}(n)\), given \(\alpha = \mathtt{a}_1\mathtt{a}_2\cdots \mathtt{a}_n \in \mathbf{S}(n)\): \[f(\alpha) = \left\{ \begin{array}{ll} \overline{\mathtt{a}}_1 & \;\;if \mathtt{a}_1\mathtt{a}_2\cdots \mathtt{a}_n \in \mathbf{C}(n);\\ {\mathtt{a}_1} \; &\;\; otherwise.\end{array} \right.\] For example, if \(\mathbf{C}(9)\) corresponds to the conjugate pairs to create the cycle-joining tree \(\mathbb{T}_9\) shown in Figure 2, then the corresponding universal cycle is:

where the two underlined strings belong to the conjugate pair \(({\boldsymbol{\textcolor{blue}}{1}}00010111, {\boldsymbol{\textcolor{blue}}{0}}00010111)\). In general, this rule requires exponential space to store the set \(\mathbf{C}(n)\). However, in some cases, it is possible to test whether a string is in \(\mathbf{C}(n)\) without pre-computing and storing \(\mathbf{C}(n)\). In our successor rule for an \(\mathcal{OS}(n)\), we use Lemma 1 to avoid pre-computing and storing \(\mathbf{C}(n)\), thereby reducing the space requirement from exponential in \(n\) to linear in \(n\).

Starting with any string in \(\alpha \in \mathbf{S}(n)\), we can repeatedly apply \(g(\alpha)\) to obtain the next bit in a universal cycle for \(\mathbf{S}(n)\).

4 Periodic nodes in \(\mathbb{T}_n\)↩︎

In this section, we present several results on periodic nodes in \(\mathbb{T}_n\), assuming \(n \geq 6\).

From equation 1 , we immediately have the following corollary.

5 Computing the children of a node in \(\mathbb{T}_n\)↩︎

In this section, we present an optimized way to determine the children of a node \(\beta = \mathtt{b}_1\mathtt{b}_2\cdots \mathtt{b}_n\) in \(\mathbb{T}_n\). We use this optimization in Section 6 to generate orientable sequences in \(O(1)\)-amortized time per bit.
Let \(s\) and \(t\) be integers such that \(\beta\) has prefix \(0^s1\) and suffix \(10^{t}1\). Let \(s'\) denote the largest integer such that \(0^{s'}\) is a substring of \(\mathtt{b}_{s+1}\cdots \mathtt{b}_n\). Let \(\beta_k\) denote \(\mathtt{b}_1\cdots \mathtt{b}_{k-1}\overline{\mathtt{b}}_k\mathtt{b}_{k+1}\cdots \mathtt{b}_n\); it differs from \(\beta\) only at index \(k\). Recall that \(\tilde{\beta_k}\) is the necklace in \([\beta_k]\). Let denote the maximum of the integers \(x\) and \(y\). Our goal is to determine the indices \(k\) such that \(\tilde{\beta_k}\) is in \(\mathbf{A}(n)\) and \(\mathop{\mathrm{par}}(\tilde{\beta_k}) = \beta\). Consider the three cases of the parent rule \(\mathop{\mathrm{par}}\):

• Suppose \(\mathop{\mathrm{par}}(\tilde{\beta_k}) = \mathop{\mathrm{first1}}(\tilde{\beta_k}) = \beta\). Since \(\beta\) and \(\beta_k\) differ only at index \(k\), it must be that \(k\) is the index of the first \(1\) in \(\beta_k\). Thus \(\tilde{\beta_k} = \beta_k\) has prefix \(0^{k-1}1\) and \(k \leq s\). Since \(\beta_k\) is a necklace, \(k >\) . Suppose \(+ 1 < k < s\) and \(\beta_k\) is not in \(\mathbf{A}(n)\). Note that \(\beta_k\) is a necklace since it has a unique substring \(0^{k-1}\) as a prefix. Thus, it must be that \(1\mathtt{b}_{k+1}\cdots \mathtt{b}_n \geq (1\mathtt{b}_{k+1}\cdots \mathtt{b}_n)^R\). Since \(k+1 \leq s\), this implies that \(1\mathtt{b}_{k+2}\cdots \mathtt{b}_n \geq (1\mathtt{b}_{k+2}\cdots \mathtt{b}_n)^R\) and hence \(\beta_{k+1}\) is also not in \(\mathbf{A}(n)\). Thus, starting from index \(k=\) \(+ 1\) (which may or may not lead to a child), and incrementing up to \(s\), we can stop testing once an index \(k >\) \(+ 1\) does not lead to a child.

• Suppose \(\mathop{\mathrm{par}}(\tilde{\beta_k}) = \mathop{\mathrm{last1}}(\tilde{\beta_k}) = \beta\). It follows from Remark [rem:lastone] that \(\tilde{\beta_k} = \mathtt{b}_{k+1}\cdots \mathtt{b}_n0^{k-1}1\). Since \(\tilde{\beta_k}\) is a necklace, it must be that \(k \leq \lceil{s/2}\rceil\). If \(k\) is the smallest index in \(1, 2, \ldots , \lceil s/2 \rceil -1\) such that \(\mathtt{b}_{k+1}\cdots \mathtt{b}_n0^{k-1}1\) is not in \(\mathbf{A}(n)\), then by applying the definition of an asymmetric bracelet, it is straightforward to verify that \(\mathtt{b}_{k+2}\cdots \mathtt{b}_n0^{k}1\) is also not in \(\mathbf{A}(n)\). Thus, starting from index \(k=1\) and incrementing, we can stop testing indices \(k\) for this case once \(\mathtt{b}_{k+1}\cdots \mathtt{b}_n0^{k-1}1\) is not in \(\mathbf{A}(n)\).

• Suppose \(\mathop{\mathrm{par}}(\tilde{\beta_k}) = \mathop{\mathrm{last0}}(\tilde{\beta_k}) = \beta\). Then it must be that \(k=n-1\) or \(k=n-2\) from Lemma 3.

Based on this analysis, the function defined in Algorithm 3 will return \(\mathtt{c}_1\mathtt{c}_2\cdots \mathtt{c}_n\) such that \(\mathtt{c}_k = 1\) if and only if \(\tilde{\beta_k}\) is a child of \(\beta\).

6 Concatenation trees and RCL order↩︎

In this section, we present an algorithm based on the recent theory of concatenation trees [5]. It generates the orientable sequences constructed in the previous section in \(O(1)\)-amortized time per bit using \(O(n^2)\) space.

A bifurcated ordered tree is a rooted tree where each node contains two ordered lists of children, the left-children and right-children, respectively. The concatenation tree \(\mathcal{T}_n\) is a bifurcated ordered tree derived from \(\mathbb{T}_n\) that keeps the same parent-child structure, while the label of each node may change from \(\alpha\) to another string in its necklace class \([\alpha]\), and the children are partitioned into to ordered left-children and right-children. The label of each non-root node becomes the string in its necklace class that differs from the label of its parent in exactly one position that we call the change index. The label and change index are unique since periodic nodes appear only at the leaves (see Lemma 4). The root is labeled \(\mathit{r}_n\) (the same label as the root of \(\mathbb{T}_n\)) and assigned change index \(n\). If a node has change index \(c\), its left-children are the children with change index less than \(c\), and the right-children are the children with change index greater than \(c\). In both cases, the children are ordered from smallest to largest based on their change index. As an example, the concatenation tree \(\mathcal{T}_9\) in Figure 4 is obtained from the cycle-joining tree \(\mathbb{T}_9\) illustrated in Figure 2.

A right-current-left (RCL) traversal of \(\mathcal{T}_n\) starts at the root and recursively visits the right-children from first to last, followed by the current node, followed by recursively visiting the left-children from first to last. Let \(\mathop{\mathrm{RCL}}(\mathcal{T}_n)\) denote the sequence generated by traversing \(\mathcal{T}_n\) in RCL order, outputting the aperiodic prefix \(\mathop{\mathrm{ap}}(\alpha)\) as each node \(\alpha\) is visited. The order the nodes of \(\mathcal{T}_9\) are visited by an RCL traversal is illustrated in Figure 4; the corresponding sequence \(\mathop{\mathrm{RCL}}(\mathcal{T}_9)\) is an \(\mathcal{OS}(9)\) of length \(L_9=126\):

In this example, each node \(\alpha\) is aperiodic and hence \(\mathop{\mathrm{ap}}(\alpha) = \alpha\), but this is not always the case.

The following theorem follows directly from the main result in [5], recalling the successor-rule \(g\) defined in Section 3.1.

To avoid the exponential space required to store a concatenation tree, we demonstrate how to efficiently determine the children of a given node \(\alpha=\mathtt{a}_1\mathtt{a}_2\cdots \mathtt{a}_n\) in \(\mathcal{T}_n\). In particular, given an index \(k\), we want to determine whether or not \(\alpha_k = \mathtt{a}_1\cdots \mathtt{a}_{k-1}\overline{\mathtt{a}}_k\mathtt{a}_{k+1}\cdots \mathtt{a}_n\) is a child of \(\alpha\). From Lemma 4, if \(\alpha\) is periodic, it has no children. Otherwise, \(\tilde{\alpha} = \mathtt{a}_s\cdots \mathtt{a}_n\mathtt{a}_1\cdots \mathtt{a}_{s-1}\) is a node in \(\mathbb{T}_n\) for some \(1\leq s \leq n\); it is the necklace of \([\alpha]\). Thus, if \(\mathtt{c}_1\mathtt{c}_2\cdots \mathtt{c}_n =\) (see Section 5), \(\mathtt{d}_1\mathtt{d}_2\cdots \mathtt{d}_n = \mathtt{c}_s\cdots \mathtt{c}_n\mathtt{c}_1\cdots \mathtt{c}_{s-1}\) is a sequence such that \(\mathtt{d}_k = 1\) if and only if \(\alpha_k\) is a child of \(\alpha\) in \(\mathcal{T}_n\). The procedure , shown in Algorithm 5, applies this observation to generate \(\mathop{\mathrm{RCL}}(\mathcal{T}_n)\) when initialized with \(\alpha = \mathit{r}_n\) and \(c=n\).

Since \(\mathcal{T}_6\) consists only of the root \(r_6 = 001011\), the output of is simply \(001011\).

7 Extending orientable sequences↩︎

The values from the column labeled \(L^*_n\) in Table ¿tbl:table:bounds? were found by extending an \(\mathcal{OS}(n)\) of length \(L_n\) constructed in the previous section. Given an \(\mathcal{OS}(n)\), \(\mathtt{o}_1\cdots \mathtt{o}_m\), the following approaches were applied to find longer \(\mathcal{OS}(n)\)s for \(n\leq 20\):

1. For each index \(i\), apply a standard backtracking search to see whether \(\mathtt{o}_{i}\cdots \mathtt{o}_m\mathtt{o}_1\cdots \mathtt{o}_{i-1}\) can be extended to a longer \(\mathcal{OS}(n)\). We followed several heuristics: (a) find a maximal length extension for a given \(i\), and then attempt to extend starting from index \(i+1\); (b) find a maximal length extension over all \(i\), then repeat; (c) find the “first” possible extension for a given \(i\), and then repeat for the next index \(i+1\). In each case, we repeat until no extension can be found for any starting index. This approach was fairly successful for even \(n\), but found shorter extensions for \(n\) odd. Steps (a) and (b) were only applied to \(n\) up to \(14\) before the depth of search became infeasible.

2. Refine the search in the previous step so the resulting \(\mathcal{OS}(n)\) of length \(m'\) has an odd number of \(1\)s and at most one substring \(0^{n-4}\). Then we can apply the recursive construction by Mitchell and Wild [3] to generate an \(\mathcal{OS}(n+1)\) with length \(2m'\) or \(2m'+1\). Then, starting from the sequences generated by recursion, we again apply the exhaustive search to find minor extensions (the depth of recursion is significantly reduced). This approach found significantly longer extensions to obtain \(\mathcal{OS}(n+1)\)s when \(n+1\) is odd.

8 Acyclic orientable sequences↩︎

Let \(\mathcal{AOS}(n)\) denote an acyclic orientable sequence of order \(n\). If \(\mathtt{o}_1\mathtt{o}_2\cdots \mathtt{o}_m\) is an \(\mathcal{OS}(n)\), then it follows from our definitions that \(\mathtt{o}_1\cdots \mathtt{o}_m\mathtt{o}_1\cdots \mathtt{o}_{n-1}\) is an \(\mathcal{AOS}(n)\). As noted in [1], none of the \(2^{\lfloor (n+1)/2 \rfloor}\) binary palindromes of length \(n\) can appear as a substring in any \(\mathcal{AOS}(n)\). Thus, a straightforward upper bound on the length of any \(\mathcal{AOS}(n)\) is \[\hat{U}_n = \frac{1}{2}(2^{n} - 2^{\lfloor (n+1)/2 \rfloor}) + (n-1)~~~~\cite{BM}.\]

By applying our cycle-joining based construction, we can efficiently construct an \(\mathcal{AOS}(n)\) of length \(L_n + (n{-}1)\). Previously, the only construction of \(\mathcal{AOS}(n)\)s recursively applied Lempel’s lift [3], requiring exponential space. Starting with an \(\mathcal{OS}(n)\) found by extending a constructed sequence of length \(L_n\) (see Section 7), we apply a computer search to extend the \(\mathcal{OS}(n)\) to an \(\mathcal{AOS}(n)\) by considering each \(\mathtt{o}_{i}\cdots \mathtt{o}_m\mathtt{o}_1\cdots \mathtt{o}_{i-1}\) and attempting to extend in each direction. This approach produced the longest known \(\mathcal{AOS}(n)\)s for \(n=12,13,14\), improving on the lengths discovered by Burns and Mitchell [1] from applying a computer search. The original data from [1] was for \(n \leq 16\); we extend the list of longest known \(\mathcal{AOS}(n)\)s up to \(n=20\).⁴ These results are summarized in Table 1.

9 Conclusion↩︎

In this paper we presented two algorithms to construct orientable sequences with asymptotically optimal length. The first algorithm is a successor rule that outputs each bit in \(O(n)\) time using \(O(n)\) space; the second algorithm generates the same sequences in \(O(1)\)-amortized time per bit using \(O(n^2)\) space by applying a recent concatenation-tree framework [5]. This answers a long-standing open question by Dai, Martin, Robshaw, and Wild [2]. We conclude with the following directions for future research:

1. Can the lower bound of \(L_n\) for \(\mathcal{OS}(n)\)s be improved?

2. Can small strings be inserted systematically into our constructed \(\mathcal{OS}(n)\)s to obtain longer orientable sequences?

3. A problem closely related to efficiently generating long \(\mathcal{OS}(n)\)s is the problem of decoding or unranking orientable sequences. That is, given an arbitrary length-\(n\) substring of an \(\mathcal{OS}(n)\), efficiently determine where in the sequence this substring is located. There has been little to no progress in this area. Even in the well-studied area of de Bruijn sequences, only a few efficient decoding algorithms have been discovered.

10 Acknowledgment↩︎

Joe Sawada (grant RGPIN-2025-03961) and Daniel Gabrić (grant RGPIN-2026-04863) gratefully acknowledge research support from the Natural Sciences and Engineering Research Council of Canada (NSERC).

References↩︎

---

1. This paper was presented in part at Combinatorial Pattern Matching 2024 (CPM 2024) [6].↩︎

2. Periodic strings are are also known as powers in the literature. The term periodic is sometimes used to denote a string of the form \((\alpha\beta)^i \alpha\) where \(\alpha\) is non-empty, \(\beta\) is possibly empty, \(i\geq 1\), and \(\frac{|(\alpha\beta)^i \alpha|}{|\alpha\beta|}\geq 2\). Under this definition, the word \(\mathtt{alfalfa}\) is periodic, but \(\mathtt{bonobo}\) is not.↩︎

3. These bounds correspond to \(\tilde{L}_n\) and \(\tilde{U}_n\), respectively, as they appear in [2].↩︎

4. The resulting \(\mathcal{AOS}(n)\)s generated up to \(n=20\) are available for download at http://debruijnsequence.org/db/orientable.↩︎