{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T11:56:49Z","timestamp":1776859009240,"version":"3.51.2"},"reference-count":38,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2003,4,1]],"date-time":"2003-04-01T00:00:00Z","timestamp":1049155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3796,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,4]]},"DOI":"10.1016\/s0304-3975(01)00386-3","type":"journal-article","created":{"date-parts":[[2003,4,23]],"date-time":"2003-04-23T19:53:40Z","timestamp":1051127620000},"page":"123-150","source":"Crossref","is-referenced-by-count":27,"title":["On a conjecture on bidimensional words"],"prefix":"10.1016","volume":"299","author":[{"given":"Chiara","family":"Epifanio","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Koskas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Filippo","family":"Mignosi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00386-3_BIB1","doi-asserted-by":"crossref","unstructured":"A. Amir, G.E. Benson, Alphabet independent two-dimensional pattern matching, Proc. 24th ACM Symp. Theory on Computers, 1992, pp. 59\u201368.","DOI":"10.1145\/129712.129719"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB2","unstructured":"A. Amir, G.E. Benson, Two-dimensional periodicity and its applications, Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 440\u2013452."},{"issue":"1","key":"10.1016\/S0304-3975(01)00386-3_BIB3","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1137\/S0097539795298321","article-title":"Two-dimensional periodicity in rectangular arrays","volume":"27","author":"Amir","year":"1998","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB4","doi-asserted-by":"crossref","unstructured":"A. Amir, M. Farach, Efficient matching of nonrectangular shapes, Ann. Math. Artif. Intell., special issue on the Foundations of Artificial Intelligence (4) (1991) 211\u2013224.","DOI":"10.1007\/BF01531057"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB5","doi-asserted-by":"crossref","unstructured":"A. Amir, M. Farach, Two dimensional dictionary matching, Inform. Process. Lett. 1992, Vol. 44, pp. 233\u2013239.","DOI":"10.1016\/0020-0190(92)90206-B"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB6","doi-asserted-by":"crossref","unstructured":"A. Amir, G.E. Benson, M. Farach, An alphabet independent approach to two dimensional pattern matching, SIAM J. Comput. 23(2) (1994) 313\u2013323 (preliminary version appeared in STOC 92).","DOI":"10.1137\/S0097539792226321"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB7","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0012-365X(00)00039-X","article-title":"Tilings and rotations: a two-dimensional generalization of Sturmian sequences","volume":"223","author":"Berth\u00e9","year":"2000","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB8","unstructured":"J. Cassaigne, Double sequences with complexity mn+1. J. Auto. Lang. Comb. 4 (1999), pp. 153\u2013170."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB9","doi-asserted-by":"crossref","unstructured":"J. Cassaigne, Private communication, 1999.","DOI":"10.1080\/12460125.1999.10511756"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB10","unstructured":"J. Cassaigne, D. Bernardi, Private communication, 1997."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB11","article-title":"A linear algorithm for segmentation of digital curves","author":"Debled","year":"1995","journal-title":"IEEE Int. J.P.R.A.I."},{"issue":"2","key":"10.1016\/S0304-3975(01)00386-3_BIB12","first-page":"319","article-title":"A local criterion for regularity of a system of points","volume":"17","author":"Delone [B.N. Delaunay]","year":"1976","journal-title":"Sov. Math. Dokl."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB13","first-page":"747","article-title":"Regularity and finiteness conditions","volume":"Vol. 1","author":"de Luca","year":"1997"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB14","doi-asserted-by":"crossref","unstructured":"N.P. Dolbilin, J.C. Lagarias, M. Senechal, Multiregular point systems, Discrete Comput. Geom., to appear.","DOI":"10.1007\/PL00009397"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB15","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","article-title":"Uniqueness theorem for periodic functions","volume":"16","author":"Fine","year":"1965","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB16","doi-asserted-by":"crossref","unstructured":"Z. Galil, R. Giancarlo, On the exact complexity of string matching: upper bounds,SIAM J. Comp. 20(6) 1008\u20131020.","DOI":"10.1137\/0220063"},{"issue":"5","key":"10.1016\/S0304-3975(01)00386-3_BIB17","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1137\/S0097539792241941","article-title":"Alphabet-independent two-dimensional witness computation","volume":"25","author":"Galil","year":"1996","journal-title":"Siam J. Comput."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB18","doi-asserted-by":"crossref","unstructured":"Z. Galil, K. Park, Truly alphabet independent two-dimensional pattern matching, Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992, pp. 247\u2013256.","DOI":"10.1109\/SFCS.1992.267767"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB19","doi-asserted-by":"crossref","unstructured":"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\u2013141.","DOI":"10.1007\/BFb0017478"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB20","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0012-365X(96)00077-5","article-title":"Complexit\u00e9s de Suites de Toeplitz","volume":"83","author":"Koskas","year":"1998","journal-title":"Discr. Math."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB21","unstructured":"Lothaire, Combinatorics on words, Encyclopedia of Mathemathics and its Applications, Vol. 17, Addison-Wesley, Reading, MA, 1983."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB22","unstructured":"Lothaire, Algebraic combinatorics on words, Available for the moment at URL http:\/\/www-igm.univ-mlv.fr\/~berstel\/Lothaire."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB23","series-title":"Combinatorial Group Theory","author":"Lyndon","year":"1977"},{"issue":"4","key":"10.1016\/S0304-3975(01)00386-3_BIB24","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1307\/mmj\/1028998766","article-title":"The equation am=bncp in a free group","volume":"9","author":"Lyndon","year":"1962","journal-title":"Michigan Math. J."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB25","doi-asserted-by":"crossref","unstructured":"F. Mignosi, A. Restivo, P.V. Silva, On Fine and Wilf's theorem for bidimensional words, Theoret. Comput. Sci., to appear.","DOI":"10.1016\/S0304-3975(01)00226-2"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB26","doi-asserted-by":"crossref","first-page":"815","DOI":"10.2307\/2371264","article-title":"Symbolic dynamics","volume":"60","author":"Morse","year":"1938","journal-title":"Amer. J. Math."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB27","unstructured":"M. Nivat, Invited talk at ICALP\u201997."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB28","doi-asserted-by":"crossref","first-page":"661","DOI":"10.2307\/2118575","article-title":"The pinwheel tilings of the plane","volume":"139","author":"Radin","year":"1994","journal-title":"Ann. Math."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB29","doi-asserted-by":"crossref","unstructured":"M. Regnier, L. Rostami, A unifying look at d-dimensional periodicities and space coverings, Proc. 4th Symposium on Combinatorial Pattern Matching, 1993, pp. 215\u2013227.","DOI":"10.1007\/BFb0029807"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB30","unstructured":"J.P. Reveill\u00e8s, G\u00e9om\u00e9trie Discr\u00e8te, Calcul en nombres entiers et algorithmique, Th\u00e8se D\u2019\u00c9tat, Universit\u00e9 Louis Pasteur, Strasbourg, 1991."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB31","doi-asserted-by":"crossref","unstructured":"J.P. Reveill\u00e8s, Combinatorial pieces in digital lines and planes, Vision Geometry, IV, San Diego, CA, 1995, pp. 23\u201334.","DOI":"10.1117\/12.216425"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB32","series-title":"Digital Picture Processing","author":"Rosenfeld","year":"1982"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB33","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/PL00004798","article-title":"Low complexity functions and convex sets in Zk","volume":"233","author":"Sander","year":"2000","journal-title":"Math. Z."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB34","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0304-3975(99)00078-X","article-title":"The complexity of functions on lattices","volume":"246","author":"Sander","year":"2000","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB35","doi-asserted-by":"crossref","unstructured":"J.W. Sander, R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices, Theoret. Comput. Sci., to appear.","DOI":"10.1016\/S0304-3975(01)00281-X"},{"key":"10.1016\/S0304-3975(01)00386-3_BIB36","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0304-3975(97)00117-5","article-title":"Combinatoire des motifs d'une suite sturmienne bidimensionnelle","volume":"209","author":"Vuillon","year":"1998","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB37","unstructured":"L. Vuillon, Contribution \u00e0 l\u2019\u00e9tude des pavages et des surfaces discr\u00e8tis\u00e9es, Ph.D. Thesis, Aix-Marseille II, December, 1996."},{"key":"10.1016\/S0304-3975(01)00386-3_BIB38","first-page":"625","article-title":"Local configurations in discrete planes","volume":"6","author":"Vuillon","year":"1999","journal-title":"Bull. Belg. Math. Soc."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003863?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003863?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T02:08:22Z","timestamp":1620094102000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501003863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":38,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2003,4]]}},"alternative-id":["S0304397501003863"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00386-3","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}