37 citations · 180 across the 24 of their papers we have counts for
25 papers
Vocabulary Growth Fundamentals: Bernstein Functions and Hausdorff Sequences
Łukasz Dębowski
We survey the theory of vocabulary growth founded in the setting of stochastic processes. In particular, we model the expected number of types through Bernstein functions and Hausd…
From Letters to Words and Back: Invertible Coding of Stationary Measures
Łukasz Dębowski
Motivated by problems of statistical language modeling, we consider probability measures on infinite sequences over two countable alphabets of a different cardinality, such as lett…
Corrections of Zipf's and Heaps' Laws Derived from Hapax Rate Models
Łukasz Dębowski
The article introduces corrections to Zipf's and Heaps' laws based on systematic models of the proportion of hapaxes, i.e., words that occur once. The derivation rests on two assum…
Repetition and recurrence times: Dual statements and summable mixing rates
Łukasz Dębowski
By an analogy to the duality between the recurrence time and the longest match length, we introduce a quantity dual to the maximal repetition length, which we call the repetition t…
Multiperiodic Processes: Ergodic Sources with a Sublinear Entropy
Łukasz Dębowski
Several explicit stochastic processes are known to satisfy Hilberg's law, a power-law growth of block entropy conjectured for natural language and recently connected to the neural…
There Are Fewer Facts Than Words: Communication With A Growing Complexity
Łukasz Dębowski
We present an impossibility result, called a theorem about facts and words, which pertains to a general communication system. The theorem states that the number of distinct words u…
Local Grammar-Based Coding Revisited
Łukasz Dębowski
In the setting of minimal local grammar-based coding, the input string is represented as a grammar with the minimal output length defined via simple symbol-by-symbol encoding. This…
Universal Densities Exist for Every Finite Reference Measure
Łukasz Dębowski
As it is known, universal codes, which estimate the entropy rate consistently, exist for stationary ergodic sources over finite alphabets but not over countably infinite ones. We g…
Bounds for Algorithmic Mutual Information and a Unifilar Order Estimator
Łukasz Dębowski
Inspired by Hilberg's hypothesis, which states that mutual information between blocks for natural language grows like a power law, we seek for links between power-law growth rate o…
Universal Coding and Prediction on Ergodic Martin-Löf Random Points
Łukasz Dębowski, Tomasz Steifer
Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to m…
On a Class of Markov Order Estimators Based on PPM and Other Universal Codes
Łukasz Dębowski
We investigate a class of estimators of the Markov order for stationary ergodic processes which form a slight modification of the constructions by Merhav, Gutman, and Ziv in 1989 a…
Is Natural Language a Perigraphic Process? The Theorem about Facts and Words Revisited
Łukasz Dębowski
As we discuss, a stationary stochastic process is nonergodic when a random persistent topic can be detected in the infinite random text sampled from the process, whereas we call th…
Maximal Repetition and Zero Entropy Rate
Łukasz Dębowski
Maximal repetition of a string is the maximal length of a repeated substring. This paper investigates maximal repetition of strings drawn from stochastic processes. Strengthening p…
Consistency of the Plug-In Estimator of the Entropy Rate for Ergodic Processes
Łukasz Dębowski
A plug-in estimator of entropy is the entropy of the distribution where probabilities of symbols or blocks have been replaced with their relative frequencies in the sample. Consist…
Regular Hilberg Processes: An Example of Processes with a Vanishing Entropy Rate
Łukasz Dębowski
A regular Hilberg process is a stationary process that satisfies both a hyperlogarithmic growth of maximal repetition and a power-law growth of topological entropy, which are a kin…
Hilberg Exponents: New Measures of Long Memory in the Process
Łukasz Dȩbowski
The paper concerns the rates of power-law growth of mutual information computed for a stationary measure or for a universal code. The rates are called Hilberg exponents and four su…
A Preadapted Universal Switch Distribution for Testing Hilberg's Conjecture
Łukasz Dębowski
Hilberg's conjecture about natural language states that the mutual information between two adjacent long blocks of text grows like a power of the block length. The exponent in this…
On Hidden Markov Processes with Infinite Excess Entropy
Łukasz Dębowski
We investigate stationary hidden Markov processes for which mutual information between the past and the future is infinite. It is assumed that the number of observable states is fi…
When is Menzerath-Altmann law mathematically trivial? A new approach
Ramon Ferrer-i-Cancho, Antoni Hernández-Fernández, Jaume Baixeries +2
Menzerath's law, the tendency of Z, the mean size of the parts, to decrease as X, the number of parts, increases is found in language, music and genomes. Recently, it has been argu…
Mixing, Ergodic, and Nonergodic Processes with Rapidly Growing Information between Blocks
Łukasz Dębowski
We construct mixing processes over an infinite alphabet and ergodic processes over a finite alphabet for which Shannon mutual information between adjacent blocks of length grow…
Variable-Length Coding of Two-Sided Asymptotically Mean Stationary Measures
Łukasz Dębowski
We collect several observations that concern variable-length coding of two-sided infinite sequences in a probabilistic setting. Attention is paid to images and preimages of asympto…
The Redundancy of a Computable Code on a Noncomputable Distribution
Łukasz Dębowski
We introduce new definitions of universal and superuniversal computable codes, which are based on a code's ability to approximate Kolmogorov complexity within the prescribed margin…
On the Vocabulary of Grammar-Based Codes and the Logical Consistency of Texts
Łukasz Dębowski
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…
Valence extraction using EM selection and co-occurrence matrices
Łukasz Dębowski
This paper discusses two new procedures for extracting verb valences from raw texts, with an application to the Polish language. The first novel technique, the EM selection algorit…