Periodicity in rectangular arrays

DOI10.1016/J.IPL.2016.09.011MaRDI QIDQ344541zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1602.06915

zbMATH Keywords

algorithmsformal languagestheory of computation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

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

• Two-Dimensional Periodicity in Rectangular Arrays
• Periodicity properties on partial words
• Generalized periodicity and primitivity for words
• Optimal discovery of repetitions in 2D
• Testing primitivity on partial words

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)