Automatic Complexity and Block-Entropy Coding - Preparations for Lempel-Ziv Analysis

Explore a detailed seminar lecture from the Kolmogorov Seminar series on computational and descriptional complexity that delves into three distinct methods for measuring finite complexity of symbol strings. Learn how to analyze long strings through entropy of k-letter block frequency distributions, finite-state transducer input length minimization, and superadditive function properties. Understand the fundamental equivalence between these three approaches, including the connections through Huffman encoding, automaton single-letter production, and prefix complexity bounds. Gain insights into these theoretical foundations that serve as preparation for understanding the efficiency of Lempel-Ziv compression algorithms compared to block-entropy coding methods.