zbMATH — the first resource for mathematics

On shortening \(u\)-cycles and \(u\)-words for permutations. (English) Zbl 1409.05010
Summary: 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, \ldots,(n - 2)!\).

05A05 Permutations, words, matrices
Full Text: DOI arXiv
[1] Chen, H. Z.Q.; Kitaev, S.; Mütze, T.; Sun, B. Y., On universal partial words, Discrete Math. Theor. Comput. Sci., 19, 1, 1-19, (2017) · Zbl 1408.68122
[2] Chung, F.; Diaconis, P.; Graham, R., Universal cycles for combinatorial structures, Discrete Math., 110, 43-59, (1992) · Zbl 0776.05001
[3] Compeau, P. E.C.; Pevzner, P. A.; Tesler, G., How to apply de Bruijn graphs to genome assembly, Nature Biotechnol., 29, 11, 987-991, (2011)
[4] Fine, N. J.; Wilf, H. S., Uniqueness theorem for periodic functions, Proc. Amer. Math. Soc., 16, 109-114, (1965) · Zbl 0131.30203
[5] Goeckner, B.; Groothuis, C.; Hettle, C.; Kell, B.; Kirkpatrick, P.; Kirsch, R.; Solava, R., Universal partial words over non-binary alphabets, Theoret. Comput. Sci., 713, 56-65, (2018) · Zbl 1394.68271
[6] Nyu, V.; Fon-Der-Flaass, D., Estimates for the length of a universal sequence for permutations, (Russian), Diskretn. Anal. Issled. Oper. Ser., 17, 2, 65-70, (2000) · Zbl 0995.05003
[7] Pagès, J.; Salvi, J.; Collewet, C.; Forest, J., Optimised De Bruijn patterns for one-shot shape acquisition, Image Vis. Comput., 23, 8, 707-720, (2005)
[8] Ralston, A., De Bruijn sequences—a model example of the interaction of discrete mathematics and computer science, Math. Mag., 55, 3, 131-143, (1982) · Zbl 0492.05014
[9] Scheinerman, E. R., Determining planar location via complement-free De Brujin sequences using discrete optical sensors, IEEE Trans. Robot. Autom., 17, 6, 883-889, (2001)
[10] Sohn, H.; Bricker, D. L.; Simon, J. R.; Hsieh, Y., Optimal sequences of trials for balancing practice and repetition effects, Behav. Res. Methods Instrum. Comput., 29, 4, 574-581, (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.