A computational framework for determining square-maximal strings

We investigate the function σd(n) = max{s(x) x is a (d, n)-string}, where s(x) denotes the number of distinct primitively rooted squares in a string x and (d, n)-string denotes a string of length n with exactly d distinct symbols. New properties of the σd(n) function are presented. The notion of s-cover is presented and discussed with emphasis on the recursive computational determination of σd(n). In particular, we were able to determine all …