Abstract
We propose a formal characterization of d-dimensional periodicities. We show first that any periodic pattern has a canonical decomposition and a minimal generator, generalizing the 1D property, This allows to classify the d-dimensional patterns in 2d−1 + 1 classes, according to their periodicities, each class having subclasses. A full classification of the coverings of a 2-dimensional space by a pattern follows. These results have important algorithmic issues in pattern matching. First, the covering classification allows an efficient use of the now classical “duel” paradigm. Second, d-dimensional pattern matching complexity is intrinsically different for each class.
This work was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract No. 3075 (project ALCOM).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A. Amir and G. Benson. Two-dimensional periodicity and its application. In SODA'92, 1992. Proc. 3-rd Symposium on Discrete Algorithms, Orlando, FL.
A. Amir, G. Benson, and M. Farach. Alphabet independent two dimensional matching. In STOC'92, pages 59–67, 1992. Victoria,BC.
R. Baeza-Yates and M. Régnier. Fast algorithms for two dimensional and multiple pattern matching. In SWAT'90, volume 447 of Lecture Notes in Computer Science, pages 332–347. Springer-Verlag, 1990. Preliminary draft in Proc. Swedish Workshop on Algorithm Theory, Bergen, Norway. To appear in IPL.
R. Cole and R. Hariharan. Tighter Bounds on the Exact Complexity of String Matching. In FOCS'92. IEEE, 1992. Proc. 33-rd IEEE Conference on Foundations of Computer Science, Pittsburgh, USA.
Z. Galil. Hunting Lions in the Desert Optimally or a Constant-Time Optimal Parallel String-Matching Algorithm. In STOCS'92, 1992. Victoria,BC.
Z. Galil and K. Park. Truly Alphabet Independent Two-Dimensional Pattern Matching. In FOCS'92. IEEE, 1992. Proc. 33-rd IEEE Conference on Foundations of Computer Science, Pittsburgh, USA.
S. Lang. Elliptic Functions. Springer-Verlag, New-York, 1987.
Lothaire. Combinatorics on Words. Addison-Wesley, Reading, Mass., 1983.
P. Nicodème and M. Régnier. Towards 2D Pattern Matching Complexity, 1992. in preparation.
M. Régnier. Knuth-Morris-Pratt algorithm: an analysis. In MFCS'89, volume 379 of Lecture Notes in Computer Science, pages 431–444. Springer-Verlag, 1989. Proc. Mathematical Foundations for Computer Science 89, Porubka, Poland.
U. Vishkin. Optimal Parallel Pattern Matching in Strings. Information and Control, 67:91–113, 1985.
R.F. Zhu and T. Takaoka. A technique for two-dimensional pattern matching. CACM., 32(9):1110–1120, 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Régnier, M., Rostami, L. (1993). A unifying look at d-dimensional periodicities and space coverings. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds) Combinatorial Pattern Matching. CPM 1993. Lecture Notes in Computer Science, vol 684. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029807
Download citation
DOI: https://doi.org/10.1007/BFb0029807
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56764-6
Online ISBN: 978-3-540-47732-7
eBook Packages: Springer Book Archive