6 papers
The Agafonov and Schnorr-Stimm theorems for probabilistic automata
Laurent Bienvenu, Hugo Gimbert, Subin Pulari
For a fixed alphabet , an infinite sequence is said to be normal if every word over appears in with the same frequency as any other word of the same length. A cl…
Point-to-set Principle and Constructive Dimension Faithfulness
Satyadev Nandakumar, Subin Pulari, Akhil S
Hausdorff -dimension is a notion of Hausdorff dimension developed using a restricted class of coverings of a set. We introduce an effective version of Hausdorff -dimension,…
Efficient Constructions of Finite-State Independent Normal Pairs
Subin Pulari
Finite-state independence is a robust notion of algorithmic independence for infinite words. It was introduced for general infinite words by Becher, Carton, and Heiber via determin…
On Normality and Equidistribution for Separator Enumerators
Subin Pulari
A separator is a countable dense subset of , and a separator enumerator is a naming scheme that assigns a real number in to each finite word so that the set of all n…
A Markov-Chain Characterization of Finite-State Dimension and a Generalization of Agafonov's Theorem
Laurent Bienvenu, Hugo Gimbert, Subin Pulari
Finite-state dimension quantifies the asymptotic rate of information in an infinite sequence as perceived by finite automata. For a fixed alphabet, the infinite sequences that have…
One-Way Functions and Polynomial Time Dimension
Satyadev Nandakumar, Subin Pulari, Akhil S +1
This paper demonstrates a duality between the non-robustness of polynomial time dimension and the existence of one-way functions. Polynomial-time dimension (denoted $\mathrm{cdim}_…