Maximizing T-complexity

Article type: Research Article

Authors: Clark, Gregory^{a; *} | Teutsch, Jason^b

Affiliations: [a] U.S. Department of Defense, Washington, DC 20301-1400, USA. gsclark@tycho.ncsc.mil | [b] Penn State University, University Park, PA 16082, USA. teutsch@cse.psu.edu

Note: [*] Address for correspondence: U.S. Department of Defense, Washington, DC 20301-1400, USA.

Abstract: We investigate Mark Titchener’s T-complexity, an algorithm which measures the information content of finite strings. After introducing the T-complexity algorithm, we turn our attention to a particular class of “simple” finite strings. By exploiting special properties of simple strings, we obtain a fast algorithm to compute the maximum T-complexity among strings of a given length, and our estimates of these maxima show that T-complexity differs asymptotically from Kolmogorov complexity. Finally, we examine how closely de Bruijn sequences resemble strings with high T-complexity.

DOI: 10.3233/FI-2015-1223

Journal: Fundamenta Informaticae, vol. 139, no. 1, pp. 1-19, 2015