Recurrence along directions in multidimensional words

DOI10.1016/J.DISC.2020.112006MaRDI QIDQ785801zbMATH OpenOpenAlexFDO

Authors Émilie Charlier, Svetlana Puzynina, Élise Vandomme

Publication date 12 August 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

uniform recurrencemultidimensional morphismsmultidimensional words

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(5)

• On uniform recurrence of a direct product
• REPETITIONS, FULLNESS, AND UNIFORMITY IN TWO-DIMENSIONAL WORDS
• scientific article; zbMATH DE number 6861068 (Why is no real title available?)
• Recurrence in multidimensional words
• scientific article; zbMATH DE number 3943055 (Why is no real title available?)

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)