Dr. Francesco Dolce

Publikace

On balanced sequences and their critical exponent

Autoři
Dvořáková, L.; Dolce, F.; Pelantová, E.
Rok
2023
Publikováno
Theoretical Computer Science. 2023, 939 18-47. ISSN 0304-3975.
Typ
Článek
Anotace
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 show that the language of v is eventually dendric and we focus on return words to its factors. We deduce a method computing critical exponent and asymptotic critical exponent of balanced sequences provided the associated Sturmian sequence u has a quadratic slope. The method is based on looking for the shortest return words to bispecial factors in v. We illustrate our method on several examples, in particular we confirm a conjecture of Rampersad, Shallit and Vandomme that two specific sequences have the least critical exponent among all balanced sequences over 9- resp. 10-letter alphabets.

Column Representation of Sturmian Words in Cellular Automata

Autoři
Dolce, F.; Tahay, P.
Rok
2022
Publikováno
Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2022. p. 127-138. ISSN 0302-9743. ISBN 978-3-031-05577-5.
Typ
Stať ve sborníku
Anotace
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

Autoři
Dolce, F.; Pelantová, E.
Rok
2022
Publikováno
Fundamenta Informaticae. 2022, 185(1), 1-25. ISSN 0169-2968.
Typ
Článek
Anotace
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

Autoři
Dolce, F.; Perrin, D.
Rok
2021
Publikováno
Ergodic Theory and Dynamical Systems. 2021, 41(7), 2023-2048. ISSN 0143-3857.
Typ
Článek
Anotace
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

Autoři
Dolce, F.; Dvořáková, L.; Pelantová, E.
Rok
2021
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.