BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR92-181
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: On The De Bruijn Torus Problem
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Hurlbert, Glenn
AUTHOR:: Isaak, Garth
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1992
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR92-181.pdf
ABSTRACT::
	A (kn;n)k-de Bruijn Cycle is a cyclic k-ary sequence with the
property that every k-ary n-tuple appears exactly once contiguously on
the cycle.  A (kr, ks; m, n)k-de Bruijn Torus is a k-ary krXks
toroidal array with the property that every k-ary m x n matrix appears
exactly once contiguously on the torus.  As is the case with de Bruijn
cycles, the 2-dimensional version has many interesting applications,
from coding and communications to pseudo-random arrays, spectral
imaging, and robot self-location.  J.C. Cock proved the existence of
such tori for all m, n, and k, and Chung, Diaconis, and Graham asked
if it were possible that r = s and m -= n for n even.  Fan, Fan, Ma
and Siu showed this was possible for k - 2.  Combining new techniques
with old, we prove the result for k > 2 and show that actually much
more is possible.  The cases in 3 or more dimensions remain.
END:: ncstrl.dartmouthcs//TR92-181