Specifying periodic words by restrictions
- Authors: Lavrov P.A.1
-
Affiliations:
- Mechanics and Mathematics Faculty
- Issue: Vol 93, No 3 (2016)
- Pages: 300-303
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/223783
- DOI: https://doi.org/10.1134/S1064562416030224
- ID: 223783
Cite item
Abstract
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.
About the authors
P. A. Lavrov
Mechanics and Mathematics Faculty
Author for correspondence.
Email: msuorange@gmail.com
Russian Federation, Moscow, 119991