On the Vocabulary of Grammar-Based Codes and the Logical Consistency of Texts

Abstract

The article presents a new interpretation for Zipf-Mandelbrot's law in natural language which rests on two areas of information theory. Firstly, we construct a new class of grammar-based codes and, secondly, we investigate properties of strongly nonergodic stationary processes. The motivation for the joint discussion is to prove a proposition with a simple informal statement: If a text of length $n$ describes $n^{\beta }$ independent facts in a repetitive way then the text contains at least $n^{\beta }/\log n$ different words, under suitable conditions on $n$. In the formal statement, two modeling postulates are adopted. Firstly, the words are understood as nonterminal symbols of the shortest grammar-based encoding of the text. Secondly, the text is assumed to be emitted by a finite-energy strongly nonergodic source whereas the facts are binary IID variables predictable in a shift-invariant way.

24 pages, no figures

References in corpus (5)

• Entropy and Long range correlations in literary English
• Complexity Through Nonextensivity
• On Hilberg's Law and Its Links with Guiraud's Law
• Variable-Length Coding of Two-Sided Asymptotically Mean Stationary Measures
• On vocabulary size of grammar-based codes

Cited by in corpus (17)

• Prediction, Retrodiction, and The Amount of Information Stored in the Present
• Excess entropy in natural language: present state and perspectives
• Is Natural Language a Perigraphic Process? The Theorem about Facts and Words Revisited
• On Hidden Markov Processes with Infinite Excess Entropy
• Constant conditional entropy and related hypotheses
• Mixing, Ergodic, and Nonergodic Processes with Rapidly Growing Information between Blocks
• Variable-Length Coding of Two-Sided Asymptotically Mean Stationary Measures
• Maximal Repetition and Zero Entropy Rate
• The Past and the Future in the Present
• Hilberg Exponents: New Measures of Long Memory in the Process
• Trimming the Independent Fat: Sufficient Statistics, Mutual Information, and Predictability from Effective Channel States
• On a Class of Markov Order Estimators Based on PPM and Other Universal Codes
• A Preadapted Universal Switch Distribution for Testing Hilberg's Conjecture
• Universal Coding and Prediction on Ergodic Martin-Löf Random Points
• Repetition and recurrence times: Dual statements and summable mixing rates
• From Letters to Words and Back: Invertible Coding of Stationary Measures
• Bounds for Algorithmic Mutual Information and a Unifilar Order Estimator