On shortening u-cycles and u-words for permutations

Sergey Kitaev, Vladimir N. Potapov, Vincent Vajnovszki

Research output: Contribution to journalArticle

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

LanguageEnglish
Pages203-213
Number of pages11
JournalDiscrete Applied Mathematics
Volume260
Early online date6 Feb 2019
DOIs
Publication statusPublished - 15 May 2019

Fingerprint

Permutation
De Bruijn Sequences
Cycle

Keywords

  • universal cycles
  • universal words
  • permutations
  • mathematics
  • computation

Cite this

Kitaev, Sergey ; Potapov, Vladimir N. ; Vajnovszki, Vincent. / On shortening u-cycles and u-words for permutations. In: Discrete Applied Mathematics. 2019 ; Vol. 260. pp. 203-213.
@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 = "5",
day = "15",
doi = "10.1016/j.dam.2019.01.025",
language = "English",
volume = "260",
pages = "203--213",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",

}

On shortening u-cycles and u-words for permutations. / Kitaev, Sergey; Potapov, Vladimir N.; Vajnovszki, Vincent.

In: Discrete Applied Mathematics, Vol. 260, 15.05.2019, p. 203-213.

Research output: Contribution to journalArticle

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

VL - 260

SP - 203

EP - 213

JO - Discrete Applied Mathematics

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -