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 |