ON THE EXISTENCE OF DE-BRUIJN TORI WITH 2 BY 2 WINDOWS

Necessary and sufficient conditions for the existence of de Bruijn Tor i (or Perfect Maps) with two by two windows over any alphabet are give n. This is the first two-dimensional window size for which the existen ce question has been completely answered for every alphabet. The techn iques used to construct these arrays utilise existing results on Perfe ct Factors and Perfect Multi-Factors in one and two dimensions and inv olve new results on Perfect Factors with 'puncturing capabilities'. Fi nally, the existence question for two-dimensional Perfect Factors is c onsidered and is settled for two by two windows and alphabets of prime -power size. (C) 1996 Academic Press, Inc.