Constructing Orientable Sequences Using Cycle Joining Algorithm
Mahmoud Hazari · The Atrium (University of Guelph) · 2023
A de Bruijn sequence of order n is a cyclic sequence that stretches to a length of 2^n, where each string of length n is featured exactly once as a substring. Orientable sequences are a relative type of de Bruijn sequences that necessitate every substring to not only appear just once but also to be unique when interpreted from either left to right or right to left. Such sequences have applications in position-location sensing in robotic vision. Like de Bruijn sequences, orientable sequences can also be constructed through different methods. For example, they can be generated using greedy algorithms like Prefer-same and Prefer-opposite, or via Exhaustive search, Cycle joining, and more. The upper bound on the length of orientable sequences can be achieved through calculations, whereas the lower bound is a little more complex. While Dai et al. provideda construction method for the lower bound, it has not been implemented by other researchers so far. The aim of this research is to find a practical and easily implementable method for constructing the lower bound of orientable sequences. To achieve this, we implemented the Cycle Joining algorithm. This algorithm aims to identify strings with n−1 bits in common and subsequently link them together to create a longer sequence of the same order n.