Maximizing T-complexity

• Autorzy: Clark G. , Teutsch J.

Identyfikatory

DOI

10.3233/FI-2015-1223

• Języki publikacji: EN

Abstrakty

EN

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 Tcomplexity.

Słowa kluczowe

EN

computer algorithms; information theory; Kolmogorov complexity; sequences; set theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 139, nr 1
• Strony: 1--19
• Opis fizyczny: Bibliogr. 23 poz., tab.

Twórcy

autor

Clark G.

• U.S. Department of Defense Washington, DC 20301-1400, USA

autor

Teutsch J.

• Penn State University University Park, PA 16082, USA

Bibliografia

• [1] van Aardenne-Ehrenfest, T., de Bruijn, N. G.: Circuits and trees in oriented linear graphs, Simon Stevin, 28, 1951, 203–217, ISSN 0037-5454.
• [2] Calude, C. S., Salomaa, K., Roblot, T. K.: Finite-State Complexity and Randomness, Technical Report 374, University of Auckland CDMTCS Research Report Series, December 2009.
• [3] Chebolu, S. K.,Min´aˇc, J.: Counting Irreducible Polynomials over Finite Fields Using the Inclusion-Exclusion Principle, Mathematics Magazine, 84(5), 2011, 369–371.
• [4] Eimann, R., Speidel, U., Brownlee, N., Yang, J.: Network Event Detection with T-Entropy, CDMTCS Research Report Series, 266, 2005.
• [5] Eimann, R. E. A.: Network event detection with entropy measures, Ph.D. Thesis, The University of Auckland, 2008.
• [6] Gulliver, T. A.,Makwakwa, I., Speidel, U.: On the Generation of Aperiodic and Periodic Necklaces via T-augmentation, Fundamenta Informaticae, 83(1-2), 2008, 91–107, ISSN 0169-2968.
• [7] Hamano, K., Yamamoto, H.: A differential equation method to derive the formulas of the Tcomplexity and the LZ-complexity, Proceedings of the 2009 IEEE international conference on Symposium on Information Theory - Volume 1, ISIT 2009, IEEE Press, Piscataway, NJ, USA, 2009, ISBN 978-1-4244-4312-3.
• [8] Ireland, K., Rosen, M.: A Classical Introduction to Modern Number Theory, Number 84 in Graduate Texts in Mathematics, second edition, Springer-Verlag, New York, 1990, ISBN 0-387-97329X.
• [9] Lempel, A., Ziv, J.: On the complexity of finite sequences, IEEE Transactions on Information Theory, IT-22(1), 1976, 75–81, ISSN 0018-9448.
• [10] Li, M., Vit´anyi, P.: An introduction to Kolmogorov complexity and its applications, Texts in Computer Science, third edition, Springer, New York, 2008, ISBN 978-0-387-33998-6.
• [11] Li, M., Vitányi, P. M. B.: Statistical properties of finite sequences with high Kolmogorov complexity, Mathematical Systems Theory, 27(4), 1994, 365–376, ISSN 0025-5661.
• [12] Matoušek, J., Nešetřil, J.: Invitation to discrete mathematics, Second edition, Oxford University Press, Oxford, 2009, ISBN 978-0-19-857042-4.
• [13] Moreau, C.: Sur les permutations circulaires distinctes, Nouvelles annalles de mathématiques, 2(11), 1872, 309–314.
• [14] Niven, I., Zuckerman, H. S., Montgomery, H. L.: An introduction to the theory of numbers, Fifth edition, John Wiley & Sons Inc., New York, 1991, ISBN 0-471-62546-9.
• [15] Speidel, U.: T-Complexity and T-Information Theory–an Executive Summary, 2nd revised version, Technical Report 286, University of Auckland CDMTCS Research Report Series, October 2006.
• [16] Speidel, U.: On the bounds of the Titchener T-complexity, Proceedings of Communication Systems, Networks and Digital Signal Processing 2008, CNSDSP 2008, July 2008.
• [17] Titchener, M. R.: Digital encoding by means of new T-codes to provide improved data synchronization and message integrity, July 1984, Technichal note.
• [18] Titchener, M. R., Nicolescu, R., Staiger, L., Gulliver, A., Speidel, U.: Deterministic Complexity and Entropy, Fundamenta Informaticae, 64(1-4), 2004, 443–461, ISSN 0169-2968.
• [19] Welch, T. A.: A Technique for High-Performance Data Compression, Computer, 17(6), june 1984, 8–19, ISSN 0018-9162.
• [20] Xie, S. Q.: Notes on de Bruijn sequences, Discrete Applied Mathematics, 16(2), 1987, 157–177, ISSN 0166-218X.
• [21] Ziv, J., Lempel, A.: A universal algorithm for sequential data compression, IEEE Transactions on Information Theory, 23(3), may 1977, 337–343, ISSN 0018-9448.
• [22] Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding, IEEE Transactions on Information Theory, 24(5), september 1978, 530–536, ISSN 0018-9448.
• [23] Zvonkin, A. K., Levin, L. A.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms., Russian Mathematical Surveys, 25(6), 1970, 83–124.