On shortening u-cycles and u-words for permutations

Kitaev, Sergey and Potapov, Vladimir N. and Vajnovszki, Vincent (2019) On shortening u-cycles and u-words for permutations. Discrete Applied Mathematics, 260. pp. 203-213. ISSN 0166-218X

[img] Text (Kitaev-etal-DAM-2019-On shortening-u-cycles-and-u-words-for-permutations)
Accepted Author Manuscript
Restricted to Repository staff only until 6 February 2020.
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (297kB) | Request a copy from the Strathclyde author


    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)!.