Abstract: We discuss several two-dimensional generalizations of the familiar Lyndon-Schutzenberger 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 x n arrays that are primitive. Finally, we show that one can test primitivity and compute the primitive root of an array in linear time.
Recommendations
Cites work
- scientific article; zbMATH DE number 3811868 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 742992 (Why is no real title available?)
- scientific article; zbMATH DE number 801745 (Why is no real title available?)
- A Second Course in Formal Languages and Automata Theory
- A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
- A note on defect theorems for 2-dimensional words and trees
- An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
- Computing and Combinatorics
- Coverability in two dimensions
- Defect theorem in the plane
- Fast Pattern Matching in Strings
- On Fine and Wilf's theorem for bidimensional words.
- The Sequence of Pedal Triangles
- The equation \(a_ M=b^ Nc^ P\) in a free group
- Two-Dimensional Periodicity in Rectangular Arrays
- Two-dimensional prefix string matching and covering on square matrices
Cited in
(11)- Enumeration of two dimensional palindromes
- Multidimensional period recovery
- Algebraic properties of Parikh matrices of binary picture arrays
- Two-dimensional maximal repetitions
- From words to pictures: row-column combinations and Chomsky-Schützenberger theorem
- Two-dimensional maximal repetitions
- HV-Palindromes in Two-Dimensional Words
- Two-dimensional Fibonacci words: tandem repeats and factor complexity
- Two-dimensional codes
- Reducing the local alphabet size in tiling systems by means of 2D comma-free codes
- On the least number of palindromes in two-dimensional words
This page was built for publication: Periodicity in rectangular arrays
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344541)
