On shortening u-cycles and u-words for permutations

Sergey Kitaev; Vladimir N. Potapov; Vincent Vajnovszki

doi:10.1016/j.dam.2019.01.025

On shortening u-cycles and u-words for permutations

Sergey Kitaev, Vladimir N. Potapov, Vincent Vajnovszki

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

15 Downloads (Pure)

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

Original language	English
Pages (from-to)	203-213
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	260
Early online date	6 Feb 2019
DOIs	https://doi.org/10.1016/j.dam.2019.01.025
Publication status	Published - 15 May 2019

Keywords

universal cycles
universal words
permutations
mathematics
computation

Access to Document

10.1016/j.dam.2019.01.025

Kitaev-etal-DAM-2019-On shortening-u-cycles-and-u-words-for-permutationsAccepted author manuscript, 291 KBLicence: CC BY-NC-ND 4.0

Cite this

@article{3052ae38df734b7dab2fbe3f4a0a4559,

title = "On shortening u-cycles and u-words for permutations",

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

keywords = "universal cycles, universal words, permutations, mathematics, computation",

author = "Sergey Kitaev and Potapov, {Vladimir N.} and Vincent Vajnovszki",

year = "2019",

month = may,

day = "15",

doi = "10.1016/j.dam.2019.01.025",

language = "English",

volume = "260",

pages = "203--213",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

}

TY - JOUR

T1 - On shortening u-cycles and u-words for permutations

AU - Kitaev, Sergey

AU - Potapov, Vladimir N.

AU - Vajnovszki, Vincent

PY - 2019/5/15

Y1 - 2019/5/15

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

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

KW - universal cycles

KW - universal words

KW - permutations

KW - mathematics

KW - computation

UR - https://www.journals.elsevier.com/discrete-applied-mathematics

U2 - 10.1016/j.dam.2019.01.025

DO - 10.1016/j.dam.2019.01.025

M3 - Article

SN - 0166-218X

VL - 260

SP - 203

EP - 213

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

On shortening u-cycles and u-words for permutations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this