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.
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2017, 118, pp.58-63. 〈10.1016/j.ipl.2016.09.011〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01378894
Contributeur : Gwenaël Richomme <>
Soumis le : lundi 10 octobre 2016 - 22:20:58
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

108