6533b828fe1ef96bd1287a95
RESEARCH PRODUCT
On shortening u-cycles and u-words for permutations
Vincent VajnovszkiVladimir N. PotapovSergey Kitaevsubject
QA75De Bruijn sequenceApplied Mathematics0211 other engineering and technologies021107 urban & regional planning0102 computer and information sciences02 engineering and technology01 natural sciencesCombinatorics010201 computation theory & mathematicsFOS: MathematicsDiscrete Mathematics and CombinatoricsMathematics - CombinatoricsCombinatorics (math.CO)Mathematicsdescription
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 ) ! .
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-07-19 |