Home
Scholarly Works
A computational framework for determining...
Conference

A computational framework for determining square-maximal strings

Abstract

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 values of σ2(n) for n ≤ 53 and σ3(n) for n ≤ 42 and to point out that σ2(n)(33) < σ3(n)(33); that is, among all strings of length 33, no binary string achieves the maximum number of distinct primitively rooted squares. Noticeably, these computations reveal the unexpected existence of pairs (d,n) satisfying σd+1(n)(n + 2) - σd(n)(n) > 1 such as (2,33) and (2,34), and of three consecutive equal values: σ2(n)(31) = σ2(n)(32) = σ2(n)(33). In addition we show that σ2(n)(11) ≤ 2n - 66 for n ≥ 53. © Czech Technical University in Prague, Czech Republic.

Authors

Deza A; Pranek F; Jiang M

Pagination

pp. 111-119

Publication Date

December 12, 2012

Conference proceedings

Proceedings of the Prague Stringology Conference Psc 2012

Contact the Experts team