Envelope Words and the Reflexivity of the Return Word Sequences in the Period-doubling Sequence

2017/03/21 by Yuke Huang, Huang, Yu-Ke, Zhi-Ying Wen +1 · 1 citation
Computer Science · #semigroups and automata theory #Natural Language Processing Techniques #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.1703.07157

Abstract

We consider the infinite one-sided sequence over alphabet \a,b\ generated by the period-doubling substitution σ(a)=ab and σ(b)=aa, denoted by \mathbbD. Let r_p(ω) be the p-th return word of factor ω. The main result of this paper is twofold. (1) For any factor ω in \mathbbD, the return word sequence \r_p(ω)\_p≥1 is Θ₁ or Θ₂. Both of them are substitutive sequences and determined completely in this paper. (2) For any factor ω in Θ₁ (resp. Θ₂), the return word sequence \r_p(ω)\_p≥1 is still Θ₁ or Θ₂. We call it the reflexivity property of the return word sequence. As an application, we introduce a notion of spectrum for studying some typical combinatorial properties, such as separated, adjacent and overlapped.

Cited by

• Derivated sequences of complementary symmetric Rote sequences

Related

• Envelope Words and Return Words Sequences in the Period-doubling Sequence
• Envelope Word and Gap Sequence in Doubling Sequence
• A new factorization of the generalized period-doubling sequences through kernel words and gaps sequences
• The analogue of overlap-freeness for the period-doubling sequence
• Sequences with constant number of return words