Deterministic Complexity and Entropy

• Autorzy: Titchener M. R. , Gulliver A. , Nicolescu R. , Speidel U. , Staiger L.
• Języki publikacji: EN

Abstrakty

EN

Lempel and Ziv (1976) proposed a computable string production-complexity. In this paper, our emphasis is on providing the rigorous development, where possible, for the theoretical aspects of a more recent and contrasting measure of string complexity. We derive expressions for complexity bounds subject to certain constraints. We derive an analytic approximation to the upper bound to linearize the complexity measure. The linearized measure enables us to propose an entropy measure, observed elsewhere to correspond closely with the Kolmogorov-Sinai entropy in simple dynamical systems.

Słowa kluczowe

EN

formal languages; generative systems; prefix codes; complexity measures; T-codes; entropy; information

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 443--461
• Opis fizyczny: Bibliogr. 22 poz., wykr.

Twórcy

autor

Titchener M. R.

• Department of Computer Science, The University of Auckland, Auckland, New Zealand

autor

Gulliver A.

• Dept. of Electrical & Computer Engineering University of Victoria, Canada

autor

Nicolescu R.

• Department of Computer Science, The University of Auckland, Auckland, New Zealand

autor

Speidel U.

• Department of Computer Science, The University of Auckland, Auckland, New Zealand

autor

Staiger L.

• Institut für Informatik Martin-Luther-Universität Halle-Wittenberg, Germany

Bibliografia

• [1] Abramowitz, M., and Stegun, I. A.: Handbook of Mathematical Functions, Dover Publications, Inc., NY, 1965.
• [2] Chaitin, G.: A theory of program size formally identical to information theory, Rep. RC 4805, IBM, Yorktown Heights, N.Y., April 1974.
• [3] Ebeling, W., Steuer, R., Titchener, M. R.: Partition-based entropies of deterministic and stochastic maps, Stochastics and Dynamics, 1(1), 2001, 45–61.
• [4] Günther U.: Robust source coding with generalized T-codes, PhD Thesis, The University of Auckland, 1998, http://www.citr.auckland.ac.nz/~ulrich/pdh.ps.gz.
• [5] Kolmogorov, A. N.: Three approaches to the quantitative definition of information, Probl. Inform. Transmission, 1, 1965, 1–7.
• [6] Lempel, A., and Ziv, J.: On the Complexity of Finite Sequences, IEEE Transactions on Information Theory, 22(1), 1976, 75–81.
• [7] Marcus, S.: Entropie et energie poetique, Cahiers de Linguistique Th´eorique et Appliqu´ee, 4, 1967, 171–180.
• [8] Marcus, S.: On types of meters of a poem and their informational energy, Semiotica, 4(1), 1971, 31–36.
• [9] Marcus, S.: The poetic relevance of the information energy, in: Studies in Probability and Related Topics (M. Demetrescu, M. Iosifescu, Eds.), Nagard, Roma, 1983, 355–360.
• [10] Marcus, S.: Symmetry as periodicity and complexity as absence of symmetry, Proceedings of the 2nd International Conference on Symmetry and Antisymmetry in Mathematics, Formal Languages and Computer Science, Satellite Conference of the Third European Congress of Mathematics, Brasov, June 29 – July 1, 2000, 17–19.
• [11] Nicolescu, R.: Uniqueness theorems for T-codes, TR.9, Tamaki Report Series, Auckland, September 1995.
• [12] Nicolescu, R., Titchener, M. R.: Uniqueness theorems for T-codes, Romanian Journal of Information Science and Technology, 1(3), 1998, 243–258.
• [13] Solomonoff, R. J.: A formal theory of inductive inference, Information and Control, Part I: 7(1), 1964, 1–22, Part II: 7(2), 1964, 224–254.
• [14] Titchener, M. R.: A measure of information, Proceedings Data Compression Conference, Snowbird, UT, 2000, 353–362.
• [15] Titchener, M. R.: Deterministic computation of complexity, information and entropy, Proceedings IEEE International Symposium on Information Theory, 16–21 Aug 1998, 326.
• [16] Titchener,M. R.: A novel deterministicmethod for evaluating the entropy of language texts, 3rd Conference in Information-Theoretic Approaches to Logic, Languages, and Computation, Hsi-tou, Taiwan, June 1998.
• [17] Titchener,M. R.: A deterministic theory of complexity, information and entropy, IEEE Information Theory Workshop, San Diego, CA, February 1998, 80.
• [18] Titchener, M. R.: Generalised T-codes: extended construction algorithm for self-synchronising codes, IEE Proceedings – Communications, 143(3), 1996, 122–128.
• [19] Titchener,M. R.: Digital encoding by means of new T-codes to provide improved data synchronization and message integrity, IEE Proceedings – Computers and Digital Techniques, Technical Note, 131(4), 1984, 51–53.
• [20] Titchener,M. R., Gulliver, A., Nicolescu, R., Speidel, U., Staiger, L: Deterministic Complexity and Entropy, TR 253, CDMTCS, Auckland, 2004.
• [21] Wackrow, S., Titchener, M. R., G¨unther U.: Tcalc.c, Source code under GNU licence, The University of Auckland, 1999, http://tcode.auckland.ac.nz/~mark/tcalc.c.
• [22] Yang, J., Speidel, U.: An improved T-decomposition algorithm, Fourth ICICS and IEEE PCM Proceedings, Singapore, December 2003, Vol.3, 1551–1555.