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
|
Text (Kitaev-etal-DAM-2019-On shortening-u-cycles-and-u-words-for-permutations)
Kitaev_etal_DAM_2019_On_shortening_u_cycles_and_u_words_for_permutations.pdf Accepted Author Manuscript License: ![]() Download (297kB)| Preview |
Official URL: https://doi.org/10.1016/j.dam.2019.01.025
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)!.
Creators(s): |
Kitaev, Sergey ![]() | Item type: | Article |
---|---|
ID code: | 66670 |
Keywords: | universal cycles, universal words, permutations, mathematics, computation, Electronic computers. Computer science, Applied Mathematics, Computer Science(all) |
Subjects: | Science > Mathematics > Electronic computers. Computer science |
Department: | Faculty of Science > Computer and Information Sciences |
Depositing user: | Pure Administrator |
Date deposited: | 22 Jan 2019 10:30 |
Last modified: | 15 Feb 2021 02:14 |
Related URLs: | |
URI: | https://strathprints.strath.ac.uk/id/eprint/66670 |
Export data: |
CORE (COnnecting REpositories)