The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.5 / (1996))
Alphabet-Independent Two-Dimensional Witness Computation
Zvi Galil, Kunsoo Park,
Pages. 907-935
Abstract
Contents 1. Introduction
2. Preliminaries
3. Two-dimensional periodicity
3.1. Lattice-periodicity
3.2. Line-periodicity
3.3. Radiant-periodicity
4. The witness computation
4.1. $P^{t-1}$ is nonperiodic
4.2. $P^{t-1}$ is lattice-periodic
4.3. $P^{t-1}$ is line-peiodic (quad-I)
4.4. $P^{t-1}$ is radiant-periodic (quad-I)
5. Conclusion
Key words two-dimensional periodicity, pattern matching, witness computation
Mathmatical Subject Classification 68Q20, 68Q25, 68U10