Column Representation of Sturmian Words in Cellular Automata
Authors
Dolce, F.; Tahay, P.
Year
2022
Published
Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2022. p. 127-138. ISSN 0302-9743. ISBN 978-3-031-05577-5.
Type
Proceedings paper
Departments
Annotation
We prove that, given a Sturmian word w with quadratic slope, it is possible to construct a one-dimensional cellular automaton such that w is represented in a chosen column in its space-time diagram. Our proof is constructive and use the continued fraction expansion of the slope of the word.
On Morphisms Preserving Palindromic Richness
Authors
Dolce, F.; Pelantová, E.
Year
2022
Published
Fundamenta Informaticae. 2022, 185(1), 1-25. ISSN 0169-2968.
Type
Article
Departments
Annotation
Itisknownthateachwordoflengthncontainsatmostn+1distinctpalindromes.A finite rich word is a word with maximal number of palindromic factors. The definition of palin- dromic richness can be naturally extended to infinite words. Sturmian words and Rote comple- mentary symmetric sequences form two classes of binary rich words, while episturmian words and words coding symmetric d-interval exchange transformations give us other examples on larger al- phabets. In this paper we look for morphisms of the free monoid, which allow us to construct new rich words from already known rich words. We focus on morphisms in Class Pret. This class contains morphisms injective on the alphabet and satisfying a particular palindromicity property: for every morphism φ in the class there exists a palindrome w such that φ(a)w is a first complete return word to w for each letter a. We characterize Pret morphisms which preserve richness over a binary alphabet. We also study marked Pret morphisms acting on alphabets with more letters. In particular we show that every Arnoux-Rauzy morphism is conjugated to a morphism in Class Pret and that it preserves richness.
Eventually dendric shift spaces
Authors
Dolce, F.; Perrin, D.
Year
2021
Published
Ergodic Theory and Dynamical Systems. 2021, 41(7), 2023-2048. ISSN 0143-3857.
Type
Article
Departments
Annotation
We define a new class of shift spaces which contains a number of classes
of interest, like Sturmian shifts used in discrete geometry. We show that
this class is closed under two natural transformations. The first one is
called conjugacy and is obtained by sliding block coding. The second one
is called the complete bifix decoding, and typically includes codings by
non overlapping blocks of fixed length.
On Balanced Sequences and Their Asymptotic Critical Exponent
Authors
Dolce, F.; Dvořáková, L.; Pelantová, E.
Year
2021
Published
15th International Conference on Language and Automata Theory and Applications, LATA 2021. Springer Science and Business Media Deutschland GmbH, 2021. p. 293-304. Lecture Notes in Computer Science. vol. 12638. ISSN 0302-9743. ISBN 9783030681944.
Type
Proceedings paper
Departments
Annotation
We study aperiodic balanced sequences over finite alphabets. A sequence v of this type is fully characterised by a Sturmian sequence u and two constant gap sequences y and y′. We study the language of v, with focus on return words to its factors. We provide a uniform lower bound on the asymptotic critical exponent of all sequences v arising by y and y′. It is a counterpart to the upper bound on the least critical exponent of v conjectured and partially proved recently in works of Baranwal, Rampersad, Shallit and Vandomme. We deduce a method computing the exact value of the asymptotic critical exponent of v provided the associated Sturmian sequence u has a quadratic slope. The method is used to compare the critical and the asymptotic critical exponent of balanced sequences over an alphabet of size d≤ 10 which are conjectured by Rampersad et al. to have the least critical exponent.