Specifying periodic words by restrictions
- Авторы: Lavrov P.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