On Christoffel and standard words and their derivatives

详细信息    查看全文

• 作者：Alma D'Aniello^a ; ^{alma.daniello@unina.it} ; Aldo de Luca^a ; ¹ ; ^{aldo.deluca@unina.it} ; Alessandro De Luca^b ; ² ; ^{alessandro.deluca@unina.it}
• 关键词：Christoffel word ; Standard word ; Central word ; Characteristic word ; Derivative of a word
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：7 January 2017
• 年：2017
• 卷：658
• 期：part_PA
• 页码：122-147
• 全文大小：643 K
• 卷排序：658

文摘

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+1bak+1b (resp., abkabk) and b   to akbakb (resp., abk+1abk+1) for a suitable k>0k>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.