Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952295 | Theoretical Computer Science | 2017 | 26 Pages |
Abstract
We introduce and study natural derivatives for Christoffel and standard words, as well as for characteristic Sturmian words. These derivatives, which are defined as inverse images under suitable morphisms, preserve the aforementioned classes of words. In the case of Christoffel words, the morphisms involved map a to ak+1b (resp., abk) and b to akb (resp., abk+1) for a suitable k>0. As long as derivatives are not just a single letter, higher-order derivatives are naturally obtained. We define the depth of a Christoffel or of a 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alma D'Aniello, Aldo de Luca, Alessandro De Luca,