×

On a conjecture on bidimensional words. (English) Zbl 1040.68076

Summary: We prove that, given a double sequence \(\mathbf w\) over the alphabet \(A\) (i.e. a mapping from \(\mathbb Z^2\) to \(A\)), if there exists a pair \((n_0, m_0) \in \mathbb Z^2\) such that \(p_{\mathbf W} (n_0, m_0) < \frac {1}{100} n_0m_0\), then \(\mathbf w\) has a periodicity vector, where \(p_{\mathbf w}\) is the complexity function in rectangles of \(\mathbf w\).

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Amir, G.E. Benson, Alphabet independent two-dimensional pattern matching, Proc. 24th ACM Symp. Theory on Computers, 1992, pp. 59-68.; A. Amir, G.E. Benson, Alphabet independent two-dimensional pattern matching, Proc. 24th ACM Symp. Theory on Computers, 1992, pp. 59-68.
[2] A. Amir, G.E. Benson, Two-dimensional periodicity and its applications, Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 440-452.; A. Amir, G.E. Benson, Two-dimensional periodicity and its applications, Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 440-452. · Zbl 0829.68062
[3] Amir, A.; Benson, G. E., Two-dimensional periodicity in rectangular arrays, SIAM J. Comput., 27, 1, 90-106 (1998) · Zbl 0907.68108
[4] A. Amir, M. Farach, Efficient matching of nonrectangular shapes, Ann. Math. Artif. Intell., special issue on the Foundations of Artificial Intelligence (4) (1991) 211-224.; A. Amir, M. Farach, Efficient matching of nonrectangular shapes, Ann. Math. Artif. Intell., special issue on the Foundations of Artificial Intelligence (4) (1991) 211-224. · Zbl 1034.68537
[5] A. Amir, M. Farach, Two dimensional dictionary matching, Inform. Process. Lett. 1992, Vol. 44, pp. 233-239.; A. Amir, M. Farach, Two dimensional dictionary matching, Inform. Process. Lett. 1992, Vol. 44, pp. 233-239. · Zbl 0796.68193
[6] A. Amir, G.E. Benson, M. Farach, An alphabet independent approach to two dimensional pattern matching, SIAM J. Comput. 23(2) (1994) 313-323 (preliminary version appeared in STOC 92).; A. Amir, G.E. Benson, M. Farach, An alphabet independent approach to two dimensional pattern matching, SIAM J. Comput. 23(2) (1994) 313-323 (preliminary version appeared in STOC 92). · Zbl 0804.68056
[7] Berthé, V.; Vuillon, L., Tilings and rotations: a two-dimensional generalization of Sturmian sequences, Discrete Math., 223, 27-33 (2000) · Zbl 0970.68124
[8] J. Cassaigne, Double sequences with complexity mn; J. Cassaigne, Double sequences with complexity mn · Zbl 0971.68123
[9] J. Cassaigne, Private communication, 1999.; J. Cassaigne, Private communication, 1999.
[10] J. Cassaigne, D. Bernardi, Private communication, 1997.; J. Cassaigne, D. Bernardi, Private communication, 1997.
[11] Debled, I.; Reveillès, J. P., A linear algorithm for segmentation of digital curves, IEEE Int. J.P.R.A.I. (1995)
[12] Delone [B. N. Delaunay], B. N.; Dolbilin, N. P.; Shtogrin, M. I.; Galiulin, R. V., A local criterion for regularity of a system of points, Sov. Math. Dokl., 17, 2, 319-322 (1976) · Zbl 0338.50007
[13] de Luca, A.; Varricchio, S., Regularity and finiteness conditions, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, Vol. 1 (1997), Springer: Springer Berlin), 747-810
[14] N.P. Dolbilin, J.C. Lagarias, M. Senechal, Multiregular point systems, Discrete Comput. Geom., to appear.; N.P. Dolbilin, J.C. Lagarias, M. Senechal, Multiregular point systems, Discrete Comput. Geom., to appear. · Zbl 0915.51017
[15] Fine, N. J.; Wilf, H. S., Uniqueness theorem for periodic functions, Proc. Amer. Math. Soc., 16, 109-114 (1965) · Zbl 0131.30203
[16] Z. Galil, R. Giancarlo, On the exact complexity of string matching: upper bounds,SIAM J. Comp. 20(6) 1008-1020.; Z. Galil, R. Giancarlo, On the exact complexity of string matching: upper bounds,SIAM J. Comp. 20(6) 1008-1020. · Zbl 0738.68042
[17] Galil, Z.; Park, K., Alphabet-independent two-dimensional witness computation, Siam J. Comput., 25, 5, 907-935 (1996) · Zbl 0861.68032
[18] Z. Galil, K. Park, Truly alphabet independent two-dimensional pattern matching, Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992, pp. 247-256.; Z. Galil, K. Park, Truly alphabet independent two-dimensional pattern matching, Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992, pp. 247-256. · Zbl 0942.68707
[19] R. Giancarlo, F. Mignosi, Generalizations of the periodicity theorem of Fine and Wilf, CAAP94,Lecture Notes in Computer Science, Vol. 787, Springer, Berlin, pp. 130-141.; R. Giancarlo, F. Mignosi, Generalizations of the periodicity theorem of Fine and Wilf, CAAP94,Lecture Notes in Computer Science, Vol. 787, Springer, Berlin, pp. 130-141. · Zbl 0938.68765
[20] Koskas, M., Complexités de Suites de Toeplitz, Discr. Math., 83, 161-183 (1998) · Zbl 0895.11011
[21] Lothaire, Combinatorics on words, Encyclopedia of Mathemathics and its Applications, Vol. 17, Addison-Wesley, Reading, MA, 1983.; Lothaire, Combinatorics on words, Encyclopedia of Mathemathics and its Applications, Vol. 17, Addison-Wesley, Reading, MA, 1983. · Zbl 0514.20045
[22] Lothaire, Algebraic combinatorics on words, Available for the moment at URL http://www-igm.univ-mlv.fr/ berstel/Lothaire; Lothaire, Algebraic combinatorics on words, Available for the moment at URL http://www-igm.univ-mlv.fr/ berstel/Lothaire · Zbl 1001.68093
[23] Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory (1977), Springer: Springer Berlin · Zbl 0368.20023
[24] Lyndon, R. C.; Schutzenberger, M. P., The equation \(a^m=b^{n\) · Zbl 0106.02204
[25] F. Mignosi, A. Restivo, P.V. Silva, On Fine and Wilf’s theorem for bidimensional words, Theoret. Comput. Sci., to appear.; F. Mignosi, A. Restivo, P.V. Silva, On Fine and Wilf’s theorem for bidimensional words, Theoret. Comput. Sci., to appear. · Zbl 1064.68075
[26] Morse, M.; Hedlund, G. A., Symbolic dynamics, Amer. J. Math., 60, 815-866 (1938) · JFM 64.0798.04
[27] M. Nivat, Invited talk at ICALP’97.; M. Nivat, Invited talk at ICALP’97.
[28] Radin, C., The pinwheel tilings of the plane, Ann. Math., 139, 661-702 (1994) · Zbl 0808.52022
[29] M. Regnier, L. Rostami, A unifying look at \(d\); M. Regnier, L. Rostami, A unifying look at \(d\)
[30] J.P. Reveillès, Géométrie Discrète, Calcul en nombres entiers et algorithmique, Thèse D’État, Université Louis Pasteur, Strasbourg, 1991.; J.P. Reveillès, Géométrie Discrète, Calcul en nombres entiers et algorithmique, Thèse D’État, Université Louis Pasteur, Strasbourg, 1991.
[31] J.P. Reveillès, Combinatorial pieces in digital lines and planes, Vision Geometry, IV, San Diego, CA, 1995, pp. 23-34.; J.P. Reveillès, Combinatorial pieces in digital lines and planes, Vision Geometry, IV, San Diego, CA, 1995, pp. 23-34.
[32] Rosenfeld, A.; Kak, A. C., Digital Picture Processing (1982), Academic Press: Academic Press New York · Zbl 0564.94001
[33] Sander, J. W.; Tijdeman, R., Low complexity functions and convex sets in \(Z^k\), Math. Z., 233, 205-218 (2000) · Zbl 1022.37011
[34] Sander, J. W.; Tijdeman, R., The complexity of functions on lattices, Theoret. Comput. Sci., 246, 195-225 (2000) · Zbl 1005.68118
[35] J.W. Sander, R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices, Theoret. Comput. Sci., to appear.; J.W. Sander, R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices, Theoret. Comput. Sci., to appear. · Zbl 0989.68062
[36] Vuillon, L., Combinatoire des motifs d’une suite sturmienne bidimensionnelle, Theoret. Comput. Sci., 209, 261-285 (1998) · Zbl 0913.68206
[37] L. Vuillon, Contribution à l’étude des pavages et des surfaces discrètisées, Ph.D. Thesis, Aix-Marseille II, December, 1996.; L. Vuillon, Contribution à l’étude des pavages et des surfaces discrètisées, Ph.D. Thesis, Aix-Marseille II, December, 1996.
[38] Vuillon, L., Local configurations in discrete planes, Bull. Belg. Math. Soc., 6, 625-636 (1999) · Zbl 1002.11022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.