Affiliations: Dept. of Computer Science, The University of Auckland,
New Zealand. mark@tcode.auckland.ac.nz | Dept. of Computer Science, The University of Auckland,
New Zealand | Institut für Informatik,
Martin-Luther-Universitä Halle-Wittenberg, Germany | Dept. of Electrical & Computer Engineering,
University of Victoria, Canada | Dept. of Computer Science, The University of Auckland,
New Zealand
Note: [] Address for correspondence: Dept. of Computer Science, The
University of Auckland, New Zealand
Abstract: 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.
