Skip to Main content Skip to Navigation
Journal articles

Periodicity in rectangular arrays

Abstract : We discuss several two-dimensional generalizations of the familiar Lyndon–Schützenberger periodicity theorem for words. We consider the notion of primitive array (as one that cannot be expressed as the repetition of smaller arrays). We count the number of mxn arrays that are primitive. Finally, we show that one can test primitivity and compute the primitive root of an array in linear time.
Complete list of metadata
Contributor : Gwenaël Richomme <>
Submitted on : Monday, October 10, 2016 - 10:20:58 PM
Last modification on : Thursday, May 13, 2021 - 12:10:01 PM

Links full text



Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit, Taylor J. Smith. Periodicity in rectangular arrays. Information Processing Letters, Elsevier, 2017, 118, pp.58-63. ⟨10.1016/j.ipl.2016.09.011⟩. ⟨lirmm-01378894⟩



Record views