On the bounds of the Titchener T-complexity
Ulrich Speidel · 2008
Titchenerpsilas T-complexity is a computable complexity measure for finite strings with practical applications in a number of areas ranging from similarity measurement to network event detection. While its lower bound for strings of length L is well known, the corresponding upper bound presents a more difficult problem. Knowledge of this bound is desirable in order to relate computable complexities to notions of information and Shannonpsilas entropy. Beyond practical computability (i.e., short L), a previous result by Titchener, Nicolescu, Staiger, Gulliver, and Speidel based on a special string construction algorithm points at an asymptotic L/ log L bound. This paper revisits this result in the light of a more recently discovered link between the T-complexity computation and the theory of cyclic equivalence classes, confirming some of the assumptions made by Titchener et. al. The paper also offers a non-recursive formulation for their ldquoexhaustion lengthsrdquo and their associated T-complexities.