| Affiliation: | (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 symbols1 through q to the integers modulo q n so that every word appears on some translate of  . Thisdefinition generalizes that of de Bruijn cycles, and opens up a multitude of questions. We addressthe existence of such cycles, discuss  reduced cycles (ones in which the all-zeroes string neednot appear), and provide general bounds on the shortest sequence which contains all words onsome translate of  . We also prove a variant on recent results concerning decompositions ofcomplete graphs into cycles and employ it to resolve the case of  completely.AMS Subject Classification: 94A55, 05C70. |
