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 NameAffiliation
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: 58
Download times: 70
Abstract:
      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.
Citation:
DOI:10.3770/j.issn:2095-2651.2019.06.015
View Full Text  View/Add Comment  Download reader