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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01378894
Contributor : Gwenaël Richomme <>
Submitted on : Monday, October 10, 2016 - 10:20:58 PM
Last modification on : Tuesday, May 12, 2020 - 1:46:05 PM

Links full text

Identifiers

Citation

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⟩

Share

Metrics

Record views

270