Specifying Periodic Words by Restrictions

P. A. Lavrov

Presented by Academician A.L. Semenov April 10, 2015

Received December 11, 2015

Abstract—Consider a periodic sequence over a finite alphabet, say ..ababab… . This sequence can be speci-
fied 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.

DOI: 10.1134/S1064562416030224

Pleiades Publishing home page | journal home page | top

If you have any problems with this server, contact webmaster.