黄煜可,文志英.因子谱与诱导序列[J].数学研究及应用,2019,39(6):718~732
因子谱与诱导序列
The Factor Spectrum and Derived Sequence
投稿时间:2019-08-15  修订日期:2019-10-10
DOI:10.3770/j.issn:2095-2651.2019.06.015
中文关键词:  核词  包络词  回归词  诱导序列  因子谱
英文关键词:kernel word  envelope word  return word  derived sequence  the factor spectrum
基金项目:国家自然科学基金(Grant Nos.11701024; 11431007).
作者单位
黄煜可 北京邮电大学理学院, 北京 100876 
文志英 清华大学数学科学系, 北京 100084 
摘要点击次数: 757
全文下载次数: 505
中文摘要:
      对于任意给定的性质${\mathcal{P}}$和序列$\rho$, 词上的组合领域一个重要的研究课题是找出所有的因子$\omega$和序数$p$,使得序列$\rho$中第$p$次出现的因子$\omega$ (记为$\omega_p$) 满足性质${\mathcal{P}}$.这个问题等价于研究``因子谱''.确定因子谱是一个困难的问题. 为了实现目标,我们引入并研究了一系列的概念:核词、包络词、回归词和任意因子的诱导序列. 利用因子谱和诱导序列,我们可以解决序列中的一些计数问题.例如:在序列的任意一个片段中回文或者高次方词的个数. 本文中,我们将结合几个特殊的序列展示相关的研究结果.这些序列包括: Fibonacci序列、Tribonacci序列、Period-doubling序列等等. 我们相信这些概念和方法对于所有的一致常返序列都是有效的.
英文摘要:
      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.
查看全文  查看/发表评论  下载PDF阅读器