Source author record

Aldo de Luca

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Formal Languages and Automata Theory

Catalog footprint

Research overview

9works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On Christoffel and standard words and their derivatives

We introduce and study natural derivatives for Christoffel and finite standard words, as well as for characteristic Sturmian words. These derivatives, which are realized as inverse images under suitable morphisms, preserve the aforementioned classes of words. In the case of Christoffel words, the morphisms involved map $a$ to $a^{k+1}b$ (resp.,~ $ab^{k}$ ) and $b$ to $a^{k}b$ (resp.,~ $ab^{k+1}$ ) for a suitable $k>0$ . As long as derivatives are longer than one letter, higher-order derivatives are naturally obtained. We define the depth of a Christoffel or standard word as the smallest order for which the derivative is a single letter. We give several combinatorial and arithmetic descriptions of the depth, and (tight) lower and upper bounds for it.

preprint2015arXiv

On prefixal factorizations of words

We consider the class ${\cal P}_1$ of all infinite words $x\in A^ω$ over a finite alphabet $A$ admitting a prefixal factorization, i.e., a factorization $x= U_0 U_1U_2 \cdots$ where each $U_i$ is a non-empty prefix of $x.$ With each $x\in {\cal P}_1$ one naturally associates a "derived" infinite word $δ(x)$ which may or may not admit a prefixal factorization. We are interested in the class ${\cal P}_{\infty}$ of all words $x$ of ${\cal P}_1$ such that $δ^n(x) \in {\cal P}_1$ for all $n\geq 1$ . Our primary motivation for studying the class ${\cal P}_{\infty}$ stems from its connection to a coloring problem on infinite words independently posed by T. Brown in \cite{BTC} and by the second author in \cite{LQZ}. More precisely, let ${\bf P}$ be the class of all words $x\in A^ω$ such that for every finite coloring $φ: A^+ \rightarrow C$ there exist $c\in C$ and a factorization $x= V_0V_1V_2\cdots$ with $φ(V_i)=c$ for each $i\geq 0.$ In \cite{DPZ} we conjectured that a word $x\in {\bf P}$ if and only if $x$ is purely periodic. In this paper we show that ${\bf P}\subseteq {\cal P}_{\infty},$ so in other words, potential candidates to a counter-example to our conjecture are amongst the non-periodic elements of ${\cal P}_{\infty}.$ We establish several results on the class ${\cal P}_{\infty}$ . In particular, we show that a Sturmian word $x$ belongs to ${\cal P}_{\infty}$ if and only if $x$ is nonsingular, i.e., no proper suffix of $x$ is a standard Sturmian word.

preprint2015arXiv

On some variations of coloring problems of infinite words

Given a finite coloring (or finite partition) of the free semigroup $A^+$ over a set $A$ , we consider various types of monochromatic factorizations of right sided infinite words $x\in A^ω$ . Some stronger versions of the usual notion of monochromatic factorization are introduced. A factorization is called sequentially monochromatic when concatenations of consecutive blocks are monochromatic. A sequentially monochromatic factorization is called ultra monochromatic if any concatenation of arbitrary permuted blocks of the factorization has the same color of the single blocks. We establish links, and in some cases equivalences, between the existence of these factorizations and fundamental results in Ramsey theory including the infinite Ramsey theorem, Hindman's finite sums theorem, partition regularity of IP sets and the Milliken-Taylor theorem. We prove that for each finite set $A$ and each finite coloring $φ: A^+\rightarrow C,$ for almost all words $x\in A^ω,$ there exists $y$ in the subshift generated by $x$ admitting a $φ$ -ultra monochromatic factorization, where "almost all" refers to the Bernoulli measure on $A^ω.$

preprint2014arXiv

A Coloring Problem for Infinite Words

In this paper we consider the following question in the spirit of Ramsey theory: Given $x\in A^ω,$ where $A$ is a finite non-empty set, does there exist a finite coloring of the non-empty factors of $x$ with the property that no factorization of $x$ is monochromatic? We prove that this question has a positive answer using two colors for almost all words relative to the standard Bernoulli measure on $A^ω.$ We also show that it has a positive answer for various classes of uniformly recurrent words, including all aperiodic balanced words, and all words $x\in A^ω$ satisfying $λ_x(n+1)-λ_x(n)=1$ for all $n$ sufficiently large, where $λ_x(n)$ denotes the number of distinct factors of $x$ of length $n.$

preprint2014arXiv

