×

Three-dimensional periodicity and its application to pattern matching. (English) Zbl 1087.68080

Summary: We study three-dimensional periodicity in finite arrays and introduce four categories of three-dimensional periodicity: edge-periodic, side-aperiodic, side-periodic, and completely periodic. We analyze three-dimensional periodicity thoroughly, and we characterize periods of a finite three-dimensional array by a small number of vectors. This periodicity analysis leads to an efficient algorithm for three-dimensional pattern matching.

MSC:

68R15 Combinatorics on words
68R05 Combinatorics in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI