Special orientable sequences
Provides necessary building blocks for constructing orientable sequences over any alphabet, solving a bottleneck in prior recursive methods for position-location applications.
The authors construct special orientable sequences over arbitrary finite alphabets for all window sizes, achieving periods asymptotic to the optimal as alphabet size increases. This enables recursive construction methods for orientable sequences in automatic position-location applications.
Analogously to de Bruijn sequences, Orientable sequences have application in automatic position-location applications and, until recently, studies of these sequences focused on the binary case. In recent work by Alhakim et al., recursive methods of construction were described for orientable sequences over arbitrary finite alphabets, requiring 'starter sequences' with special properties. Some of these methods required as input special orientable sequences, i.e. orientable sequences which were simultaneously negative orientable. We exhibit methods for constructing special orientable sequences with properties appropriate for use in two of the recursive methods of Alhakim et al. As a result we are able to show how to construct special orientable sequences for arbitrary sizes of alphabet (larger than a small lower bound) and for all window sizes. These sequences have periods asymptotic to the optimal as the alphabet size increases.