Specifying periodic words by restrictions
- 作者: Lavrov P.A.1
-
隶属关系:
- Mechanics and Mathematics Faculty
- 期: 卷 93, 编号 3 (2016)
- 页面: 300-303
- 栏目: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/223783
- DOI: https://doi.org/10.1134/S1064562416030224
- ID: 223783
如何引用文章
详细
Consider a periodic sequence over a finite alphabet, say ..ababab.... This sequence can be specified by prohibiting the subwords aa and bb. In the paper, the maximum period of a word that can be defined by using k restrictions is determined. A sharp exponential bound is obtained: the period of a word determined by k restrictions cannot exceed the kth Fibonacci number. Thus, the period colength is estimated. The problem is studied in the context of Gröbner bases, namely, the growth of a Gröbner basis of an ideal (the cogrowth of an algebra). The proof uses the technique of Rauzy graphs.
作者简介
P. Lavrov
Mechanics and Mathematics Faculty
编辑信件的主要联系方式.
Email: msuorange@gmail.com
俄罗斯联邦, Moscow, 119991
补充文件
