The Factor Spectrum and Derived Sequence
Received:August 15, 2019  Revised:October 10, 2019
Key Word: kernel word   envelope word   return word   derived sequence   the factor spectrum
Fund ProjectL:Supported by the National Natural Science Foundation of China (Grant Nos.11701024; 11431007).
 Author Name Affiliation Yuke HUANG School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, P. R. China Zhiying WEN Department of Mathematical Sciences, Tsinghua University, Beijing 100084, P. R. China
Hits: 175
Given a sequence $\rho$ over a finite alphabet $\mathcal{A}$, an important topic in combinatorics on words is to find out all factors $\omega$ of $\rho$ and positive integers $p$ such that $\omega_p$ (the $p$-th occurrence of $\omega$) fulfills property ${\mathcal{P}}$. This problem is equivalent to determining a notion called the factor spectrum. Determining the factor spectrum is a difficult problem. To this aim, we introduce several notions, such as: kernel word, envelope word, return word and derived sequence of each factor $\omega$. Using the factor spectrum and derived sequence, we can solve some enumerations of factors, such as the numbers of palindromes, fractional powers, etc. We will show some results for several sequences, such as the Fibonacci sequence, the Tribonacci sequence, the Period-doubling sequence, etc. And we think that these notions and methods are suitable for all recurrent sequences.