Envelope Words and Return Words Sequences in the Period-doubling Sequence

2016/06/16 by Yuke, Huang, Zhiying, Wen
Computer Science · #semigroups and automata theory #Algorithms and Data Compression #Natural Language Processing Techniques

paper · pdf · doi:10.48550/arxiv.1606.05150

Abstract

We consider the infinite one-sided sequence generated by the period-doubling substitution σ(a,b)=(ab,aa), denoted by \mathbbD. Since \mathbbD is uniformly recurrent, each factor ω appears infinite many times in the sequence, which is arranged as ω_p (p≥ 1). Let r_p(ω) be the p-th return word over ω. The main result is: for each factor ω, the sequence \r_p(ω)\_p≥1 is Θ₁ or Θ₂, which are substitutive sequences and determined completely in this paper.

Related

• Envelope Words and the Reflexivity of the Return Word 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
• Repetition factorization of automatic sequences