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)
Kitaev_etal_DAM_2019_On_shortening_u_cycles_and_u_words_for_permutations.pdf
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

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

    Author(s):Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Potapov, Vladimir N. and Vajnovszki, Vincent
    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:09 Nov 2019 04:09
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/66670
    Export data:
    CORE (COnnecting REpositories)