An orientable sequence of order n is a cyclic binary sequence such that each length-n substring appears at most once in either direction. Maximal length orientable sequences are known only for n ≤ 7, and a trivial upper bound on their length is 2^{n-1} - 2^{⌊(n-1)/2⌋}. This paper presents the first efficient algorithm to construct orientable sequences with asymptotically optimal length; more specifically, our algorithm constructs orientable sequences via cycle-joining and a successor-rule approach requiring O(n) time per bit and O(n) space. This answers a longstanding open question from Dai, Martin, Robshaw, Wild [Cryptography and Coding III (1993)]. Our sequences are applied to find new longest-known orientable sequences for n ≤ 20.

A border of a word w is a word that is both a non-empty proper prefix and suffix of w . If w has a border, then it is said to be bordered ; otherwise, it is said to be unbordered . The main results of this paper are the first algorithms to rank and unrank length- n bordered and unbordered words over a k -letter alphabet. We show that, under the unit-cost RAM model, ranking bordered and unbordered words can be done in O ( k n 3 ) time using O ( n ) space, and unranking them can be done in O ( n 4 k log ⁡ k ) time using O ( n ) space.

A word is said to beborderedif it contains a non-empty proper prefix that is also a suffix. We can naturally extend this definition to pairs of non-empty words. A pair of words$(u,v)$is said to bemutually borderedif there exists a word that is a non-empty proper prefix of$u$and suffix of$v$, and there exists a word that is a non-empty proper suffix of$u$and prefix of$v$. In other words,$(u,v)$is mutually bordered if$u$overlaps$v$and$v$overlaps$u$. We give a recurrence for the number of mutually bordered pairs of words. Furthermore, we show that, asymptotically, there are$c\cdot k^{2n}$mutually bordered words of length-$n$over a$k$-letter alphabet, where$c$is a constant. Finally, we show that the expected shortest overlap between pairs of words is bounded above by a constant.

We present a simple framework for constructing$k$-ary de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes several previously known de Bruijn sequence constructions based on the pure cycling register and is applied to derive a new construction that is perhaps the simplest of all successors. Furthermore, it generalizes an algorithm to construct binary de Bruijn sequences based on any arbitrary nonsingular feedback function. The framework is applied to derive and prove the correctness of successors to efficiently construct 1) universal cycles for$k$-ary strings of length$n$whose weight is bounded by some$w$and 2) universal cycles for permutations. It has also been subsequently applied to find the first universal cycle constructions for weak orders.