Abstract

The exponent of periodicity is a key parameter used in all currently known algorithms for solving word equations. A lower bound for it is 2c|E|, where |E| is the length of the equation E. We prove that in fixed dimension, i.e. when the variables belong to a fixed set V, the exponent of periodicity can be bound by a polynomial p(|E|) of degree no more than thrice the size of the set V.