On shortening u-cycles and u-words for permutations

This paper initiates the study of shortening universal cycles (u-cycles) and universal words (u-words) for permutations either by using incomparable elements, or by using non-deterministic symbols. The latter approach is similar in nature to the recent relevant studies for the de Bruijn sequences. A particular result we obtain in this paper is that u-words for n-permutations exist of lengths n! + (1 - k)(n - 1) for k = 0, 1, ..., (n - 2)!. (C) 2019 Published by Elsevier B.V.