On a conjecture on bidimensional words.

DOI10.1016/S0304-3975(01)00386-3zbMath1040.68076WikidataQ123144126 ScholiaQ123144126MaRDI QIDQ1874389

Michel Koskas, Chiara Epifanio, Filippo Mignosi

Publication date: 25 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

wordsPeriodicityCombinatorics on wordsBidimensionalComplexity functions

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (25)

Tree shift topological entropy ⋮ Digital planarity -- a review ⋮ Periodicity and local complexity ⋮ An Algebraic Geometric Approach to Multidimensional Words ⋮ Extensions of rich words ⋮ On periodic decompositions, one-sided nonexpansive directions and Nivat's conjecture ⋮ Nivat's conjecture and pattern complexity in algebraic subshifts ⋮ Complexity of short rectangles and periodicity ⋮ Minimal Complexities for Infinite Words Written with d Letters ⋮ An alphabetical approach to Nivat’s conjecture ⋮ On Periodicity of Generalized Two-Dimensional Words ⋮ Counting generic measures for a subshift of linear growth ⋮ On periodicity of two-dimensional words ⋮ Double sequences of low complexity ⋮ Plane digitization and related combinatorial problems ⋮ Maximal pattern complexity of two-dimensional words ⋮ Strong cocycle triviality for \(Z^{2}\) subshifts ⋮ On the least number of palindromes in two-dimensional words ⋮ An algebraic geometric approach to Nivat's conjecture ⋮ On periodicity of generalized two-dimensional infinite words ⋮ Aperiodic two-dimensional words of small abelian complexity ⋮ Optimal discovery of repetitions in 2D ⋮ On Fine and Wilf's theorem for bidimensional words. ⋮ A multidimensional critical factorization theorem ⋮ Nonexpansive $\mathbb {Z}^2$-subdynamics and Nivat’s Conjecture

Cites Work

• The equation \(a_ M=b^ Nc^ P\) in a free group
• Two-dimensional dictionary matching
• Combinatorics on patterns of a bidimensional Sturmian sequence
• Multiregular point systems
• The pinwheel tilings of the plane
• Efficient matching of nonrectangular shapes.
• Complexity of Toeplitz sequences
• The complexity of functions on lattices
• Tilings and rotations on the torus: A two-dimensional generalization of Sturmian sequences
• On Fine and Wilf's theorem for bidimensional words.
• Low complexity functions and convex sets in \(\mathbb{Z}^k\)
• Local configurations in a discrete plane
• On the Exact Complexity of String Matching: Lower Bounds
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• Two-Dimensional Periodicity in Rectangular Arrays
• Alphabet-Independent Two-Dimensional Witness Computation
• Uniqueness Theorems for Periodic Functions
• The rectangle complexity of functions on two-dimensional lattices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On a conjecture on bidimensional words.