BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Aldo de Luca contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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.
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.
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$.
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.