Recurrence along directions in multidimensional words

DOI10.1016/J.DISC.2020.112006zbMATH Open1477.68249arXiv1907.00192OpenAlexW3037889731MaRDI QIDQ785801FDOQ785801

Authors: Émilie Charlier, Svetlana Puzynina, Élise Vandomme 

Publication date: 12 August 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: In this paper we introduce and study new notions of uniform recurrence in multidimensional words. A $d$-dimensional word is called emph{uniformly recurrent} if for all $(s_1,ldots,s_d)inmathbb{N}^d$ there exists $ninmathbbN$ such that each block of size $(n,ldots,n)$ contains the prefix of size $(s_1,ldots,s_d)$. We are interested in a modification of this property. Namely, we ask that for each rational direction $(q_1,ldots,q_d)$, each rectangular prefix occurs along this direction in positions $ell(q_1,ldots,q_d)$ with bounded gaps. Such words are called emph{uniformly recurrent along all directions}. We provide several constructions of multidimensional words satisfying this condition, and more generally, a series of four increasingly stronger conditions. In particular, we study the uniform recurrence along directions of multidimentional rotation words and of fixed points of square morphisms.

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

Recommendations

• Recurrence in multidimensional words
• On uniform recurrence of a direct product
• Maximal pattern complexity of higher dimensional words
• REPETITIONS, FULLNESS, AND UNIFORMITY IN TWO-DIMENSIONAL WORDS
• Balance properties of multi-dimensional words

zbMATH Keywords

uniform recurrencemultidimensional morphismsmultidimensional words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics in computer science (68R05) Combinatorics on words (68R15)

Cites Work

• Poincaré recurrence and number theory
• A characterization of substitutive sequences using return words
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Palindromes and two-dimensional Sturmian sequences
• Four encounters with Sierpiński's gasket
• Title not available (Why is that?)
• Tilings and rotations on the torus: A two-dimensional generalization of Sturmian sequences
• On additive properties of sets defined by the Thue-Morse word
• Multidimensional extension of the Morse-Hedlund theorem
• Infinite words with uniform frequencies, and invariant measures
• Combinatoire des codages de rotations
• Nonexpansive \(\mathbb{Z}^{2}\)-subdynamics and Nivat's conjecture
• Towards a characterization of self-similar tilings in terms of derived Voronoï tessellations
• A primer of substitution tilings of the Euclidean plane
• Combinatorics on patterns of a bidimensional Sturmian sequence
• Title not available (Why is that?)
• On successive settings of an arc on the circumference of a circle
• Multidimensional generalized automatic sequences and shape-symmetric morphic words
• Presburgerness of predicates regular in two number systems
• The definable criterion for definability in Presburger arithmetic and its applications.
• A self-similar aperiodic set of 19 Wang tiles
• On uniform recurrence of a direct product

Cited In (5)

• REPETITIONS, FULLNESS, AND UNIFORMITY IN TWO-DIMENSIONAL WORDS
• Title not available (Why is that?)
• Recurrence in multidimensional words
• Title not available (Why is that?)
• On uniform recurrence of a direct product

This page was built for publication: Recurrence along directions in multidimensional words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q785801)