| Institution: | (1) Department of Mathematics, Courant Institute of Mathematical Sciences, New York University, 10012 New York, NY, USA;(2) Department of Computer Science and Engineering, University of California at San Diego, 92093 San Diego, CA, USA |
| Abstract: | For a set of integers
, we define a q-ary
-cycle to be an assignment of the symbols
1 through q to the integers modulo
q
n
so that every word appears on some translate of
. This
definition generalizes that of de Bruijn cycles, and opens up a multitude of questions. We address
the existence of such cycles, discuss  reduced cycles (ones in which the all-zeroes string need
not appear), and provide general bounds on the shortest sequence which contains all words on
some translate of
. We also prove a variant on recent results concerning decompositions of
complete graphs into cycles and employ it to resolve the case of
completely.AMS Subject Classification: 94A55, 05C70. |
