An analytic upper bound on T-complexity
Ulrich Speidel, Thomas Aaron Gulliver · 2012
The Titchener T-complexity CTof a string has applications in, e.g., randomness testing, event detection and similarity comparison. Like the Lempel-Ziv production complexity, the upper bound of CTis demonstrably not a linear function of the string length. Knowledge of the bound for a given length is however required in order to convert CTinto a measure with linear upper bound such as Titchener's T-information. For this reason, the upper bound of CThas been investigated before by several authors, with various asymptotic solutions proposed. We present a new analytic closed-form asymptotic upper bound for CTbased on the Hurwitz-Lerch zeta function.