Luca Q. Zamboni
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Luca Q. Zamboni has a total of 32 co-authors. Here are the top co-authors by number of shared publications:
- Anna E. Frid
Aix Marseille Univ CNRS Centrale Marseille I2M Marseille France
5 shared publications - Svetlana Puzynina
Saint Petersburg State University
4 shared publications - Julien Cassaigne
UMR 7373 CNRS Aix Marseille Université I2M 13331 Marseille France
3 shared publications - Caïus Wojcik
UMR 5208 Université de Lyon Université Lyon 1 CNRS Institut Camille Jordan 43 boulevard du 11 novembre 1918 F69622 Villeurbanne Cedex France
2 shared publications - Kalle Saari
Department of Mathematics, University of Turku, 20014 Turku, Finland
2 shared publications - Neil Hindman
Department of Mathematics, Howard University, Washington, USA
2 shared publications
Latest Publications
- Open Access
Clustering and Arnoux-Rauzy words
We characterize the clustering of a word under the Burrows-Wheeler transform in terms of the resolution of a bounded number of bispecial factors belonging to the language generated by all its powers. We use this criterion to compute, in every given Arnoux-Rauzy language on three letters, an explicit bound $K$ such that each word of length at least $K$ is not clustering; this bound is sharp for a set of Arnoux-Rauzy languages including the Tribonacci one. In the other direction, we characterize all standard Arnoux-Rauzy clustering words, and all perfectly clustering Arnoux-Rauzy words. We extend some results to episturmian languages, characterizing those which produce infinitely many clustering words, and to larger alphabets.Open AccessClustering and Arnoux-Rauzy words
We characterize the clustering of a word under the Burrows-Wheeler transform in terms of the resolution of a bounded number of bispecial factors belonging to the language generated by all its powers. We use this criterion to compute, in every given Arnoux-Rauzy language on three letters, an explicit bound $K$ such that each word of length at least $K$ is not clustering; this bound is sharp for a set of Arnoux-Rauzy languages including the Tribonacci one. In the other direction, we characterize all standard Arnoux-Rauzy clustering words, and all perfectly clustering Arnoux-Rauzy words. We extend some results to episturmian languages, characterizing those which produce infinitely many clustering words, and to larger alphabets. - 11 February 2023
- Published by Wiley in Mathematika
- Vol. 69 (2) , 432-457
Extremal values of semi‐regular continuants and codings of interval exchange transformations
- 11 February 2023
- Published by Wiley in Mathematika
- Vol. 69 (2) , 432-457
Extremal values of semi‐regular continuants and codings of interval exchange transformations
- Open Access
Languages of general interval exchange transformations
The languages generated by interval exchange transformations have been characterized by Ferenczi-Zamboni (2008) and Belov-Cernyatev (2010) under some extra conditions on the system. Lifting these conditions leads us to consider successively natural codings of standard interval exchange transformations, natural codings of affine interval exchange transformations, grouped codings of affine interval exchange transformations, and natural codings of generalized interval exchange transformations. We show that these four classes of languages are strictly increasing, and give necessary and/or sufficient (but not all equally explicit) combinatorial criteria to describe each of them. These work also, mutatis mutandis, for interval exchanges with flips
Open AccessLanguages of general interval exchange transformations
The languages generated by interval exchange transformations have been characterized by Ferenczi-Zamboni (2008) and Belov-Cernyatev (2010) under some extra conditions on the system. Lifting these conditions leads us to consider successively natural codings of standard interval exchange transformations, natural codings of affine interval exchange transformations, grouped codings of affine interval exchange transformations, and natural codings of generalized interval exchange transformations. We show that these four classes of languages are strictly increasing, and give necessary and/or sufficient (but not all equally explicit) combinatorial criteria to describe each of them. These work also, mutatis mutandis, for interval exchanges with flips
- Open Access
A Ramsey Characterisation of Eventually Periodic Words
A factorisation $x = u_1 u_2 \cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic', for a given colouring of the finite words $X^*$ on alphabet $X$, if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^*$ there is a monochromatic factorisation of $x$. On the other hand, it follows from Ramsey's theorem that, for \textit{any} word $x$, for every finite colouring of $X^*$ there is a suffix of $x$ having a monochromatic factorisation. A factorisation $x = u_1 u_2 \cdots$ is called `super-monochromatic' if each word $u_{k_1} u_{k_2} \cdots u_{k_n}$, where $k_1 < \cdots < k_n$, is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^*$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest.Open AccessA Ramsey Characterisation of Eventually Periodic Words
A factorisation $x = u_1 u_2 \cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic', for a given colouring of the finite words $X^*$ on alphabet $X$, if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^*$ there is a monochromatic factorisation of $x$. On the other hand, it follows from Ramsey's theorem that, for \textit{any} word $x$, for every finite colouring of $X^*$ there is a suffix of $x$ having a monochromatic factorisation. A factorisation $x = u_1 u_2 \cdots$ is called `super-monochromatic' if each word $u_{k_1} u_{k_2} \cdots u_{k_n}$, where $k_1 < \cdots < k_n$, is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^*$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest. - 6 September 2021
- Published by Springer Nature
- p. 20-26
Continuants with Equal Values, a Combinatorial Approach
- 6 September 2021
- Published by Springer Nature
- p. 20-26
Continuants with Equal Values, a Combinatorial Approach
- Open Access
- 11 October 2019
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 26 (4) , P4.23
Combining Extensions of the Hales-Jewett Theorem with Ramsey Theory in Other Structures
The Hales-Jewett Theorem states that given any finite nonempty set ${\mathbb A}$ and any finite coloring of the free semigroup $S$ over the alphabet ${\mathbb A}$ there is a variable word over ${\mathbb A}$ all of whose instances are the same color. This theorem has some extensions involving several distinct variables occurring in the variable word. We show that, when combined with a sufficiently well behaved homomorphism, the relevant variable word simultaneously satisfies a Ramsey-Theoretic conclusion in the other structure. As an example we show that if $\tau$ is the homomorphism from the set of variable words into the natural numbers which associates to each variable word $w$ the number of occurrences of the variable in $w$, then given any finite coloring of $S$ and any infinite sequence of natural numbers, there is a variable word $w$ whose instances are monochromatic and $\tau(w)$ is a sum of distinct members of the given sequence.Our methods rely on the algebraic structure of the Stone-Čech compactification of $S$ and the other semigroups that we consider. We show for example that if $\tau$ is as in the paragraph above, there is a compact subsemigroup $P$ of $\beta{\mathbb N}$ which contains all of the idempotents of $\beta{\mathbb N}$ such that, given any $p\in P$, any $A\in p$, and any finite coloring of $S$, there is a variable word $w$ whose instances are monochromatic and $\tau(w)\in A$.We end with a new short algebraic proof of an infinitary extension of the Graham-Rothschild Parameter Sets Theorem.- 11 October 2019
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 26 (4) , P4.23
Open AccessCombining Extensions of the Hales-Jewett Theorem with Ramsey Theory in Other Structures
The Hales-Jewett Theorem states that given any finite nonempty set ${\mathbb A}$ and any finite coloring of the free semigroup $S$ over the alphabet ${\mathbb A}$ there is a variable word over ${\mathbb A}$ all of whose instances are the same color. This theorem has some extensions involving several distinct variables occurring in the variable word. We show that, when combined with a sufficiently well behaved homomorphism, the relevant variable word simultaneously satisfies a Ramsey-Theoretic conclusion in the other structure. As an example we show that if $\tau$ is the homomorphism from the set of variable words into the natural numbers which associates to each variable word $w$ the number of occurrences of the variable in $w$, then given any finite coloring of $S$ and any infinite sequence of natural numbers, there is a variable word $w$ whose instances are monochromatic and $\tau(w)$ is a sum of distinct members of the given sequence.Our methods rely on the algebraic structure of the Stone-Čech compactification of $S$ and the other semigroups that we consider. We show for example that if $\tau$ is as in the paragraph above, there is a compact subsemigroup $P$ of $\beta{\mathbb N}$ which contains all of the idempotents of $\beta{\mathbb N}$ such that, given any $p\in P$, any $A\in p$, and any finite coloring of $S$, there is a variable word $w$ whose instances are monochromatic and $\tau(w)\in A$.We end with a new short algebraic proof of an infinitary extension of the Graham-Rothschild Parameter Sets Theorem. - Open Access
$ω$-Lyndon words
Let $\A$ be a finite non-empty set and $\preceq $ a total order on $\A^\nats$ verifying the following lexicographic like condition: For each $n\in \nats$ and $u, v\in \A^n,$ if $u^\omega \prec v^\omega$ then $ux\prec vy$ for all $x, y \in \A^\nats.$ A word $x\in \A^\nats$ is called $\omega$-Lyndon if $x\prec y$ for each proper suffix $y$ of $x.$ A finite word $w\in \A^+$ is called $\omega$-Lyndon if $w^\omega \prec v^\omega$ for each proper suffix $v$ of $w.$ In this note we prove that every infinite word may be written uniquely as a non-increasing product of $\omega$-Lyndon words.Open Access$ω$-Lyndon words
Let $\A$ be a finite non-empty set and $\preceq $ a total order on $\A^\nats$ verifying the following lexicographic like condition: For each $n\in \nats$ and $u, v\in \A^n,$ if $u^\omega \prec v^\omega$ then $ux\prec vy$ for all $x, y \in \A^\nats.$ A word $x\in \A^\nats$ is called $\omega$-Lyndon if $x\prec y$ for each proper suffix $y$ of $x.$ A finite word $w\in \A^+$ is called $\omega$-Lyndon if $w^\omega \prec v^\omega$ for each proper suffix $v$ of $w.$ In this note we prove that every infinite word may be written uniquely as a non-increasing product of $\omega$-Lyndon words. - Open Access
- 3 April 2019
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 147 (7) , 3103-3115
A characterization of words of linear complexity
Given an infinite word $x=x_0x_1x_2\cdots \in \mathbb {A}^\mathbb {N}$ over some finite alphabet $\mathbb {A},$ the factor complexity $p_x(n)$ counts the number of distinct factors of $x$ of each given length $n,$ i.e., the number of distinct blocks $x_ix_{i+1}\cdots x_{i+n-1}\in \mathbb {A}^n$ occurring in $x.$ The factor complexity provides a useful measure of the extent of randomness of $x$: periodic words have bounded factor complexity while digit expansions of normal numbers have maximal complexity. In this paper we obtain a new characterization of infinite words $x$ of sublinear complexity, namely we show that $p_x(n)=O(n)$ if and only if there exists a set $S\subseteq \mathbb {A}^*$ of bounded complexity (meaning $\limsup p_S(n)<+\infty )$ such that each factor $w$ of $x$ is a concatenation of two elements of $S,$ i.e., $w=uv$ with $u,v \in S.$ In the process we introduce the notions of marker words and marker sets which are both new and may be of independent interest. Marker sets defined by right special factors constitute the key tool needed to split each factor of an infinite word of linear complexity into two pieces.- 3 April 2019
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 147 (7) , 3103-3115
Open AccessA characterization of words of linear complexity
Given an infinite word $x=x_0x_1x_2\cdots \in \mathbb {A}^\mathbb {N}$ over some finite alphabet $\mathbb {A},$ the factor complexity $p_x(n)$ counts the number of distinct factors of $x$ of each given length $n,$ i.e., the number of distinct blocks $x_ix_{i+1}\cdots x_{i+n-1}\in \mathbb {A}^n$ occurring in $x.$ The factor complexity provides a useful measure of the extent of randomness of $x$: periodic words have bounded factor complexity while digit expansions of normal numbers have maximal complexity. In this paper we obtain a new characterization of infinite words $x$ of sublinear complexity, namely we show that $p_x(n)=O(n)$ if and only if there exists a set $S\subseteq \mathbb {A}^*$ of bounded complexity (meaning $\limsup p_S(n)<+\infty )$ such that each factor $w$ of $x$ is a concatenation of two elements of $S,$ i.e., $w=uv$ with $u,v \in S.$ In the process we introduce the notions of marker words and marker sets which are both new and may be of independent interest. Marker sets defined by right special factors constitute the key tool needed to split each factor of an infinite word of linear complexity into two pieces. - Open Access
Open and closed factors of Arnoux-Rauzy words
A finite word $u$ is called closed if its longest repeated prefix has exactly two occurrences in $u,$ once as a prefix and once as a suffix. We study the function $f_x^c:\mathbb N \rightarrow \mathbb N$ which counts the number of closed factors of each length in an infinite word $x.$ We derive an explicit formula for $f_x^c$ in case $x$ is an Arnoux-Rauzy word. As a consequence we prove that $\liminf _{n\rightarrow \infty}f_x^c(n)=+\infty.$Open AccessOpen and closed factors of Arnoux-Rauzy words
A finite word $u$ is called closed if its longest repeated prefix has exactly two occurrences in $u,$ once as a prefix and once as a suffix. We study the function $f_x^c:\mathbb N \rightarrow \mathbb N$ which counts the number of closed factors of each length in an infinite word $x.$ We derive an explicit formula for $f_x^c$ in case $x$ is an Arnoux-Rauzy word. As a consequence we prove that $\liminf _{n\rightarrow \infty}f_x^c(n)=+\infty.$ - 1 January 2019
- Published by Societe Mathematique de France in Bulletin de la Société Mathématiques de France
- Vol. 147 (4) , 639-660
Cost and dimension of words of zero topological entropy
- 1 January 2019
- Published by Societe Mathematique de France in Bulletin de la Société Mathématiques de France
- Vol. 147 (4) , 639-660
Cost and dimension of words of zero topological entropy