Author name cluster

Verónica Becher

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

I&C Journal 2025 Journal Article

Rauzy complexity and block entropy

Verónica Becher
Olivier Carton
Santiago Figueira

In 1976, Rauzy studied two complexity functions, β _ and β ‾, for infinite sequences over a finite alphabet. The function β _ achieves its maximum precisely for Borel normal sequences, while β ‾ reaches its minimum for sequences that, when added to any Borel normal sequence, result in another Borel normal sequence. We establish a connection between Rauzy's complexity functions, β _ and β ‾, and the notions of non-aligned block entropy, h _ and h ‾, by providing sharp upper and lower bounds for h _ in terms of β _, and sharp upper and lower bounds for h ‾ in terms of β ‾. We adopt a probabilistic approach by considering an infinite sequence of random variables over a finite alphabet. The proof relies on a new characterization of non-aligned block entropies, h ‾ and h _, in terms of Shannon's conditional entropy. The bounds imply that sequences with h ‾ = 0 coincide with those for which β ‾ = 0. We also show that the non-aligned block entropies, h _ and h ‾, are essentially subadditive.

Details DOI

I&C Journal 2022 Journal Article

Randomness and uniform distribution modulo one

Verónica Becher
Serge Grigorieff

We elaborate the notions of Martin-Löf and Schnorr randomness for real numbers in terms of uniform distribution of sequences. We give a necessary condition for a real number to be Schnorr random expressed in terms of classical uniform distribution of sequences. This extends the result proved by Avigad for sequences of linear functions with integer coefficients to the wider classical class of Koksma sequences of functions. And, by requiring equidistribution with respect to every computably enumerable open set (respectively, computably enumerable open set with computable measure) in the unit interval, we give a sufficient condition for Martin-Löf (respectively Schnorr) randomness.

Details DOI

I&C Journal 2013 Journal Article

A polynomial-time algorithm for computing absolutely normal numbers

Verónica Becher
Pablo Ariel Heiber
Theodore A. Slaman

We give an algorithm to compute an absolutely normal number so that the first n digits in its binary expansion are obtained in time polynomial in n; in fact, just above quadratic. The algorithm uses combinatorial tools to control divergence from normality. Speed of computation is achieved at the sacrifice of speed of convergence to normality.

Details DOI

TCS Journal 2013 Journal Article

Normal numbers and finite automata

Verónica Becher
Pablo Ariel Heiber

We give an elementary and direct proof of the following theorem: A real number is normal to a given integer base if, and only if, its expansion in that base is incompressible by lossless finite-state compressors (these are finite automata augmented with an output transition function such that the automata input–output behaviour is injective; they are also known as injective finite-state transducers). As a corollary we obtain V. N. Agafonov’s theorem on the preservation of normality on subsequences selected by finite automata.

Details DOI

TCS Journal 2012 Journal Article

A linearly computable measure of string complexity

Verónica Becher
Pablo Ariel Heiber

We present a measure of string complexity, called I -complexity, computable in linear time and space. It counts the number of different substrings in a given string. The least complex strings are the runs of a single symbol, the most complex are the de Bruijn strings. Although the I -complexity of a string is not the length of any minimal description of the string, it satisfies many basic properties of classical description complexity. In particular, the number of strings with I -complexity up to a given value is bounded, and most strings of each length have high I -complexity.

Details DOI

TCS Journal 2007 Journal Article

Random reals à la Chaitin with or without prefix-freeness

Verónica Becher
Serge Grigorieff

We give a general theorem that provides examples of n -random reals à la Chaitin, for every n ≥ 1; these are halting probabilities of partial computable functions that are universal by adjunction for the class of all partial computable functions, The same result holds for the class functions of partial computable functions with prefix-free domain. Thus, the usual technical requirement of prefix-freeness on domains is an option which we show to be non-critical when dealing with universality by adjunction. We also prove that the condition of universality by adjunction (which, though particular, is a very natural case of optimality) is essential in our theorem.

Details DOI

TCS Journal 2007 Journal Article

Turing’s unpublished algorithm for normal numbers

Verónica Becher
Santiago Figueira
Rafael Picchi

In an unpublished manuscript, Alan Turing gave a computable construction to show that absolutely normal real numbers between 0 and 1 have Lebesgue measure 1; furthermore, he gave an algorithm for computing instances in this set. We complete his manuscript by giving full proofs and correcting minor errors. While doing this, we recreate Turing’s ideas as accurately as possible. One of his original lemmas remained unproved, but we have replaced it with a weaker lemma that still allows us to maintain Turing’s proof idea and obtain his result.

Details DOI

TCS Journal 2004 Journal Article

Recursion and topology on 2⩽ω for possibly infinite computations

Verónica Becher
Serge Grigorieff

In the context of possibly infinite computations yielding finite or infinite (binary) outputs, the space 2⩽ω =2∗ ∪2ω appears to be one of the most fundamental spaces in Computer Science. Though underconsidered, next to 2 ω, this space can be viewed (Section 3. 5. 2) as the simplest compact space native to computer science. In this paper we study some of its properties involving topology and computability. Though 2⩽ω can be considered as a computable metric space in the sense of computable analysis, a direct and self-contained study, based on its peculiar properties related to words, is much illuminating. It is well known that computability for maps 2ω →2ω reduces to continuity with recursive modulus of continuity. With 2⩽ω, things get less simple. Maps 2ω →2⩽ω or 2⩽ω →2⩽ω induced by input/output behaviours of Turing machines on finite or infinite words—which we call semicomputable maps—are not necessarily continuous but merely lower semicontinuous with respect to the prefix partial ordering on 2⩽ω. Continuity asks for a stronger notion of computability. We prove for (semi)continuous and (semi)computable maps F: I→O with I, O∈{2ω, 2⩽ω} a detailed representation theorem (Theorem 81) via functions f: 2∗ →2∗ following two approaches: bottom-up from f to F and top-down from F to f.

Details DOI

TCS Journal 2002 Journal Article

An example of a computable absolutely normal number

Verónica Becher
Santiago Figueira

The first example of an absolutely normal number was given by Sierpinski in 1916, twenty years before the concept of computability was formalized. In this note we give a recursive reformulation of Sierpinski's construction which produces a computable absolutely normal number.

Details DOI