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 (https://doi.org/10.1016/j.dam.2019.01.025)

[thumbnail of Kitaev-etal-DAM-2019-On shortening-u-cycles-and-u-words-for-permutations]
Preview
 Text. Filename: Kitaev_etal_DAM_2019_On_shortening_u_cycles_and_u_words_for_permutations.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (297kB)| Preview

Abstract

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

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Potapov, Vladimir N. and Vajnovszki, Vincent;
CORE (COnnecting REpositories)