NEW CLASSES OF PERFECT MAPS .2.

The existence and construction of perfect maps, also known as de Bruij n arrays or de Bruijn tori, is further considered. A c-ary (r, s; u, u psilon) perfect map is a two-dimensional periodic array with periods r and s and symbols from an alphabet of size c with the property that e very possible u x upsilon array of symbols occurs exactly once in a pe riod of the array. Necessary conditions on the parameters r, s, u, ups ilon for the existence of perfect maps are known to be sufficient when c is a power of a prime. This result is combined with some generalisa tions of the techniques of Mitchell to construct c-ary perfect maps fo r a large class of parameter sets. Our results are the strongest yet o btained on the existence question for c-ary perfect maps. (C) 1996 Aca demic Press, Inc.