Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950921 | Information Processing Letters | 2017 | 6 Pages |
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 mÃn arrays that are primitive. Finally, we show that one can test primitivity and compute the primitive root of an array in linear time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit, Taylor J. Smith,