Periodicity in rectangular arrays
From MaRDI portal
Publication:344541
DOI10.1016/J.IPL.2016.09.011zbMATH Open1392.68216arXiv1602.06915OpenAlexW2280015856MaRDI QIDQ344541FDOQ344541
Authors: Guilhem Gamard, Gwénaël Richomme, Taylor J. Smith, Jeffrey Shallit 
Publication date: 23 November 2016
Published in: Information Processing Letters (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1602.06915
Recommendations
Cites Work
- Title not available (Why is that?)
- 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
- The equation \(a_ M=b^ Nc^ P\) in a free group
- Title not available (Why is that?)
- Fast Pattern Matching in Strings
- Title not available (Why is that?)
- A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
- Two-dimensional prefix string matching and covering on square matrices
- On Fine and Wilf's theorem for bidimensional words.
- Coverability in Two Dimensions
- Defect theorem in the plane
- A Second Course in Formal Languages and Automata Theory
- A note on defect theorems for 2-dimensional words and trees
- The Sequence of Pedal Triangles
- Two-Dimensional Periodicity in Rectangular Arrays
- Computing and Combinatorics
- Title not available (Why is that?)
Cited In (11)
- Title not available (Why is that?)
- Two-dimensional codes
- Enumeration of two dimensional palindromes
- On the least number of palindromes in two-dimensional words
- Multidimensional period recovery
- Two-dimensional maximal repetitions
- HV-Palindromes in Two-Dimensional Words
- Reducing the local alphabet size in tiling systems by means of 2D comma-free codes
- Algebraic properties of Parikh matrices of binary picture arrays
- Two-dimensional Fibonacci words: tandem repeats and factor complexity
- From words to pictures: row-column combinations and Chomsky-Schützenberger theorem
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)