Sturmian words and the Stern sequence

Central, standard, and Christoffel words are three strongly interrelated classes of binary finite words which represent a finite counterpart of characteristic Sturmian words. A natural arithmetization of the theory is obtained by representing central and Christoffel words by irreducible fractions labeling respectively two binary trees, the Raney (or Calkin-Wilf) tree and the Stern-Brocot tree. The sequence of denominators of the fractions in Raney's tree is the famous Stern diatomic numerical sequence. An interpretation of the terms $s(n)$ of Stern's sequence as lengths of Christoffel words when $n$ is odd, and as minimal periods of central words when $n$ is even, allows one to interpret several results on Christoffel and central words in terms of Stern's sequence and, conversely, to obtain a new insight in the combinatorics of Christoffel and central words by using properties of Stern's sequence. One of our main results is a non-commutative version of the "alternating bit sets theorem" by Calkin and Wilf. We also study the length distribution of Christoffel words corresponding to nodes of equal height in the tree, obtaining some interesting bounds and inequalities.

preprint2013arXiv

A Coloring Problem for Sturmian and Episturmian Words

We consider the following open question in the spirit of Ramsey theory: Given an aperiodic infinite word $w$ , does there exist a finite coloring of its factors such that no factorization of $w$ is monochromatic? We show that such a coloring always exists whenever $w$ is a Sturmian word or a standard episturmian word.

preprint2012arXiv

A generalized palindromization map in free monoids

The palindromization map $ψ$ in a free monoid $A^*$ was introduced in 1997 by the first author in the case of a binary alphabet $A$ , and later extended by other authors to arbitrary alphabets. Acting on infinite words, $ψ$ generates the class of standard episturmian words, including standard Arnoux-Rauzy words. In this paper we generalize the palindromization map, starting with a given code $X$ over $A$ . The new map $ψ_X$ maps $X^*$ to the set $PAL$ of palindromes of $A^*$ . In this way some properties of $ψ$ are lost and some are saved in a weak form. When $X$ has a finite deciphering delay one can extend $ψ_X$ to $X^ω$ , generating a class of infinite words much wider than standard episturmian words. For a finite and maximal code $X$ over $A$ , we give a suitable generalization of standard Arnoux-Rauzy words, called $X$ -AR words. We prove that any $X$ -AR word is a morphic image of a standard Arnoux-Rauzy word and we determine some suitable linear lower and upper bounds to its factor complexity. For any code $X$ we say that $ψ_X$ is conservative when $ψ_X(X^{*})\subseteq X^{*}$ . We study conservative maps $ψ_X$ and conditions on $X$ assuring that $ψ_X$ is conservative. We also investigate the special case of morphic-conservative maps $ψ_{X}$ , i.e., maps such that $ϕ\circ ψ= ψ_X\circ ϕ$ for an injective morphism $ϕ$ . Finally, we generalize $ψ_X$ by replacing palindromic closure with $θ$ -palindromic closure, where $θ$ is any involutory antimorphism of $A^*$ . This yields an extension of the class of $θ$ -standard words introduced by the authors in 2006.

preprint2012arXiv

Some extremal properties of the Fibonacci word

We prove that the Fibonacci word $f$ satisfies among all characteristic Sturmian words, three interesting extremal properties. The first concerns the length and the second the minimal period of its palindromic prefixes. Each of these two properties characterizes $f$ up to a renaming of its letters. A third property concerns the number of occurrences of the letter $b$ in its palindromic prefixes. It characterizes uniquely $f$ among all characteristic Sturmian words having the prefix $abaa$ .

preprint2008arXiv

Rich, Sturmian, and trapezoidal words

In this paper we explore various interconnections between rich words, Sturmian words, and trapezoidal words. Rich words, first introduced in arXiv:0801.1656 by the second and third authors together with J. Justin and S. Widmer, constitute a new class of finite and infinite words characterized by having the maximal number of palindromic factors. Every finite Sturmian word is rich, but not conversely. Trapezoidal words were first introduced by the first author in studying the behavior of the subword complexity of finite Sturmian words. Unfortunately this property does not characterize finite Sturmian words. In this note we show that the only trapezoidal palindromes are Sturmian. More generally we show that Sturmian palindromes can be characterized either in terms of their subword complexity (the trapezoidal property) or in terms of their palindromic complexity. We also obtain a similar characterization of rich palindromes in terms of a relation between palindromic complexity and subword complexity.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.